Mathematical and Physical Journal
for High Schools
Issued by the MATFUND Foundation
Already signed up?
New to KöMaL?

Problem A. 812. (December 2021)

A. 812. Two players play the following game: there are two heaps of tokens, and they take turns to pick some tokens from them. The winner of the game is the player who takes away the last token. If the number of tokens in the two heaps are \(\displaystyle A\) and \(\displaystyle B\) at a given moment, the player whose turn it is can take away a number of tokens that is a multiple of \(\displaystyle A\) or a multiple of \(\displaystyle B\) from one of the heaps.

Find those pair of integers \(\displaystyle (k,n)\), for which the second player has a winning strategy, if the initial number of tokens is \(\displaystyle k\) in the first heap and \(\displaystyle n\) in the second heap.

Proposed by Dömötör Pálvölgyi, Budapest

(7 pont)

Deadline expired on January 10, 2022.


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

Megoldás. Azt állítjuk, hogy pontosan akkor van a második játékosnak nyerő stratégiája, ha \(\displaystyle n \leq \varphi k\) és \(\displaystyle k \leq \varphi n\), ahol \(\displaystyle \varphi=\frac{\sqrt{5}+1}{2}\) az úgynevezett aranymetszés. Ismert, és könnyen ellenőrizhető, hogy \(\displaystyle \varphi^2-\varphi-1=0\), ezt az azonosságot többször fogjuk alkalmazni.

Nevezzünk egy helyzetet nyerőnek, ha onnan a kezdő játékos nyer, vesztőnek, ha a második. Egy helyzet pontosan akkor nyerő, ha onnan lehet vesztőre lépni, és akkor vesztő, ha onnan csak nyerőre lehet lépni. Világos, hogy a \(\displaystyle (0,k)\) és \(\displaystyle (k,0)\) helyzetek nyerők, és a \(\displaystyle (k,k)\) helyzet vesztő, mivel onnan csak \(\displaystyle (0,k)\)-ra vagy \(\displaystyle (k,0)\)-ra lehet lépni (\(\displaystyle k>0\)), így ezekben az esetekben tényleg igaz az állításunk. Mostantól a \(\displaystyle (k,n)\) állapotot vizsgáljuk, és feltesszük, hogy \(\displaystyle n,k>0\) és \(\displaystyle k<n\).

Először tegyük fel, hogy \(\displaystyle (k,n)\) vesztő helyzet, igazoljuk, hogy ekkor csak nyerő helyzetre lehet lépni. Azt tudjuk, hogy \(\displaystyle k<n\leq \varphi k<2k\), így ebből az állásból csak a \(\displaystyle (0,n)\), \(\displaystyle (k,0)\) és \(\displaystyle (k,n-k)\) helyzetekbe lehet lépni. Az első kettő nyerő, és a harmadik is, mivel

\(\displaystyle \varphi (n-k) \leq \varphi^2k-\varphi k=k,\)

és \(\displaystyle \varphi\) irracionális, így \(\displaystyle \varphi(n-k)<k.\)

Most tegyük fel, hogy \(\displaystyle (k,n)\) nyerő helyzet, azaz \(\displaystyle \varphi k<n\). Indirekten tegyük fel, hogy nem tudunk innen vesztő helyzetre lépni. Osszuk el \(\displaystyle n\)-t maradékosan \(\displaystyle k\)-val, legyen \(\displaystyle n=dk+r\) ahol \(\displaystyle r<k\). Ekkor a \(\displaystyle (k,r)\) párra lehet lépni, így \(\displaystyle \varphi r<k\). Továbbá a \(\displaystyle \varphi k<r+k\) egyenlőtlenség is teljesül, mivel vagy tudunk ide lépni, és akkor az indirekt feltevés miatt igaz, vagy \(\displaystyle r+k=n\), ekkor azért igaz, mert \(\displaystyle (k,n)\) nyerő helyzet. Ezt a két egyenlőtlenséget összevetve kapjuk, hogy

\(\displaystyle \varphi k<r+k<\frac{k}{\varphi}+k.\)

Átrendezve és \(\displaystyle \varphi\)-vel szorozva

\(\displaystyle k(\varphi^2-\varphi-1)<0,\)

ami ellentmondás, mivel \(\displaystyle \varphi^2-\varphi-1=0\).

Ezzel a bizonyítást befejeztük.


Statistics:

18 students sent a solution.
7 points:Bán-Szabó Áron, Ben Gillott, Diaconescu Tashi, Lovas Márton, Móra Márton Barnabás, Móricz Benjámin, Nádor Benedek, Seres-Szabó Márton, Simon László Bence, Sztranyák Gabriella, Tarján Bernát, Varga Boldizsár.
6 points:Berkó Sebestyén .
5 points:1 student.
3 points:1 student.
1 point:2 students.
0 point:1 student.

Problems in Mathematics of KöMaL, December 2021