Stone removing game

For discussing Olympiad Level Combinatorics problems
rah4927
Posts:110
Joined:Sat Feb 07, 2015 9:47 pm
Stone removing game

Unread post by rah4927 » Tue Aug 02, 2016 9:56 pm

There are $N>n^2$ stones on a table. $A$ and $B$ play a game. $A$ begins, and then they alternate. In each turn a player can remove $k$ stones, where $k$ is a positive integer that is either less than $n$ or a multiple of $n$ . The player who takes the last stone wins. Prove that $A$ has a winning strategy .

User avatar
Raiyan Jamil
Posts:138
Joined:Fri Mar 29, 2013 3:49 pm

Re: Stone removing game

Unread post by Raiyan Jamil » Tue Aug 02, 2016 10:59 pm

$Case 1: N$ is a multiple of $n$.
$A$ will take all the stones and declare himself as winner.
$Case 2: N$ is not a multiple of $n$.
Since $N>n^2$ can then write $N=nk+a$ where $k≥n$ and $a≡N(mod n)$. Let $r=k-a$ i.e $k-r=a$ where $k>r>0$. So, $N=nk+(k-r)$. Now, in this case, $A$ can win this by the following steps:
$1)$ First $A$ will take $nr$ stones leaving $n(k-r)+(k-r)$ i.e. $(n+1)(k-r)$.
$2)$Then in $B's$ turn, if $B$ takes stones of multiples of $n$, say $nb$, then at that $A$ would take $b$ stones in the next step.
$3)$If $B$ takes stones less than $n$, say $x$ stones, then $A$ would take $(n+1)-x$ stones .
By these steps, we can easily see that he'll indeed be the winner at the end.
A smile is the best way to get through a tough situation, even if it's a fake smile.

rah4927
Posts:110
Joined:Sat Feb 07, 2015 9:47 pm

Re: Stone removing game

Unread post by rah4927 » Wed Aug 03, 2016 10:20 pm

Basically, this is an extended version of the problem "A and B are given $kn$ stones. At any point one can pick $1,2,...,n-1$ stones. The person to pick the last stone wins. Prove that the second person has a winning strategy.$

Post Reply