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:

A B. 5420. feladat értékelése még nem fejeződött be.

A KöMaL 2024. novemberi matematika feladatai