6
$\begingroup$

There are $n$ objects on the table. Two players take turns. In one move player can take $x^2$ ($x$ is any integer, players can change it) objects. Player who can't do any move loses and the other one wins. How many $n$ are there such that the second player has a winning strategy? I think there are infinitely many $n$, but I have no idea how to prove it.

$\endgroup$
5
  • $\begingroup$ What is $x$???? $\endgroup$ May 13 '17 at 9:36
  • $\begingroup$ $x$ is any integer. $\endgroup$
    – J. Abraham
    May 13 '17 at 9:37
  • $\begingroup$ since taking $1$ is a valid move, do I understand correctlly that who takes the last object wins? $\endgroup$
    – lesath82
    May 13 '17 at 9:40
  • $\begingroup$ Yes, the one who takes the last object wins. $\endgroup$
    – J. Abraham
    May 13 '17 at 9:40
  • $\begingroup$ Incidentally, this game is very well known/studied. See en.wikipedia.org/wiki/Subtract_a_square for a lot of information going beyond the scope of this question. $\endgroup$
    – Mark S.
    May 13 '17 at 10:59
7
$\begingroup$

Define "position $k$" as a scenario where there are $k$ objects on the table at a player's turn to move.

Call position $k$ winning if a player with that position has a winning strategy (i.e., a strategy which can guarantee a win, regardless of the moves chosen by the opponent).

If a position is not winning, call it losing.

Let $W$ be the set of all winning positions, and let $L$ be the set of all losing positions.

For example, $1, 3, 4 \in W$ and $0, 2, 5 \in L$.

If the game starts in a losing position, then player $2$ has a winning strategy.

The question being asked is: How many elements does the set $L$ have?

Claim $L$ is infinite.

Suppose otherwise.

Then $L$ has a largest element, $m$, say.

Clearly we must have $m >2$ (since $5 \in L$).

Now consider the position $n = m^2-1$.

Since $n > m$, position $n$ must be winning.

It follows that for some positive integer $k < m^2$, we must have $n - k^2 \in L$.

But $n-k^2$ can't be in $L$, since

$$n - k^2 \ge n - (m-1)^2 = (m^2-1)-(m-1)^2 = 2m - 2 > m$$

Thus, we have a contradiction.

Therefore, as claimed, $L$ must be infinite.

$\endgroup$
2
  • $\begingroup$ Since $n = m^2 - 1$, the player can't subtract $m^2$. $\endgroup$
    – quasi
    May 13 '17 at 11:17
  • $\begingroup$ It was obvious... well done! $\endgroup$
    – lesath82
    May 13 '17 at 11:23
2
$\begingroup$

The game can be completely define recursively. Start at $n=1$, the first player takes that object and wins. At $n=2$, the first player has only one valid move, that is taking $1$ object, leaving the second player in a situation that has already been proven being a winning one. So first player loses. At $n=3$ the first player has at least one move (again, taking $1$ object) that sends the second player in a situation that has ben proven a losing one, so the first player wins. At higher $n$'s you go on checking whether the first player has at least one valid move to send the second player in a situation that has already been proven losing. If he doesn't have such a move, he is forced leaving the second player in a winning position so he loses.

Here is the winning table for $n$ up to $100$ (the rightmost number is one possible winning move for the first player):

enter image description here

$\endgroup$
2
  • $\begingroup$ This doesn't really address how to prove there are infinitely many losing positions. $\endgroup$
    – Mark S.
    May 13 '17 at 11:00
  • $\begingroup$ For sure. It just wanted to be a contribution to get the whole picture of the game. $\endgroup$
    – lesath82
    May 13 '17 at 11:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.