I made up the following problem
which was on the
Univ of MD Math Competition for HS Students Part II.
(It was question 3 of 5, indicating intermediary difficulty.)
It leads to other questions that may be open and/or interested.
I state it differently then it appeared so I can more easily
state the other questions.
Let A&sube N - {0}.
Let n&isin N.
NIM(A,n) is the following game:
There are initially n stones on the table.
Players I and II alternate removing stones from the table.
They can remove x stones iff x &isin A.
The first player who can't move loses.
Let SQ be the set of squares.
Show that there exists an infinite number of n such
that Player II wins NIM(SQ,n).
-
Most people who read this blog should be able to do this
problem. The solution is at the link above.
-
Let p &isin Z[x].
Let Ap = { p(x) : x &isin Z, p(x)>0 }
It is easy to show that there are an infinite number of n such
that player II wins NIM(Ap,n).
-
Let POW2 be the set of powers of 2.
Let A=N-POW2.
It is easy to show that there are only a finite number of n such
that player II wins NIM(A,n).
-
OPEN: classify exactly which A are such that there are an infinite number of n
such that Player II wins NIM(A,n).
(Note- it may not have a nice classification.)
For question (2) I imagine the solution is the same idea as for (1), namely that in the sequence p(x), x\in\mathbb{Z}, there must be arbitrarily large gaps. However, this only works for polynomials of degree >=2. Further, the result doesn't hold for linear polynomials (especially any of the form p(x)=x+a, integer a). Moreover, there are problems with the fact that an arbitrary polynomial might not assume the value 1, so it could be the case that neither player wins, especially if the game starts with 1 stone. I think the problem would have to be stated more carefully to explore (4).
ReplyDeleteI agree with the result in (3), but only if we take the convention that 1 is not a power of 2 (contrary to what I am used to).
I AGREE with the corrections of Michael Forbes. Thank you.
ReplyDelete