Let $(a,b)$ be a pair of natural numbers. Henning and Paul play the following game. At the beginning there are two piles of $a$ and $b$ coins respectively. We say that $(a,b)$ is the starting position of the game. Henning and Paul play with the following rules: $\bullet$ They take turns alternatively where Henning begins. $\bullet$ In every step each player either takes a positive integer number of coins from one of the two piles or takes same natural number of coins from both piles. $\bullet$ The player how take the last coin wins. Let $A$ be the set of all positive integers like $a$ for which there exists a positive integer $b<a$ such that Paul has a wining strategy for the starting position $(a,b)$. Order the elements of $A$ to construct a sequence $a_1<a_2<a_3<\dots$ $(a)$ Prove that $A$ has infinity many elements. $(b)$ Prove that the sequence defined by $m_k:=a_{k+1}-a_{k}$ will never become periodic. (This means the sequence $m_{k_0+k}$ will not be periodic for any choice of $k_0$)
Problem
Source: Swiss TST 2019 P6
Tags: combinatorics, game, winning strategy
13.03.2021 05:35
Bump any idea /
13.03.2021 07:59
HINT: Consider differences and induction to prove (1,2)(3,5)(4,7)(6,10)(8,13) etc are the ONLY winning positions. So for constructing a winning position, take 1, add 1 then take the next unused number, add 2, and so on.
14.03.2021 05:14
gabrupro wrote: SPOILER ALERT!!!!! Skip this post if you don’t want the hint: . . . . . Consider differences and induction to prove (1,2)(3,5)(4,7)(6,10)(8,13) etc are the ONLY winning positions. So for constructing a winning position, take 1, add 1 then take the next unused number, add 2, and so on. Can you write it more nicely?
15.03.2021 07:56
Apparently, this game was known over 100 years ago. See this : Wythoff's game