Advanced P16(BOMC 2)

[*Mahi*]

Consider the following two-person game. A number of pebbles are lying on a table. Two players make their moves alternately. A move consists in taking off the table $x$ pebbles, where $x$ is the square of any positive integer. The player who is unable to make a move loses. Prove that there are infinitely many initial situations in which the player who goes second has a winning strategy.

[*Mahi*]

We define

$P_1=$ set of numbers for which player 1 wins.
$P_2=$ set of numbers for which player 2 wins.

Hints:

$x \in P_2$ if and only if $x-a^2 \in P_1 \forall a^2 \leq x$

Try bounding on $x$, like Euclid's proof about the existence of infinitely many primes.

Desperate:

What are the possible moves for player 1 if the game starts with $n^2+2n$ pebbles?

[sourav das]

I have found a tricky solution (I think so)

Intuition:

First, I had worked with few cases and thought that taking $(mod$ $5)$ might help. But then after working in few deep it felt not so good.

Though working with cases gives me a hint!!!

Next, a simple intuition,

Contradiction.....

Structure:

If after $k$ integers only player 1(A) wins then what ? Why? (Let Player 1 and 2 are A and B)

Note that after subtracting $a^2$ from $n$ we can say that the game is similar to--A new game starting with player B with $n-a^2$!!! ....(i)

A final blow:

See (i) carefully and now ask yourself,
Can we take any special value so that $n-a^2>k$ but $n-(a+1)^2<0$(And why we want to do this???)
(I think you can )