Feladat: Gy.2654 Korcsoport: 16-17 Nehézségi fok: átlagos
Megoldó(k):  Csorba Péter ,  Csörnyei Marianna ,  Faragó Gergely ,  Gefferth András ,  Győry Máté ,  Horváth Zoltán ,  Imreh Csanád ,  Kálmán Tamás ,  Katz Sándor ,  Molnár-Sáska Gábor ,  Németh Ákos ,  Németh Krisztián ,  Pór Attila ,  Újváry-Menyhárt Zoltán 
Füzet: 1991/május, 210 - 211. oldal  PDF file
Témakör(ök): Konstruktív megoldási módszer, Logikai feladatok, Oszthatóság, Gyakorlat
Hivatkozás(ok):Feladatok: 1990/november: Gy.2654

Antal 100 gyufásdobozt megszámoz 1-től 100-ig, és mindegyikbe tetszés szerinti számú gyufát tesz. Bea tetszőlegesen kiválaszt 15 dobozt, erre Antal megszámolja a bennük levő gyufákat (úgy, hogy Bea ezt ne lássa), és megmondja, hogy a 15 dobozban együttesen páros, vagy páratlan számú gyufa van-e. Bea ezt a kérdezési lépést akárhányszor megismételheti. Ki tudja-e Bea találni, hogy az 1-es számú dobozban páros vagy páratlan sok gyufa van, és ha igen, akkor mi az ehhez szükséges minimális lépésszám?

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.

Beának 3 kérdésre van szüksége, hogy biztosan kitalálhassa, hogy az 1. dobozban páros vagy páratlan számú gyufa van. Elegendő ehhez pl. a következő három kérdés:
I. 1.‐15., II. 1.‐8. és 16.‐22., III. 1. és 9.‐22.számú dobozok.
A három kérdésre adott válaszokat a paritások összeadásának ismert szabályai (páros+páros=páratlan+páratlan=páros stb.) szerint összeadva éppen az 1 dobozban lévő gyufák számának párosságát kapjuk, hiszen a három válasz összegében az 1. doboz tartalma 3-szor, a 2.‐22. dobozoké pedig kétszer szerepel, tehát ez az összeg az 1. dobozban lévő gyufák számától páros számmal különbözik.
Be kell még látnunk, hogy háromnál kevesebb kérdés nem elegendő. Ha az 1. doboz egyik kérdésben sem szerepel, akkor egy gyufát beletéve a válaszok nem változnak, de az 1. doboz párossága igen, tehát így nem található ki, hogy páros vagy páratlan számú gyufa van-e benne.
Könnyen látható, hogy egy kérdés, vagy két azonos kérdés, valamint két, közös elem nélküli kérdés sem elég, hiszen ekkor az 1. dobozba és a vele egy kérdésben szereplő dobozok egyikébe 1-1 szál gyufát helyezve a válaszok nem változnak, de az 1. doboz párossága igen.
Ha a fenti esetek egyike sem teljesül, akkor legyen
A: csak az I. kérdésben szereplő dobozok,
B: csak a II. kérdésben szereplő dobozok, végül
C: mindkét kérdésben szereplő dobozok halmaza.
Feltevésünk szerint A,B és C egyike sem lehet üres halmaz és legalább az egyikük tartalmazza az 1. dobozt. Ha most az 1. dobozba, valamint az 1.-t nem tartalmazó halmazok egy-egy dobozába egy-egy szál gyufát teszünk, akkor a két kérdésre adott válaszok nem változnak, de az 1. doboz párossága más lesz.
Fenti eredményeinket összevetve kapjuk, hogy Bea ki tudja találni az 1. dobozban lévő gyufák számának a paritását és ehhez 3 kérdésre van szüksége.

 
 Gefferth András (Bp., Fazekas M. Gyak. Gimn., II. o. t.) dolgozata alapján