6
$\begingroup$

$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?

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

6 Answers 6

9
$\begingroup$
  • $X$ takes $4$

  • $Y$ picks some amount: $c$

  • $X$ then takes $6-c$

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

$\endgroup$
4
$\begingroup$

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$

$\endgroup$
0
4
$\begingroup$

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.

$\endgroup$
3
$\begingroup$

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.

$\endgroup$
3
$\begingroup$

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$.

$\endgroup$
1
$\begingroup$
  • $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$

$\endgroup$

Not the answer you're looking for? Browse other questions tagged .