Problem B. 4039. (November 2007)

B. 4039. Ann és Bill take turns writing digits of 0 or 1 from left to right next to each other. Ann starts. The game ends when each of them has written down exactly 2007 digits. The resulting sequence of zeros and ones is read as a number written in binary notation. Ann wins if the result is the sum of two perfect squares and Bill wins if it is not. Which of them has a winning strategy?

(4 pont)

Deadline expired on December 17, 2007.

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

Megoldás: Bandinak van nyerő stratégiája. Ha ugyanis mindig ugyanazt a számjegyet írja le, amit Andi éppen előzőleg leírt, akkor valamilyen 0m2006 egész számra a sorozat utolsó 2m számjegye 0 lesz, ami előtt közvetlenül 2 darab 1-es számjegy áll. A kiolvasott n szám tehát 4^mk alakban írható fel, ahol k 4-gyel osztva 3 maradékot ad. Tegyük fel, hogy alkalmas a,b egész számokkal n=a²+b². Páratlan szám négyzete 4-gyel osztva 1 maradékot ad, páros szám négyzete pedig osztható 4-gyel. Ha m>0, akkor ezek szerint a és b is páros kell legyen, vagyis az a₁=a/2, b₁=b/2 egész számokkal a₁²+b₁²=n/4=4^m-1k. Ezt ismételgetve azt kapjuk, hogy szükségképpen a_m=a/2^m és b_m=b/2^m olyan egész számok, amelyekre a_m²+b_m²=k; ez a megállapítás m=0 esetén is érvényes. Mivel két négyzetszám összege nem adhat 4-gyel osztva 3 maradékot, mindenképpen elentmondásra jutunk, vagyis n nem lehet két négyzetszám összege, tehát a megadott stratégiát követve Bandi megnyeri a játékot.

Statistics:

61 students sent a solution.
4 points:	Aczél Gergely, Ágoston Tamás, Angyal Levente, Bálint Dániel, Bartha Zsolt, Bencs 111 Ferenc, Blázsik Zoltán, Bodor Bertalan, Cséke Balázs, Dinh Van Anh, Éles András, Énekes Péter, Farkas Márton, Fonyó Dávid, Frankl Nóra, Gévay Gábor, Gőgös Balázs, Horváth 385 Vanda, Károlyi Gergely, Kiss 243 Réka, Kiss 716 Eszter, Kiss 902 Melinda Flóra, Konkoly 001 Csaba, Kovács 729 Gergely, Lenger Dániel, Márkus Bence, Mészáros András, Somogyi Ákos, Szalkai Balázs, Szőke Nóra, Tossenberger Anna, Tóth 369 László Márton, Varga 171 László, Véges Márton, Wang Daqian.
3 points:	Csere Kálmán, Kovács 999 Noémi, Müller Márk.
2 points:	3 students.
1 point:	7 students.
0 point:	12 students.
Unfair, not evaluated:	1 solutions.

Problems in Mathematics of KöMaL, November 2007