A B. 5420. feladat (2024. november)

B. 5420. Ádám, a hírhedt szélhámos, a következő módon működő szerencsejátékra nevezett be. Egy szabályos \(\displaystyle 13\)-szög alakú forgóasztal mindegyik csúcsában egy piros vagy egy fekete sapka van. (Az azonos színű sapkák egymástól megkülönböztethetetlenek.)

Az egyik sapka alatt 1000 dollárt rejtettek el, a többi alatt nincsen semmi. A játékvezető megpörgeti az asztalt a középpontja körül, majd Ádám felemelhet egyetlen sapkát, és amit alatta talál, azt hazaviheti. Ádám cinkostársa, Béla, a szerencsejátékot szervező cégnél dolgozik.

Miután a sapkákat a munkatársai tetszésük szerint elhelyezték az asztal csúcsaiban, Béla feladata betenni a pénzt valamelyik sapka alá. Miután betette a pénzt,

a) ki kell cserélnie a sapkát a másik színűre,

b) kicserélheti a sapkát a másik színűre

– de a többi sapkához nem nyúlhat.

Ki tud-e dolgozni Ádám és Béla egy olyan stratégiát az a), illetve a b) esetben, amellyel biztosan megnyerik a pénzt? (Miután Béla belépett a kaszinóba, már nem beszélhet Ádámmal, és az asztalt előkészítő munkatársait sem befolyásolhatja.)

Javasolta: Damásdi Gábor (Budapest)

(6 pont)

A beküldési határidő 2024. december 10-én LEJÁRT.

Megoldás. \(\displaystyle a)\) Ebben az esetben nem tudnak mindig működő stratégiát kitalálni.

Jelölje \(\displaystyle \mathcal{S}\) az összes lehetséges megkülönböztethető sapkakiosztás halmazát. Indirekt tegyük fel, hogy Ádám és Béla rendelkezik egy mindig működő stratégiával. Ebből a stratégiából készítsünk egy \(\displaystyle f:\mathcal{S} \to \mathcal{S}\) függvényt a következő módon: \(\displaystyle f\) egy tetszőleges \(\displaystyle s\) sapkakiosztáshoz egy olyan \(\displaystyle s'\) sapkakiosztást rendel, amely előállhat Béla sapkacseréje által. Tehát \(\displaystyle s\) az az állapot, amelyet Béla kap, és \(\displaystyle s'=f(s)\) az, amelyet Béla továbbad Ádámnak. Lehetséges, hogy a stratégia egy \(\displaystyle s\) sapkakiosztásoknál többféle cserét is megenged Bélának, ilyenkor ezek közül válasszunk ki egyet és rögzítsük ennek eredményét \(\displaystyle f(s)\) értékének.

Ahhoz, hogy Ádám mindig megtalálja a pénzt, az \(\displaystyle f\) függvénynek injektívnek kell lennie, azaz ha \(\displaystyle s \neq t\) különböző sapkakiosztások, akkor \(\displaystyle f(s) \neq f(t)\) is biztosan teljesül. Hiszen ha \(\displaystyle f(s)=f(t)\) lenne, akkor Ádám nem tudhatná biztosan, hogy \(\displaystyle s\) vagy \(\displaystyle t\) sapkakiosztásból kiindulva hozta létre Béla az \(\displaystyle f(s) = f(t)\) kiosztást. De így Ádám azt sem tudhatja biztosan, hogy hol a pénz, hiszen a pénzes sapkát képzeletben visszacserélve visszakapná azt a sapkakiosztást, amit Béla kapott a munkatársaitól (\(\displaystyle f(s)\)-ből úgy kapjuk vissza \(\displaystyle s\)-t, hogy a pénzes sapka színét megcseréljük).

Mivel \(\displaystyle \mathcal{S}\) véges halmaz, ezért ha \(\displaystyle f\) injektív, akkor szürjektívnek is kell lennie. Tehát kell legyen olyan \(\displaystyle s\) sapkakiosztás, amelyre \(\displaystyle f(s)\) a csupa fekete sapkából álló sapkakiosztás. De ha Ádám csupa fekete sapkát lát, akkor semmilyen információja nincs, amellyel a 13 egyforma sapka közül megtalálhatná a pénzt rejtőt.

\(\displaystyle b)\) Mutatunk egy biztosan működő stratégiát.

Ha Béla csupa ugyanolyan színű sapkát kap, akkor tetszőlegesen választ egyet, beteszi alá a pénzt, majd kicseréli a sapkát ellentétes színűre.

Egyéb esetekben nem cserél színt. Megnézi, hogy melyik színből van kevesebb: az általánosság korlátozása nélkül feltehetjük, hogy feketéből. Ha \(\displaystyle n\) darab fekete sapka van, akkor Béla minden fekete sapkához hozzárendel egy \(\displaystyle n\) darab pozitív egész számból álló \(\displaystyle (a_1,a_2,\ldots,a_n)\) rendezett listát (\(\displaystyle n\)-dimenziós vektort), amelynek elemei azt adják meg, hogy pozitív körüljárás szerint (az óramutatóval ellentétes irányban haladva) hány csúcsnyival kell továbbmenni a következő fekete sapkáig. Egy példa látható alább (\(\displaystyle n=5\) esetén).

Világos, hogy mindegyik lista esetén teljesül, hogy \(\displaystyle a_1+a_2+\ldots+a_n =13\).

Lemma. Mivel a 13 prím, bármely két sapkához különböző lista fog tartozni.

