Balti Tee 2011 · Valikvooru ülesanne

Kombinatoorika

Aino and Väinö start to play the game GCD( $m, n$ ) where $m$ and $n$ are positive integers. In the beginning there are two piles of stones on the table, one with $m$ stones, another with $n$ stones. The one whose turn it is, takes away a number of stones from one of the piles. This number is a multiple of the number of stones in the other pile. Aino starts, and the players take turns until one of the piles is empty. The one who manages to empty a pile, wins. Prove that there is an $\alpha > 1$ such that if $m$ and $n$ are positive integers with $m > \alpha n$ , then Aino has a winning strategy in the game GCD( $m, n$ ), whereas if $\alpha n > m > n$ Väinö has.

Muuda valikut

Kui oled valmis

Ülevaatematerjal muutub kättesaadavaks järgmise päevaülesannete komplektiga.

Ülevaade

Teemad

Mängud ja strateegiad · Algoritmid ja protsessid · Induktsioon ja rekursioon

Lahendused

Lahendus

Choose $\alpha = (1 + \sqrt{5})/2$ , so that $\alpha^2 = \alpha + 1$ holds. We prove by induction on the sum $m+n$ that if $m > \alpha n$ , then Aino has a winning strategy in GCD( $m, n$ ), otherwise if $\alpha n \ge m > n$ , then Väinö has.

If $n \mid m$ , then Aino can remove all of the stones from the pile with $m$ stones, thus winning. This includes the initial step of the induction.
Assume $n < m \le \alpha n$ . Note that $\alpha$ is irrational, so $n < m < \alpha n$ . The rules of the game actually force Aino to remove stones from the larger pile. As $m < 2n$ , there is no choice: she has to take exactly $n$ stones. The play continues with $n$ and $m-n$ stones in the piles, Väinö having the turn. We have $0 < m-n < n$ and

\frac{n}{m-n} > \frac{n}{\alpha n - n} = \frac{1}{\alpha - 1} = \frac{\alpha^2 - \alpha}{\alpha - 1} = \alpha.

By induction, Aino has a winning strategy in the game GCD( $n, m-n$ ), but now the turns have switched. Hence, Väinö has a winning strategy that mimicks this winning strategy of Aino's.

Finally assume $m > \alpha n$ , but $n \nmid m$ . Write $\beta = m/n - \lfloor m/n \rfloor$ and $k = \lfloor m/n \rfloor$ . Then $m = kn + \beta n$ with $0 < \beta < 1$ , as $n \nmid m$ . If $1 + \beta < \alpha$ (note that $\beta \in \mathbb{Q}$ and $\alpha \notin \mathbb{Q}$ ), then $k \ge 2$ , as $m > \alpha n$ . Therefore, Aino may take $(k-1)n$ stones out of the pile of $m$ stones, leaving there $m-(k-1)n = (1+\beta)n$ stones. By induction hypothesis, Väinö has a winning strategy in the game GCD((1+\beta)n, n), which will now be copied by Aino in order to win the game. Otherwise, if $1+\beta > \alpha$ , then Aino may take $kn$ stones, leaving $\beta n$ stones in the heap. Again, Väinö's winning strategy in the game GCD( $n, \beta n$ ) is copied by Aino. It suffices to check that

\frac{1}{\beta} < \frac{1}{\alpha - 1} = \alpha.