For a set \(S\) of positive integers and a positive integer \(n\), consider the game of \((n,S)\)-nim, which is as follows. A pile starts with \(n\) watermelons. Two players, Deric and Erek, alternate turns eating watermelons from the pile, with Deric going first. On any turn, the number of watermelons eaten must be an element of \(S\). The last player to move wins. Let \(f(S)\) denote the set of positive integers \(n\) for which Deric has a winning strategy in \((n,S)\)-nim. Let \(T\) be a set of positive integers. Must the sequence \[T, \; f(T), \; f(f(T)), \;\ldots\]be eventually constant? Proposed by Brandon Wang and Edward Wan
Problem
Source: ELMO 2023/6
Tags: Elmo, combinatorics
starchan
26.06.2023 10:31
Yes, for any set of positive integers $T$ the sequence $f^i(T)$ is eventually constant (here $f^i$ denotes composition of $f$ with itself $i$ times). Also, for the sake of brevity we shall abbreviate $(n, S)$-\textit{nim} with simply $(n, S)$.
First, observe that $T \subseteq f(T)$ since Deric wins for any $x \in T$ by simply removing $x$. In particular, if $\mathbb{Z}_{>0} \setminus f(T)$ is finite, we are already done. Thus we may assume that there are infinitely many positive integers not in $T$ as well.
We break into two cases:
Case 1: $1 \not \in T$
Let $m$ be the smallest element of $T$. Observe that $m > 1$. Observe that in all the games $(i, T)$ with $i < m$, Derek loses, and hence $i \not \in f(T)$ for all $i < m$. Also, since $T \subseteq f(T)$ it follows that $m \in f(T)$. An induction using this argument shows that the minimum element of each $f^i(T)$ is $m$.
Next, we show that if $a, b$ are positive integers such that $k \not \in f(T)$ for all $a \leq k \leq b$ then we have $b-a < m$. Suppose otherwise, and that $b-a \geq m$. Then $(a+m, S)$ and $(a, S)$ are both losing for Deric. But in the game $(a+m, S)$ Deric may remove $m$ watermelons, swap himself with Erek and replace the game with $(a, S)$ which means he wins as well, contradiction.
Now we claim that if $a \in T$ then $a+i \in f(T)$ for all $1 \leq i < m$. In the game $(a+i, S)$ Deric simply removes $a$ and then Erek cannot make any more valid moves. Thus each gap in $f(T)$ decreases by at least $m-1$ when we replace $T$ with $f(T)$. But since each gap is bounded by $m$ from the previous paragraph, it follows that after enough operations ($2$ suffice) $T$ becomes the set of all positive integers $\geq m$.
Let $T = \{m, m+1, \dots\}$. Observe that $f(T)$ has minimum element $m$ and is a superset of $T$, hence it is equal to $T$, which finishes the proof for this case.
Case 2: $1 \in T$
Let $n$ be the smallest positive integer not in $T$. If no such positive integer exists, $T = \mathbb{Z}_{>0}$ which is obviously a fixed point of $T$. Notice that $n > 1$ and $i \in T$ for all $i < n$. Observe that $n \not \in f(T)$ as well, since any valid move Deric may make reduces $n$ to one of $\{1, 2, \dots, n-1\}$ from where Erek can finish the game. Inductively, we observe that $n$ is not in any $f^i(T)$ as well.
We have the claim:
Claim: Let $a < b$ be two positive integers not in $f(T)$. Then $b-a \geq n$.
Proof:
Suppose otherwise and let $a, b$ be positive integers not in $f(T)$ such that $b = a+i$ for some $i < n$, in particular $i \in T$. Then Deric wins $(b, S)$ as he removes $i$ and reduces it to $(a, S)$ with Erek starting; a contradiction $\square$.
We also have the (somewhat obvious) claim:
Claim: Let $a, b$ be two positive integers such that $a \in T$ and $b \not \in f(T)$. Then $a+b \in f(T)$.
Proof: Consider the game $(a+b, S)$. Deric simply reduces $a+b$ by $a$ and wins. $\square$
From the first claim, observe that if $kn \not \in f(T)$ for some positive integer $k$ then $kn+i \not \in f(T)$ for all $1 \leq i < n$. Thus if the numbers $n, 2n, \dots, kn \not \in f(T)$ for some positive integer $k \geqslant 1$ then all numbers $r < (k+1)n$ are in $f(T)$ if and only if $r \not \equiv 0 \pmod n$. In particular, if there is no multiple of $n$ in $T$ we can make $k$ arbitrarily large and $f(T)$ becomes exactly the set of non multiples of $n$. Observe that if this were the case, then $f(f(T)) = f(T)$ since $f(T) \subseteq f(f(T))$ and a multiple of $n$ can never be winning for Deric, since any reduction by a non multiple leads to another non multiple.
Thus we may assume that there is some minimal $k > 1$ such that $kn \in f(T)$. Observe that $f(T)$ looks like: \[\{1, 2, \dots, n-1, n+1, n+2, \dots, 2n-1, \dots, (k-1)n+1, \dots, kn-1, kn, \dots \} \qquad (1)\]First, we prove that $in \not \in f^j(T)$ for any $1 \leq i < k$ and positive integer $j$ by inducting on $j$. It's clear for $j = 1$. Let's assume $j > 1$. Consider the game $(in, f^{j-1}(T))$ for some $1 \leq i < k$. Deric can only reduce $in$ by any number not divisible by $n$ due to the inductive hypotheses, but when he does so, Erek simply removes all watermelons since the new number of watermelons is no longer divisible by $n$.
Thus the structure we see in $(1)$ is fixed for all $f^j(T)$. In particular, using Claim 2, we deduce that if $a \in f^i(T)$ for some $i$ then $a+n \in f^{i+1}(T)$.
Let $M$ be any positive integer $> kn$. We claim that $M \in f^{k+3}(T)$. If $M$ already in $f^i(T)$ for some $i \leq k+2$ we are already done, so assume that $M \not \in f^{k+2}(T)$. In particular, this implies that $M-n \not \in f^{k+1}(T)$ from the last line in the above paragraph. Repeating this $k$ times we obtain that $M-kn \not \in f^2(T)$. But since $kn \in f(T)$ and $M-kn \not \in f^2(T)$ Claim 2 implies that $kn+M-kn = M \in f^2(T)$, a contradiction. Hence $M \in f^{k+3}(T)$, as desired.
The above discussion implies that $f^{k+3}(T) = \mathbb{Z}_{> 0} \setminus \{n, 2n, \dots, (k-1)n\}$. But since $n, 2n, \dots, (k-1)n$ never show up in any $f^j(T)$ it follows that $f^{k+3}(T) = f^{k+4}(T)$ and we have settled the problem for this case as well.
Combining the two cases, we have solved the problem.
CANBANKAN
27.06.2023 05:08
The answer is yes. Replace Deric and Erek with FIRST and SECOND. This solution focuses exclusively on small elements. If $T = \mathbb{N}$ I am trivially done. Otherwise, let $s$ be the smallest number in $\mathbb{N}\backslash T$. Clearly $T \subset f(T) \subset f^2(T) \cdots$ \begin{lemma} [6.1] $\mathbb{N} \backslash \cup_{n\ge 1} f^n(T)$ is either $s\mathbb{N}$ or $\{s, \cdots, ms\}$ for some $m \in \mathbb{N}$. \end{lemma} \begin{proof} [of 6.1] Note if $x\in f^n(T)$ then $x+s \in f^{n+1}(T)$ because FIRST can go from $x+s$ to $s$ in the game with $f^n(T)$. Therefore, we can see that if $r<s$ then $r+ks \in f^k(T)$ and all non-multiples of $s$ are in $\cup_{n\ge 1} f^n(T)$, and if $ks \in \cup_{n\ge 1} f^n(T)$ then $(k+1)s \in \cup_{n\ge 1} f^n(T)$ as well. \end{proof} If $\mathbb{N} \backslash \cup_{n\ge 1} f^n(T)=s\mathbb{N}$, then we can show that no multiple of $s$ can be in $T$, and via induction we can prove that $f(T) = \mathbb{N} \setminus s\mathbb{N}$. Thus it suffices to resolve the case where $\cup_{n\ge 1} f^n(T) = \mathbb{N} \backslash \{s,\cdots,ms\}$ We can prove that $s,\cdots,ms$ are not in $T$ but $(m+1)s\in T$. Let $$\{s,\cdots,ms=t_0 < t_1 < \cdots \} = \mathbb{N} \backslash f(T)$$ Observe that for all $j$, $t_j-t_{j-1}\ge s$, or otherwise, since $t_{j-1}$ is losing for FIRST, from $t_j$, FIRST can subtract $t_j - t_{j-1} \in \{1,\cdots,s-1\} \subset S \subset f(T)$ to win, so $t_j\in f(T)$ Also, observe that if $t_j - t_{j-1} > s$ then $t_j \in f^2(T)$. This is true because I can go from $t_j$ to $s$ by subtracting $t_j-s \in (t_{j-1}, t_j)$, so $t_j-s \in f(T)$ Let $A = \{ j \mid t_j-t_{j-1}=s\}, B = \mathbb{N} \backslash A$. Observe that $A$ doesn't contain $m+1$ consecutive integers. Assume FTSOC it contains $j+1, \cdots, j+m+1$. Then $t_{j+m+1} - t_j = (m+1)s$, which is absurd since $t_j$ is losing and so from $t_{j+m+1}$ FIRST can subtract $(m+1)s\in T$ to win. Let $j,j+l$ be adjacent elements in $B$ i.e. $\{j+1,\cdots,j+l-1\} \cap B = \emptyset$. Now note that $j \in B \to t_j \in f^2(S) \to t_{j+1} \in f^3(S) \to \cdots \to t_{j+l-1} \in f^l(S)$. Furthermore $1 \in B$. This implies that $t_k \in f^{m+1}(S)$ for all $k$, so $f^{m+1}(S) = \mathbb{N} \backslash \{s,\cdots,ms\}$.
TheUltimate123
01.07.2023 00:58
Yes, the sequence must be eventually constant. In what follows, let \(\overline S=\mathbb Z_{\ge0}\setminus S\), so \(f(S)=S+\overline{f(S)}\) for all \(S\). Note that \(S\subseteq f(S)\) always, so the limit \(f^\infty(T)\) is well-defined. Claim: Let \(m\) be the smallest positive integer in \(\overline T\). If all multiples of \(m\) are in \(\overline{f^\infty(T)}\), then \(f(T)=f^\infty(T)\). Proof. Since \(T\subseteq f^\infty(T)\), this means all multiples of \(m\) are in \(\overline T\). However, 1, 2, \ldots, \(m-1\) are in \(T\). We may then compute that \(f(T)\) is exactly the set of non-multiples of \(m\), implying \(f(T)=f^\infty(T)\). \(\blacksquare\) Claim: If there are \(a\) and \(b\) with \(a,b\in\overline{f^\infty(T)}\) but \(a+b\in f^\infty(T)\), then \(f^{j+3}(T)=f^\infty(T)\) for some \(j\) (defined below). Proof. We take \(j\) as the index for which \(n\in f^j(T)\iff n\in f^\infty(T)\) for \(n\le a+b\) (which must exist since \(S\subseteq f(S)\) always). For \(n>a+b\), note: If \(n-a-b\notin f^{j+1}(T)\) then \(n=(a+b)+(n-a-b)\in f^{j+1}(T)\). If \(n-a-b\in f^{j+1}(T)\), then \(n-b=(n-a-b)+a\in f^{j+2}(T)\) so \((n-b)+b\in f^{j+3}(T)\). Thus all \(n>a+b\) are in \(f^{j+3}(T)\subseteq f^\infty(T)\), implying \(f^{j+3}(T)=f^\infty(T)\). \(\blacksquare\) If \(\overline T=\{0\}\) then we are already done. Otherwise \(m\) exists, we may check that \(m\in\overline{f^\infty(T)}\). Then: If all multiples of \(m\) are in \(\overline{f^\infty(T)}\), then Claim 1 finishes. Otherwise, let \(\ell m\) be the smallest multiple of \(m\) not in \(\overline{f^\infty(T)}\). Taking \(a=m\) and \(b=(\ell-1)m\) in Claim 2 finishes. This completes the proof. Remark: If all multiples of \(m\) are in \(\overline{f^\infty(T)}\), then Claim 1 establishes that \(f(T)=f^2(T)\). Otherwise, the argument in Claim 1 restricted to \([1,\ell m]\) shows that \(f(T)\cap[1,\ell m]=f^\infty(T)\cap[1,\ell m]\), i.e.\ we may take \(j=1\) in Claim 2. This establishes that \(f^4(T)=f^5(T)\) for all \(T\). Remark: It has been claimed by Colin Tang (independently), Justin Lee, and Espen Slettnes that \(f^3(T)=f^4(T)\) for all \(T\), but I have yet to review a proof of this claim.
IAmTheHazard
11.10.2023 20:48
Revenge?? Not really since I only got 5 minutes to spend in contest after nearly dying on p4. Did not feel all too difficult, fairly natural to see what's going on imo The answer is yes. Throughout the solution we use "in $(n,S)$" in the place of "in a game of $(n,S)$-nim", and let $S'$ denote the complement of a set $S$ (with respect to $\mathbb{Z}^+$). Obviously, $T \subseteq f(T)$. We consider two cases. Case 1: $1 \not \in T$. Let $m$ be the smallest element of $T$. By induction, $m$ is clearly the smallest element of $f^i(T)$ for any $i$. Furthermore, for any $a$ at least one of $a$ and $a+m$ is in $f(T)$, since if $(a,T)$ is losing then Deric can eat $m$ watermelons in $(a+m,T)$ and win. Now for any $k \in f(T)$, I claim that we have $k+i \in f(f(T))$ for all $1 \leq i<m$. Indeed, in $(k+i,f(T))$ Deric can start by eating $k$ watermelons, leaving Erek with too few watermelons to do anything with. Since consecutive blocks in $f(T)'$ only have lengths at most $m$, it follows that (aside from $1,\ldots,m-1$) they die after two more iterations of $f$, i.e. $f^3(T)=\{m,m+1,\ldots\}$, whence $f^4(T)=f^3(T)$. Case 2: $1 \in T$. In this case let $m$ be the smallest positive integer not in $T$. I claim that $f(T)'$ doesn't contain any elements with absolute difference less than $m$. Indeed if $(a,T)$ is losing then Deric can eat $i$ watermelons in $(a+i,T)$ and win for all $1 \leq i<m$. Therefore if $f(T)'$ contains every multiple of $m$, it cannot contain anything else, and in this case it is clear that $f^2(T)=f(T)$. Thus suppose otherwise, and let $k>1$ be minimal such that $km \in f(T)$, so for all $1 \leq i<m$ we have $im \in f(T)'$ and all other numbers smaller than $km$ are in $f(T)$. Since larger values don't matter, by induction it in fact follows that this is true with $f(T)$ replaced by $f^i(T)$ for any positive integer $i$. For a set $S$ of positive integers, let a brick be a subset of the form $\{c,c+m,\ldots,c+dm\}$ such that $c-m$ and $c+(d+1)m$ aren't in $S$, or a subset of the form $\{c,c+m,\ldots\}$; hence bricks are "maximal". Then bricks in $f^2(T)$ have size at most $k$, since if $(a,f(T))$ is losing then $(a+km,f(T))$ is winning since Deric can start by eating $km$ watermelons. Furthermore, the smallest element of each brick aside from $\{m,2m,\ldots,(k-1)m\}$ is more than $km$. Now, since $m \in f^i(T)$ for all $i$, the least element of every brick in $f^i(T)'$ (aside from the one containing $m$) is removed when going to $f^{i+1}(T)'$. Indeed, if $c$ is this minimal element, we have $c-m \in f^i(T)$ (since it's a positive integer), so in $(c,f^i(T))$ Deric can eat $c-m$ watermelons and win since $(m,f^i(T))$ is always losing, hence $c \not \in f^{i+1}(T)$. It thus follows that all the bricks other than $\{m,2m,\ldots,(k-1)m\}$ die by the time we get to $f^{k+2}(T)$. That is, $f^{k+2}(T)'=\{m,2m,\ldots,(k-1)m\}$, whence $f^{k+2}(T)=f^{k+3}(T)$ since the elements of $f^{k+2}(T)'$ are never in $f^i(T)$. Combining these cases solves the problem. $\blacksquare$
CT17
17.10.2023 22:08
If $T=\mathbb{N}$ we are done. Otherwise, let $m\in\mathbb{N}$ be minimal such that $m\not\in T$. We have two cases. Case 1: there exists a minimal $k$ such that $km\in T$. Then $x\in f(T)$ or $x+km\in f(T)$ for every $x$. Additionally, since $m$ will always be losing, we have $x\in f^r(T)\implies x+m\in f^{r+1}(T)$ for any $x,r$. The former fact implies that there are never more than $k$ consecutive numbers not in $f(T)$ in any residue class mod $m$, and then the latter implies that $f^{k+1}(T) = \mathbb{N}\setminus \{m, 2m, \cdots, (k-1)m\}$, at which point the sequence becomes constant. Case 2: $km\not\in T$ for all $k$. Then $f(T)$ is just $\mathbb{N}\setminus m\mathbb{N}$ by induction: suppose $f(T)$ up to $km$ consists of exactly the non-multiples of $m$, then $km+r$ is winning by subtracting $r$ for $1\le r\le m-1$ and $(k+1)m$ is losing since all losing positions before it are multiples of $m$.