A lemma bizonyítása. Indirekt feltevés: két különböző fekete sapkához írt lista, \(\displaystyle (a_1,a_2,\ldots,a_n)\) és \(\displaystyle (b_1,b_2,\ldots,b_n)\) megegyezik.

Jelölje \(\displaystyle 1 \leq t \leq n-1\), hogy az előbbi (\(\displaystyle a_i\) listás) fekete sapkától pozitív körüljárási irányba elindulva az utóbbi (\(\displaystyle b_i\) listás) fekete sapka hányadik a fekete sapkák sorában.

Világos, hogy ekkor \(\displaystyle b_1=a_{1+t},b_2 = a_{2+t}\) és általában \(\displaystyle b_i = a_{i+t}\), ha az indexeket modulo \(\displaystyle n\) tekintjük. Mivel az \(\displaystyle a_i\) és a \(\displaystyle b_i\) sorozat megegyezik, ezért \(\displaystyle a_i = a_{i+t} = a_{i+2t} = \ldots = a_{i+kt}\) minden \(\displaystyle k\) pozitív egészre. Az

\(\displaystyle i, i+t, i+2t, \ldots, i+kt, \ldots \)

indexsorozat két tagja, \(\displaystyle i+k_1t\) és \(\displaystyle i+k_2t\) akkor egyezik meg modulo \(\displaystyle n\), ha \(\displaystyle n \mid (k_2-k_1) t\), azaz \(\displaystyle \frac{n}{(n,t)} \mid k_2-k_1\). Következésképpen

\(\displaystyle i, i+t, \ldots, i+\frac{n}{(n,t)}t \)

modulo \(\displaystyle n\) nézve is csupa különböző index, míg \(\displaystyle k > \frac{n}{(n,t)}\) esetén \(\displaystyle i+kt\) megegyezik valamelyik felsorolt indexszel (mod \(\displaystyle n\)).

Ezzel az \(\displaystyle \{ 1,2,\ldots,n \}\) indexhalmazt felosztottuk \(\displaystyle (n,t)\) darab \(\displaystyle \frac{n}{(n,t)}\) tagú csoporta úgy, hogy ha az \(\displaystyle i\) és \(\displaystyle j\) indexek ugyanazon csoportba tartoznak, akkor valamilyen \(\displaystyle k\)-ra \(\displaystyle i + kt \equiv j\) (mod \(\displaystyle n\)), amiből persze következik, hogy \(\displaystyle a_i = a_j\).

(Az ekvivalencia-reláció fogalmát használva így fogalmazhatunk: Az \(\displaystyle \{1,2,\ldots,n\}\) halmazon a \(\displaystyle t\) konstans definiálja a \(\displaystyle i \sim j\) relációt, amely akkor teljesül, ha valamilyen \(\displaystyle k\)-ra \(\displaystyle i + kt \equiv j\) mod \(\displaystyle n\). Világos, hogy \(\displaystyle \sim\) ekvivalencia-reláció. Fentebb lényegében azt láttuk be, hogy a \(\displaystyle \sim\) reláció \(\displaystyle (n,t)\) darab, egyenként \(\displaystyle \frac{n}{(n,t)}\) elemű ekvivalencia-osztályra bontja az alaphalmazt.)

De ezek szerint az \(\displaystyle a_1,a_2,\ldots,a_n\) sorozatban minden szám \(\displaystyle \frac{n}{(n,t)} \ell\)-szer szerepel (valamilyen \(\displaystyle 1 \leq \ell \leq (n,t)\) egészre). Ebből az következik, hogy

\(\displaystyle \frac{n}{(n,t)} \mid a_1 + a_2 + \ldots + a_n = 13. \)

Ez viszont lehetetlen, mivel \(\displaystyle 1 < \frac{n}{(n,t)} \leq 6\), míg 13 prímszám. (\(\displaystyle 1 < \frac{n}{(n,t)}\) abból következik, hogy \(\displaystyle t \leq n-1\), másrészt pedig \(\displaystyle \frac{n}{(n,t)} \leq n \leq 6\).) Ezzel a lemmát beláttuk.

Tudjuk tehát, hogy mindegyik fekete sapkához különböző lista tartozik. Béla ezek közül a listák közül kiválasztja a lexikografikusan legelsőt (pl. a fenti ábrán a \(\displaystyle (2,2,3,2,4)\) lesz ez) és elrejti alá a pénzt; a sapkát nem cseréli ki. Ugyanezeket a listákat Ádám is le tudja gyártani, megkeresi a lexikografikusan legelsőt, és kiveszi alóla a pénzt. Ha Ádám csak egyetlen fekete (vagy egyetlen piros) sapkát lát, akkor persze nem fogja tudni, hogy ez a sapka cserélve lett-e vagy sem. De a pénzt biztosan megtalálja alatta.

Statisztika:

41 dolgozat érkezett.
6 pontot kapott:	Ali Richárd, Baran Júlia, Bencze Mátyás, Bolla Donát Andor, Bui Thuy-Trang Nikolett, Csató Hanna Zita , Görömbey Tamás, Hodossy Réka, Holló Martin, Kovács Benedek Noel, Molnár István Ádám, Pázmándi József Áron, Péter Hanna, Pletikoszity Martin, Rajtik Sándor Barnabás, Sárdinecz Dóra, Sütő Áron, Szabó 721 Sámuel, Tamás Gellért, Virág Tóbiás, Vödrös Dániel László, Wágner Márton.
4 pontot kapott:	8 versenyző.
3 pontot kapott:	2 versenyző.
2 pontot kapott:	1 versenyző.
1 pontot kapott:	2 versenyző.
0 pontot kapott:	4 versenyző.

A KöMaL 2024. novemberi matematika feladatai