Megoldás: 5.3
a) Ossza Bea négy ötös csoportba a dobozokat, legyen a négy csoport A, B, C és D. Az első öt doboz legyen
A-ban, az utolsó öt
D-ben. Kérdezze meg először
A+B+D, majd
A+C+D paritását. A két eredményt összeadva megtudja
B+C paritását. Harmadszorra megkérdezi
A+B+C-t és megtudja
A paritását.
Most kérdezze meg
1.+2.+3.+B+C+19.+20.-t, így
A+B+C-vel összevetve megtudja
4.+5.+19.+20. paritását. (
x. az
x-edik dobozt jelöli.) Végül kérdezze meg
1.+4.+5.+B+C+19.+20. paritását. Ezt
A+B+C-vel összevetve megtudja
2.+3.+19.+20. paritását, s ezt az előbbi eredménnyel összevetve megvan
2.+3.+4.+5. paritása is. Másrészt
A paritását már tudja, tehát megvan az első doboz paritása is.
Megmutatjuk, hogy négy kérdéssel Bea nem érhet célhoz. Ha négy kérdést tesz fel, ebben összesen (multiplicitással számolva) 60 doboz szerepel. Összesen 20 doboz van, tehát vagy minden doboz pontosan háromszor szerepel, vagy van egy doboz, amelyik legalább négyszer szerepel.
Tegyük fel először, hogy van olyan, az 1-estől különböző doboz, amely mind a négy kérdésében szerepel. Feltehetjük, hogy ez a 2-es doboz. Bea ugyanazokat a válaszokat kapná, ha Antal minden, a 2-estől különböző dobozba még egy gyufát tett volna. Márpedig a két esetben különböző az 1-es dobozban levő gyufák paritása.
Ha csak az 1-es doboz szerepel mind a négy kérdésben, akkor egy kivétellel minden más doboz három kérdésben szerepel, egy pedig kettőben, hiszen összesen 60 doboz szerepel a kérdésekben, és
4+3·18+2=60. Van tehát olyan doboz, amely az első kérdésben nem szerepel és a többiben szerepel, feltehetjük, hogy ez a 2-es doboz. Ugyanígy van egy-egy doboz, amely csak a második, a harmadik, illetve a negyedik kérdésben nem szerepel, legyenek ezek rendre a 3-as, a 4-es és az 5-ös doboz. Bea most ugyanazokat a válaszokat kapná, ha az első öt dobozban egy-egy gyufával több volna, mert közülük pontosan négy szerepel minden kérdésében. Az első dobozban levő gyufák paritása pedig a két esetben különböző.
Marad az az eset, ha minden doboz három kérdésben szerepel. Feltehetjük, hogy az 1-es doboz az utolsó kérdésben nem szerepel (az előző háromban pedig szerepel). Nyilván van még egy (sőt, még négy) doboz, amelyre ugyanez igaz. Feltehetjük, hogy például a 2-es dobozra igaz. Bea most ugyanazt a választ kapná, ha e két dobozban egy-egy gyufával több volna, s az első dobozban levő gyufák paritása most is különböző a két esetben.
Ezzel beláttuk, hogy négy kérdésből Bea nem tudja meghatározni az első dobozban levő gyufák paritását. Nem tettük fel, hogy ne volnának azonos kérdései, így kevesebb kérdés sem lehet elég, hiszen ha kevesebb kérdés elég volna, akkor egy kérdést többször feltéve négy kérdés is elég volna.
Végül megmutatjuk, hogy már 19 doboz is elég ahhoz, hogy Bea öt kérdéssel célhoz érjen. Most minden kérdésből négy dobozt kell kihagynia. Ha sikerül úgy megtennie ezt, hogy minden dobozt páratlan sokszor hagyjon ki, kivéve az 1-est, akkor célhoz ért. Könnyen kiszámolható, hogy ezt úgy érheti el, ha az első dobozt kétszer hagyja ki, a többit egyszer-egyszer. Ezt valóban meg is teheti: az első két kérdésben hagyja ki az 1-es dobozt, ezenkívül az első kérdésben még a 2-es, 3-as és 4-es dobozt, a második kérdésben az 5-ös, 6-os és 7-es dobozt. A maradó három kérdésben hagyja ki egyszer-egyszer az eddig ki nem hagyott 12 dobozt. Így minden doboz páros sok kérdésben szerepel, kivéve az 1-es dobozt, ami páratlan sok kérdésben. Ha tehát a kapott válaszokat összeadja, megkapja az 1-es dobozban szereplő gyufák számának paritását.
b) Most Bea hat darab hármas csoportba osztja a dobozokat: A, B, C, D, E, F,
A-ban van 1.,2.,3. doboz,
F-ben az utolsó három. Bea először megkérdi az összes dobozból
B-be esőket kihagyva, majd rendre a
C-be,
D-be,
E-be és végül az
F-be esőket kihagyva, akkor a kapott öt választ mod 2 összeadva épp
A paritását kapja, hiszen az öt másik csoportbelieket páros sokszor (négyszer) kérdezte. Ezután kérdezze meg
1.+3.+B+C+D+E+20.-at, és
1.+2.+B+C+D+E+20.-at. Ezeket összeadva megtudja 2. és 3. doboz paritásának összegét. De tudja
A paritását is, így tudja az 1. dobozét is. Ez hét kérdés.
Hat kérdéssel Bea nem találhatja ki az első dobozban levő gyufák számának paritását. Ha ugyanis hat kérdést tesz fel, akkor a kérdezett dobozok száma (multiplicitással) 90. Tehát vagy van olyan doboz, amely mind a hat kérdésében szerepel, vagy minden doboz pontosan öt kérdésben szerepel. Ha minden doboz pontosan öt kérdésében szerepel, akkor feltehetjük, hogy az 1-es doboz az utolsó kérdésben nem szerepel, s hogy ebben a kérdésben rajta kívül még a 2-es és a 3-as doboz nem szerepel. Ha az 1-es és a 2-es dobozban gyufák száma eggyel nagyobb volna, Antal akkor is minden kérdésre ugyanazt a választ adná, pedig az 1-es dobozban levő gyufák száma a két esetben különböző paritású. Ez az eset tehát nem lehetséges.
Ha például a 2-es doboz mind a hat kérdésben szerepel, akkor Bea mind a hat kérdésére ugyanazt a választ kapná, ha a 2-es kivéve minden dobozban eggyel több gyufa volna, márpedig a két esetben most is különböző paritású az 1-es dobozban levő gyufák száma.
Végül ha csak az 1-es doboz szerepel mind a hat kérdésben, akkor egy kivétellel minden további doboz ötször szerepel. Mivel minden kérdésben pontosan három doboz nem szerepel, van egy-egy olyan doboz, amely csak az első, csak a második, stb. kérdésben nem szerepel. Feltehetjük, hogy az első kérdésben a 2-es, a másodikban a 3-as, a harmadikban a 4-es, a negyedikben az 5-ös, az ötödikben a 6-os, a hatodikban a 7-es doboz nem szerepel, s hogy ezek a dobozok a többi kérdésben szerepelnek. Ha mind e hét dobozban eggyel-eggyel több gyufa volna, Antal válaszai ugyanazok volnának, hiszen minden kérdésnél e dobozok közül hat szerepel. Viszont az 1-es dobozban változott a gyufák paritása, tehát Bea most sem tudja meghatározni az 1-es dobozban levő gyufák paritását.
Hat kérdés tehát nem elég, s akkor kevesebb sem (l. az a) rész megoldásának végét).
c) Ha sorra kihagyja az 2., 3., ..., 15., 16. dobozt, akkor az eredményeket összeadva éppen az 1. paritását kapja. Hiszen minden más dobozt páros sokszor (14-szer) kérdezett, míg az 1. dobozt páratlan sokszor. Tehát 15 kérdéssel Bea célhoz ér.
Viszont 14 kérdéssel nem tudja kitatlálni az 1-es doboz paritását. Ha csak 14-et kérdez, akkor van két doboz, amelyik minden kérdésében szerepel. Ha az egyik az 1-es, akkor Antal válaszai nem változnak, ha e két dobozhoz egy-egy gyufát hozzáadna. Ha pedig mondjuk a 2-es és a 3-as szerepel minden kérdésben, akkor a 2-es kivételével minden dobozba rakjon egy-egy gyufát Antal, így minden kérdésben 14-gyel nő a gyufák száma, tehát a válasz nem változik. (15 dobozban nőtt a gyufák száma és ebből egy-egy nem szerepel Bea kérdéseiben.)
Mindkét esetben változik az 1-es dobozban a gyufák számának paritása, viszont Antal válaszai nem változnak. Tehát Bea 14 kérdéssel nem ér célhoz.
Megjegyzés. A feladatnak lineáris algebrai háttere van. Például az a) rész esetében arról van szó, hogy Antal gondol egy 20-dimenziós vektorra mod 2, és Bea néhány 20-dimenziós vektort kérdezhet a mod 2 számtest felett, mégpedig olyant, amiben pontosan 15 db. egyes van. Bebizonyítható, hogy Bea pontosan akkor tudja kitalálni
k kérdéssel az első dobozban levő gyufák számának paritását, ha van legfeljebb
k ilyen vektor, amelyek összege az a 20-dimenziós vektor, amelynek az első koordinátája 1, a többi koordinátája 0. Nyilvánvaló, hogy páros sok ilyen vektor összege nem lehet az
(1,0,…,0) vektor, mert páros sok ilyen vektor összegében páros sok 1-es van. Az is világos, hogy az elsőt kivéve minden koordináta páros sok kérdésben kell, hogy 1-es legyen, az első viszont páratlan sokban. Ez
k=3 esetben legfeljebb
3+19·2=41 egyes lehet, ám három ilyen vektorban 45 egyes van. Tehát
k legalább öt.
k=5 kérdéssel valóban célt érhet Bea, a kérdésekhez tartozó vektorok könnyen felírhatók az ismertett megoldás alapján. Hasonlóan bizonyíthatjuk a b) részben, hogy
k legalább hét.
Végül ezzel a lineáris algebrai átfogalmazással (amelynek feladatunkkal való ekvivalenciája korántsem triviális) is bebizonyítjuk, hogy a c) részben 14 kérdés nem lehet elég. Tegyük fel ugyanis, hogy van
k darab 16-dimenziós 0-1 vektor,
v1
,
v2
, ...,
vk
, amelyek mod 2 vett összege az
(1,0,…,0) vektor. Láttuk már, hogy
k páratlan. Vonjuk ki mindegyik vektort a csupa-1 vektorból.
Legyen
v ez a csupa-1 vektor. Adjuk össze mod 2 az így kapott vektorokat, ezek összege
v-
∑1≤i≤k
vi
, mert
k páratlan. Vagyis az összegnek az
(0,1,…,1) vektornak kell lennie. Márpedig a
v-
vi
vektorok egy-egy 1-esből állnak, a többi helyen csupa 0 van. Ilyen vektorból legalább 15 kell, hogy az összeg olyan vektor legyen, amelyben 15 darab egyes van.