Feladat: F.2610 Korcsoport: 18- Nehézségi fok: átlagos
Megoldó(k):  Bánkövi Johanna ,  Beke Tibor ,  Benczúr András ,  Bereczky Á. ,  Binder Zsuzsanna ,  Csáki Cs. ,  Cser Z. ,  Csirik János ,  Csürös M. ,  Cynolter G. ,  Dienes J. ,  Drasny G. ,  Fodróczky T. ,  Gács András ,  Gyuris V. ,  Hajdú Gábor ,  Hajnal Z. ,  Jalsovszky P. ,  Kántor A. ,  Károlyi Gy. ,  Keleti T. ,  Kiss 303 B. ,  Kovács Tamás ,  Lipták L. ,  Madas P. ,  Mátrai Katalin ,  Őrsi A. ,  Paál B. ,  Pál G. ,  Rimányi R. ,  Sass B. ,  Szabó 484 P. ,  Szabó 522 Beáta ,  Szabó 639 A. ,  Szabó 668 T. ,  Szalay György ,  Talata I. ,  Tasnádi T. ,  Tóth 178 G. ,  Varga G. ,  Vargay P. ,  Vasy A. ,  Veres E. ,  Zaránd G. ,  Zsigmond L. 
Füzet: 1987/május, 205 - 207. oldal  PDF  |  MathML 
Témakör(ök): Mátrixjátékok, Játékelmélet, játékok, Feladat
Hivatkozás(ok):Feladatok: 1986/december: F.2610

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. Fel fogjuk használni a KÖMAL 1986. évi 4. számában megjelent "A lámpácskás játékról'' című cikkben bizonyított, könnyen belátható tételeket. Eszerint egy gombnyomássorozat után előálló minta nem függ attól, hogy a gombokat milyen sorrendben nyomtuk meg; egy gomb kétszeri megnyomása pedig nem változtat a mintán, tehát ha egy gombnyomássorozatban a páros sokszor lenyomott gombokat nem nyomnánk le, a páratlan sokszor lenyomottakat pedig csak egyszer, akkor ugyanazt a mintát kapnánk. Minden gombnyomássorozat helyett tehát tekinthetünk egy ún. lenyomásmintát, amelyben a páros sokszor lenyomott gombok helyén 0, a páratlan sokszor lenyomottak helyén pedig 1 áll.
Elegendő tehát azt belátni, hogy minden, legalább 18 darab 1-est tartalmazó lenyomásmintához tartozik egy 18-nál kevesebb 1-est tartalmazó, amely ugyanazt a világításmintát hozza létre.

 
 
1. ábra
 

Vegyünk egy tetszőleges, legalább 18 darab 1-est tartalmazó lenyomásmintát. Adjuk ehhez hozzá az 1. ábrán látható lenyomásmintát, amelyről könnyen belátható, hogy egyetlen lámpa állapotát sem változtatja meg. (Két lenyomás-mintát úgy adhatunk össze, hogy az elemeket páronként modulo 2 összeadjuk ‐ vagyis 1+1=0 lesz. Nyilvánvaló, hogy két lenyomás-mintához tartozó egy-egy gombnyomássorozat egymás utáni elvégzésekor tulajdonképpen az összegként kapott lenyomásmintát hajtjuk végre.) Ez a lenyomásminta 16 darab 1-est tartalmaz, az eredeti legalább 18-at, így a 25 lámpa közül legalább 16+18-25=9 helyén mindkét mintában 1-es fog állni, az összegként kapott lenyomásminta tehát legalább 9 darab 0-ást, azaz legfeljebb 16 darab 1-est tartalmaz.
Mivel az ábrán látható lenyomásminta minden lámpa állapotát változatlanul hagyja, az összegként kapott lenyomásminta ugyanazt a világításmintát állítja elő, mint az eredeti. Eszerint minden, legalább 18 darab 1-est tartalmazó lenyomásmintához találhatunk egy legfeljebb 16 (vagyis 18-nál biztosan kevesebb) 1-est tartalmazó lenyomásmintát, amely ugyanazt a világításmintát hozza létre; és ezt akartuk igazolni.
 

II. megoldás: Az előbbi módon elindulva a bizonyítást másképpen is befejezhetjük.
Tekintsünk egy tetszőleges lenyomásmintát. A benne szereplő 1-esek közül az 1. ábrán is 1-essel jelölt helyeken állók száma legyen a, a 0-val jelölt helyeken állóké pedig b (a≦16, b≦9). A lenyomásmintában ekkor a+b darab 1-es szerepel. Ha hozzáadjuk az 1. ábrán szereplő lenyomásmintát, akkor az összegben 16-a+b darab 1-es szerepel. Ugyanaz a világításminta tehát a+b és 16-a+b gomb lenyomásával is előáll.
Ezek számtani közepe a+b+16-a+b2=8+b≦8+9=17. Ha két szám számtani közepe nem nagyobb 17-nél, akkor a két szám sem lehet egyszerre nagyobb 17-nél, tehát vagy az eredeti, vagy az összegként kapott lenyomásmintában legfeljebb 17 darab 1-es áll.
Ezzel a gondolattal könnyen élesíthető az állítás, és belátható, hogy minden mintázat előállítható legfeljebb 15 gomb megnyomásával is.
Az említett cikkben láttuk, hogy a triviális (25 db 0-ból álló) lenyomásmintán kívül pontosan 3 olyan lenyomásminta van, amely nem változtat a lámpák állapotán:
 
 
2. ábra
 

Tekintsük most a 3. ábrán látható táblázatot. Látható, hogy a b, c, d betűk közül kettőt kiválasztva, és ezekre a helyekre 1-est, a többire 0-t írva éppen a 2. ábra 0-lenyomásmintáit kapjuk.
 
 
3. ábra
 

Az idézett cikkben olvasható, hogy egy adott lenyomásminta által előállított világításmintát még három másik lenyomásminta állít elő, és ezeket úgy kapjuk, hogy az eredetihez a fenti három "0-minta''egyikét hozzáadjuk.
Tekintsünk most egy tetszőleges lenyomásmintát, és jelöljük a, b, c, d-vel a 3. ábra táblázatán a megfelelő betűvel jelölt helyeken álló 1-esei számát. A lenyomás-mintában így a+b+c+d darab 1-es áll. A lenyomásmintához a fenti három 0-mintából egyet-egyet hozzáadva az összegekben az 1-esek száma rendre: a+8-b+8-c+d; a+8-b+c+4-d; a+b+8-c+4-d. A négy, azonos világításmintát előállító lenyomásmintában tehát az 1-esek számának átlaga a+10≦15, vagyis van köztük olyan, amelyben legfeljebb 15 darab 1-es szerepel.
 
 
4. ábra
 

Az állítás tovább már nem élesíthető, hiszen ha 5 darab a, 4 darab b, 4 darab c és 2 darab d betű helyére írunk 1-est, akkor az így kapott lenyomásminta és mindhárom, vele azonos mintázatot létrehozó lenyomásminta 15‐15 darab 1-est tartalmaz. (Pl. a 4. ábra mintázatát az 5. ábra lenyomásmintái állítják elő.)
 
 
5. ábra