Problem B. 5264. (October 2022)

B. 5264. First Player and Second Player play the following game. First Player starts and prescribes arbitrarily many (even infinitely many) terms of a binary sequence (i.e., any term is \(\displaystyle 0\) or \(\displaystyle 1\)) in a way that infinitely many terms can still be determined. Then Second Player sets the value of the first digit which has not been prescribed yet. They then repeat this procedure forever by taking turns. First Player wins if the binary sequence is periodic from a certain term, otherwise, Second Player wins. Is there a winning strategy, and if yes, who has it?

Proposed by Péter Pál Pach, Budapest

(4 pont)

Deadline expired on November 10, 2022.

Sorry, the solution is available only in Hungarian. Google translation

Megoldás. Azt mutatjuk meg, hogy Másodiknak van nyerő stratégiája. Legyen a sorozat, amit meghatároznak, \(\displaystyle (a_n)\). Tekintsük a következő \(\displaystyle (s_i)\) sorozatot:

\(\displaystyle 1,1,2,1,2,3,1,2,3,4,1,2,3,4,5,\dots,\)

amit úgy kapunk, hogy az \(\displaystyle 1,2,\dots,n\) sorozatokat fűzzük egymás után \(\displaystyle n=1\)-től kezdve. Második stratégiája legyen az, hogy az általa \(\displaystyle i\)-edik lépésben előírandó \(\displaystyle a_t\) értékét úgy választja meg, hogy amennyiben \(\displaystyle t> s_i\), akkor \(\displaystyle a_t\ne a_{t-s_i}\) legyen (vagyis \(\displaystyle a_t:=1-a_{t-s_i}\) értéket írja elő). Ha \(\displaystyle t\leq s_i\), akkor \(\displaystyle a_t\) értékét tetszőlegesen megválaszthatja.

Megmutatjuk, hogy a kapott sorozat nem lesz valahonnan kezdve periodikus. Elég belátni, hogy semmilyen \(\displaystyle 0<p\) mellett nem lesz valahonnan periodikus \(\displaystyle p\) periódussal. A \(\displaystyle p\) szám az \(\displaystyle s_i\) sorozatban végtelen sokszor szerepel. Ezek közül csak véges sokszor lehet, hogy az előírandó \(\displaystyle a_t\) szám indexére \(\displaystyle t\leq p\). Így végtelen sokszor az általa előírt \(\displaystyle a_t\)-re \(\displaystyle a_t\ne a_{t-p}\), tehát a sorozat nem periodikus \(\displaystyle p\) periódussal.

Ezzel beláttuk, hogy Másodiknak van nyerő stratégiája.

Statistics:

59 students sent a solution.
4 points:	Ali Richárd, Christ Miranda Anna, Chrobák Gergő, Czanik Pál, Domján Olivér, Duchon Márton, Fórizs Emma, Fülöp Csilla, Kovács Benedek Noel, László Anna, Melján Dávid Gergő, Molnár István Ádám, Nagy 429 Leila, Nguyen Kim Dorka, Simon László Bence, Szakács Ábel, Szakács Domonkos, Szeibert Dominik, Tarján Bernát, Varga Boldizsár, Virág Rudolf, Wiener Anna, Zömbik Barnabás.
3 points:	Csilling Dániel, Csonka Illés, Czirják Márton Pál, Han Ziying, Kocsis 827 Péter, Sági Mihály.
2 points:	5 students.
1 point:	10 students.
0 point:	10 students.
Unfair, not evaluated:	3 solutionss.
Not shown because of missing birth date or parental permission:	1 solutions.

Problems in Mathematics of KöMaL, October 2022