3
$\begingroup$

Consider a single-pile NIM variant, played under standard (not misere) objective, with the rule that you may remove any prime number from the pile. The winning positions of this game are all numbers $a_n$ where $a_0 = 0$ and for $A \equiv \{a_n\}$ consists of all numbers which are not of the form $p+a_k : p \text{ prime}, k<n$. (This sequence appears, to 10,000 terms, in OEIS as A025043.)

For example, 0 and 1 are winning position because there is no way to remove a prime number from such a pile; 8 is not a winning position because faced with 8 chips you can take away 7, leaving a winning position; and both 9 and 10 are winning positions.

I posted a question about the asymptotic form of the "counting number" of winning positions (that is, the number of winning positions up to $N$ as a funtion of $N$, as $N$ goes to infinity), and for a proof of whether the natural density of winning positions goes to zero.

Here, I am asking what may well be an easier question: Can you prove that there is no largest winning position?

$\endgroup$
1
  • $\begingroup$ If there is no answer in a couple of days, I will post a proof that the set of winning positions is infinite. $\endgroup$ – Mark Fischler Nov 2 '15 at 17:27
2
$\begingroup$

There is no last winning position in this game. In more generality, let $S$ be a subset of $\mathbb N$ such that there are arbitrarily long intervals in $\mathbb N$ disjoint from $S$. We will prove that, if $S$ is the set of legal amount to remove from the pile, there is no largest winning position.

Note that the set of primes satisfies this condition. To find an interval of length $\ell$ disjoint from the primes, we may use the Chinese remainder theorem to find a $k>\ell$ satisfying $k\equiv n\pmod{p_n}$ for $0\leq n \leq \ell$ where $p_n$ is $n^{th}$ prime starting with $p_0=2$. Then, the interval $[k-\ell,k]$ contains no primes, as $p_c$ divides $k-c$.

We can then prove our result by contradiction: Suppose there is no winning position greater than $a$. Our condition guarantees that there is a $k$ such that $[k-a,k]$ is disjoint from $S$. However, this means that $k$ is a winning position as all the $s\in S$ less than $k$ would be less than $k-a$. Thus, any legal move would leave more than $a$ stones in the pile, which is a losing position. As every move leads to a losing position, $k$ is a winning position.

$\endgroup$
1
  • $\begingroup$ I actually like this one better than the other correct answer; it uses absolutely nothing fancy yet is just about as brief. $\endgroup$ – Mark Fischler Jan 19 '16 at 3:45
1
$\begingroup$

Let $P$ be the set of primes, and suppose that $A$ is finite, say with maximum element $m$. If $n>m$, then $n\notin A$, so there must be a $p\in P$ such that $n-p\in A$. Thus, $A+P$ contains every integer greater than $m$, and

$$\lim_{n\to\infty}\frac{|(A+P)\cap[1,n]|}{n}=1\;.$$

However, for $n\in\Bbb Z^+$ we have

$$|(A+P)\cap[1,n]|\le |A|\pi(n)\;,$$

so

$$\frac{|(A+P)\cap[1,n]|}{n}\le|A|\frac{\pi(n)}n\sim\frac{|A|}{\ln n}\;,$$

so

$$\lim_{n\to\infty}\frac{|(A+P)\cap[1,n]|}{n}=0\;.$$

Thus, $A$ must be infinite.

$\endgroup$

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.