4
$\begingroup$

this is my first question on these forums. I apologize in advance if I've overlooked a rule or done something wrong. Unfortunately, I can't remember where I came across this problem, but it's been bothering me for some time. I'd appreciate any sort of help here.

The Question:
Two people, $A$ and $B$, are playing a game. Given some number $N$, $A$ subtracts a perfect square less than or equal to $N$ from $N$. $B$ then subtracts a perfect square less than the resulting number from that number. And so on. The winner is the last person to subtract a number.
Determine all $N$ such that $A$ has a winning strategy.

An Example:
$N=13$; $A$ subtracts $1$, $B$ subtracts $9/4/1$, $A$ subtracts $1/1/9$, $B$ subtracts $1/(1 or 4)/1$, $A$ subtracts $1/(4 or 1)/1$, $B$ subtracts $-*/1/-*$, $A$ subtracts $-/1/-$, $B$ subtracts$-/-*/-$. Since $A$ can force $B$ to lose regardless of how $B$ plays, $A$ wins.

Work I've done so far:
We say a number $x$ is a winning number if $A$ has a strategy for winning when $N=x$ and is a losing number if $A$ doesn't have a strategy for winning when $N=x$. Note that if $x$ is a winning number, then there exists a perfect square $k^2$ such that $x-k^2$ is losing. Also, if $x$ is a losing number then for any $k^2$, $x-k^2$ is a winning number. The difference between any $2$ losing numbers can never be a perfect square. We also note that, if $x-L$ (where $L$ is any losing number less than $x$) isn't a perfect square, then $x$ can't be a winning number. So, using this I found a recursive means of computing some losing numbers $(0,2,5,7,10,12...)$. The losing numbers didn't seem to have a pattern, so I figured I'd try showing that there were only a finite number and then bashing through the recursion to find them all. But as it turns out there are infinitely many losing numbers. I'm at a dead end here, which probably means I'm overlooking a trick of some sort.

Research:
I did a google search of something along the lines of "game subtracting perfect squares" and didn't find anything helpful. I also checked a few of the related posts that Stack Exchange had as "Questions that may have your answer" and this one looked similar, but it wasn't particularly useful since parity doesn't seem to be very helpful in this problem. I posted this question on another math forum as well, but I haven't gotten a response.

$\endgroup$
  • $\begingroup$ Presumably you mean a nonzero perfect square. $\endgroup$ – Robert Israel Aug 3 '14 at 19:19
  • $\begingroup$ Yes, that's correct $\endgroup$ – rdj5933mile5math64 Aug 3 '14 at 19:19
  • 1
    $\begingroup$ How about if you find complete solutions for $N=1,2,3,4,5,6,7,8$ because the only nonzero squares involved are $1,4.$ Tell us how it works out. $\endgroup$ – Will Jagy Aug 3 '14 at 19:20
  • $\begingroup$ The question is resolved, but for completeness sake: 1,3=1+1+1,4,6=1+(1/4)+(4/1),8=1+(1/4)+(4/1) are winning numbers and 2=1+1,5=(1/4)+(4/1), and 7=(1/4)+(4/1)+1+1 are losing numbers $\endgroup$ – rdj5933mile5math64 Aug 3 '14 at 19:50
3
$\begingroup$

The losing numbers are OEIS sequence A030193

$\endgroup$
  • $\begingroup$ Thanks, I thought the answer would be less involved. If you don't mind me asking, how did you know that so quickly? $\endgroup$ – rdj5933mile5math64 Aug 3 '14 at 19:24
  • $\begingroup$ I entered 0,2,5,7,10,12 in the search box at oeis.org. $\endgroup$ – Robert Israel Aug 3 '14 at 19:25
  • $\begingroup$ I see, thanks again for the help :) $\endgroup$ – rdj5933mile5math64 Aug 3 '14 at 19:26

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.