# Brain teaser Strategic choice... [closed]

$X$ and $Y$ are playing a game. There are $11$ coins on the table and each player must pick up at least $1$ coin, but not more than $5$. The person picking up the last coin loses. $X$ starts. How many should he pick up to start to ensure a win no matter what strategy $Y$ employs?

• What do you think? Have you ever encountered a similar problem? Aug 7, 2014 at 19:29

• $X$ takes $4$

• $Y$ picks some amount: $c$

• $X$ then takes $6-c$

• $Y$ has no option but to take the last one.

If $X$ takes $4$ at the start, then there will be $7$ left.

$Y$ can then take any between $1-5$. Let $y$ be the number of coins $Y$ picks up. Then $X$ can pick up $6-y$ coins and there will be one coin left on the table, which $Y$ has to pick up. We know $X$ can pick up $6-y$ coins because $1 \leq y \leq 5$, therefore $1 \leq 6-y \leq 5$

No matter what Y needs to be left with only $1$. Since the most someone can take is $5$ and the least someone can take is $1$ then in order to win, X needs to make sure he is picking when there are between $1+1=2$ and $1+5=6$ coins left. So to do this in the least amount of steps possible, X needs to start off by taking $4$ coins. Then there will be $7$ coins left. After Y's turn, there will be guaranteed between $2$ and $6$ coins left. Then X just needs to take $5$ coins and Y will be forced to take $1$ and X wins.

You want your opponent to have exactly 1 coin on their turn, so on your turn you could have anywhere from 2 to 6 coins. In order to force your opponent to leave you with this many coins, they should have 7 coins. So if there are eleven coins you should take 4 as your first move.

A player facing $n$ coins can force a win iff there exists $1\le k \le 5$ such that a player facing $n-k$ coins cannot escape a loss.

Clearly, $n=1$ is a lost position. Therefore $n=2, 3, 4, 5, 6$ are won positions. Therefore $n=7$ is a lost position. Therefore $n=8, 9,10,11,12$ are won positions. One readily sees that this pattern continues and a position $n$ is lost if and only if $n\equiv 1\pmod 6$. Therefore $n=11$ is a won position - and the (only) winning move consists in going to the lost position $7$.

• $X$ must not reach the state of $2\dots6$ coins left on the table at $Y$'s turn

• Otherwise, $Y$ can take $1\dots5$ coins (leaving $1$ coin on the table) and win

• So $X$ should take $4$ coins off the table, and leave $7$ coins on the table

• Then, however many coins $Y$ takes, $X$ can take the remaining coins minus $1$