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
26.06.2023 10:31
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\}$.
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.
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$
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$.