Feladat: 5.2.
Antal 100 gyufásdobozt megszámoz 1-től 100-ig, és mindegyikbe tetszése szerinti számú gyufát tesz. Bea tetszőlegesen kiválaszt 15 dobozt (ő dönti el, melyikeket), 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. 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? (OKTV, 1990)
Megoldás: 5.2
Bea két kérdéssel nyilván nem tudja megállapítani, hogy egy dobozban levő gyufák száma páros-e vagy páratlan. Nyilván két különböző kérdést fog feltenni, és nyilván legalább az egyikben fog szerepelni az 1-es doboz. Ha az 1-es doboz mindkét kérdésében szerepel, akkor van egy
x és egy
y doboz, amelyek közül
x csak az első kérdésben,
y csak a második kérdésben szerepel. Rakjon Antal egy-egy gyufát az 1-es, az
x és az
y dobozba, így válaszai nem változnak, márpedig az 1-es dobozban levő gyufák száma egyik esetben páros, másik esetben páratlan. Ha az 1-es doboz csak az egyik kérdésében szerepel, és van egy másik,
x doboz, amely szintén csak ebben a kérdésben szerepel, akkor Antal válasza ugyanaz lenne, ha e két dobozba beletenne egy-egy gyufát, márpedig az 1-es dobozban levő gyufák paritása nem változik. Marad az az eset, ha az 1-es dobozon kívül minden más doboz szerepel mindkét kérdésében. De ha például a 2-es doboz szerepelne mindkét kérdésben, akkor Antal válasza nem változna, ha a 2-esen kívül minden dobozba tenne egy további gyufát.
Két kérdéssel tehát Bea nem érhet célhoz. Három kérdéssel viszont már igen. Legyen
A={2,3,4,5,6,7,8}
B={9,10,11,12,13,14,15} és
C={16,17,18,19,20,21,22,23}. A három kérdés legyen a következő:
A∪C,
B∪C és
A∪B∪{1}. Ez három 15 elemű halmaz.
A,
B,
C minden elemére kétszer kérdez rá,
1-re egyszer. Tehát az első dobozban levő gyufák paritása egyenlő lesz az Antal által adott három válasz összegének paritásával.