Feladat: Gy.1960 Korcsoport: 14-15 Nehézségi fok: könnyű
Füzet: 1981/november, 143 - 144. oldal  PDF  |  MathML 
Témakör(ök): Kombinatorika, Gyakorlat
Hivatkozás(ok):Feladatok: 1981/február: Gy.1960

A szöveg csak Firefox böngészőben jelenik meg helyesen. Használja a fenti PDF file-ra mutató link-et a letöltésre.

I. megoldás. Tegyük fel, hogy egy színből sincs több gyöngy, mint pirosból. Fűzzük fel füzérbe a gyöngyöket a pirosakon kezdve, majd a kékeken és sárgákon át folytatva a zöldekig. Vágjuk szét középen két egyforma darabra a kapott fűzért, és húzzuk előre a második felét (anélkül hogy megfordítanánk) az első darab alá.


Fésüljük össze a felsőn kezdve a két füzért, vagyis felváltva tegyünk át róluk egy-egy gyöngyöt a készítendő nyakláncra. Megmutatjuk, hogy ezen nem kerülhet két szín egymás mellé. A nyaklánc készítését piros gyönggyel kezdjük, és biztos, hogy nem pirossal fejezzük be, hiszen piros gyöngyünk sem lehet több, mint a többi együttvéve. Emiatt az alsó füzérre már egyáltalán nem kerülhet piros gyöngy. Ha más szín nem fordul elő egyidejűleg lent és fent az összefésülés előtt, akkor készen is vagyunk a bizonyítással, hiszen a láncra a két füzér gyöngyei felváltva kerülnek. Csak az a szín találkozhatna önmagával, amelyiket kettévágunk a nagy füzéren. Ez viszont azt jelentené, hogy az egymás alá kerülő pároknak legalább az egyik tagja (kezdetben lent, aztán fent) kettévágott színű volna. Ámde ekkor a kettévágott színből legalább ötven gyöngyünk volna. Mivel ebből sincs több, mint pirosból, így piros is legalább ötven volna. De ekkor a felső füzér csupa piros gyöngyből állna, tehát mégsem volna kettévágott szín. Ellentmondásra jutottunk, ami azt bizonyítja, hogy jó nyakláncot csináltunk.
 

II. megoldás. Jelöljük a piros, kék, sárga és zöld gyöngyök számát rendre p-vel, k-val, s-sel és z-vel, és tegyük fel, hogy
p≥k≥s≥z.(1)
Készítsük el az első, nagy füzért ugyanúgy, mint. az I. megoldásban, de ezt most csupa p hosszúságú darabra vágjuk szét, kivéve az utolsó darabot, ami természetesen lehet p-nél rövidebb. Tegyük egymás alá a kapott darabokat, és fésüljük össze őket felülről lefelé haladva.

Biztosan jó nyakláncot kapunk, hiszen most csak azokat a színeket vághatjuk ketté, amelyekből p-nél kevesebb van, tehát nem kerülhetnek azonos színű gyöngyök egymás alá. Mivel p≤50, legalább még egy p hosszúságú darabunk lesz, így minden piros gyöngy mögé jut más színű gyöngy, a kapott lánc valóban megfelelő.
 

Megjegyzés. Mindkét megoldás könnyen módosítható úgy, hogy csak annyit használjunk fel, hogy egy színből sincs több, mint a többiből együttvéve. Különben a színek és a gyöngyök száma tetszőleges lehet.