## 2 An \(O(n)\)-Round Strategy for [PERSON]
### When \(n\) is prime
Assuming the inductive hypothesis for \(i-1\), it follows that  
\[a_{i}=2a_{i-1}-1=2(2^{i-1}(|A|-1)+1)-1=2^{i}(|A|-1)+1.\]  
**Lemma 2**. : _Let \(n>2\) be prime, and \(A\subseteq\mathbb{Z}_{n}\), \(|A|\geq 2\). Then \(A\subseteq M(A)\subseteq M^{(2)}(A)\subseteq\cdots\subseteq M^{(\lceil\log_{2 }(n)\rceil)}(A)=\mathbb{Z}_{n}\). Note that it is possible to have \(M^{(i)}(A)=\mathbb{Z}_{n}\) for \(i<\lceil\log_{2}(n)\rceil\)._  
Proof. : The inclusions follow from the definition of the map \(M\). For \(|A|\geq 2\), we have \(2^{\lceil\log_{2}(n)\rceil}(|A|-1)+1>n\). Then by Lemma 1, \(|M^{(\lceil\log_{2}(n)\rceil)}(A)|=n\), and so \(M^{(\lceil\log_{2}(n)\rceil)}(A)=\mathbb{Z}_{n}\). **Lemma 3**. : _Let \(n>2\) be prime, and let \(A\subseteq\mathbb{Z}_{n}\), \(|A|\geq 2\). Then if \(z\in M^{(i)}(A)\setminus M^{(i-1)}(A)\) for some \(i>0\), there exist two distinct positions \(x,y\in M^{(i-1)}(A)\) such that \(z\) is equidistant from \(x\) and \(y\)._  
Proof. : Since \(z\in M^{(i)}(A)\setminus M^{(i-1)}(A)\), by definition of the map \(M\) there exist positions \(x,y\in M^{(i-1)}(A)\) such that \(z=2^{-1}(x+y)\). Thus \(z\) is equidistant from \(x\) and \(y\). Since \(z\
ot\in M^{(i-1)}(A)\), \(x\) and \(y\) are distinct. Thus, given a set of unvisited positions \(\mathbb{A}\), we are able to construct a nested sequence of sets with the desired property. While \(|\mathbb{A}|\geq 2\), Lemmas 2 and 3 guarantee that [PERSON] can move the token to an unvisited position. By repeated use of this idea until \(|\mathbb{A}|=1\), [PERSON] can visit all but one position. It remains to show that this takes at most \(2(n-1)\) rounds. **Remark 2**. : _Notice that [PERSON] controls which single position remains unvisited. We will use this fact when we give the strategy for composite table sizes in Section 2.3._  
**Theorem 4**. : _Let the table size \(n>2\) be prime. Then [PERSON] can visit \(f^{*}(n)=n-1\) positions in at most \(2(n-1)\) rounds._  
Proof. : Throughout this proof we will use \(\mathbb{A}\) to denote the remaining set of unvisited positions, and \(K\) the current position of the token. At the beginning of the game, \(|\mathbb{A}|=n-1\), since the token initially occupies a position. Let \(h=\lfloor\log_{2}(n)\rfloor\). In order to count the number of rounds required, we use the following idea. Let \(k\) be a non-negative integer. By equation 1 in Lemma 1, if \(|\mathbb{A}|\geq\left\lceil\frac{n-1}{2^{k}}\right\rceil+1\), then \(|M^{(k)}(\mathbb{A})|\geq\min\{n,2^{k}(|\mathbb{A}|-1)+1\}\) = n. It follows that \(M^{(k)}(\mathbb{A})=\mathbb{Z}_{n}\), and so [PERSON] can move the token to an unvisited position in at most \(k\) rounds. Initially, \(|\mathbb{A}|=n-1=\left\lceil\frac{n-1}{2^{0}}\right\rceil\geq\left\lceil\frac {n-1}{2^{1}}\right\rceil+1\), so \(M^{(1)}(\mathbb{A})=\mathbb{Z}_{n}\) and only one round is required to move the token to an unvisited position. [PERSON] may continue to visit unvisited positions at the cost of one round per position until \(|\mathbb{A}|<\left\lceil\frac{n-1}{2^{1}}\right\rceil+1\). Thus he visits \(\left\lceil\frac{n-1}{2^{0}}\right\rceil-\left\lceil\frac{n-1}{2^{1}}\right\rceil\) positions in \(1\times\left(\left\lceil\frac{n-1}{2^{0}}\right\rceil-\left\lceil\frac{n-1} {2^{1}}\right\rceil\right)\) rounds. Similarly, when \(\left\lceil\frac{n-1}{2^{1}}\right\rceil+1>|\mathbb{A}|\geq\left\lceil\frac{n -1}{2^{2}}\right\rceil+1\), he may visit \(\left\lceil\frac{n-1}{2^{1}}\right\rceil-\left\lceil\frac{n-1}{2^{2}}\right\rceil\) positions at the cost of at most two rounds per position, for a total of at most \(2\times\left(\left\lceil\frac{n-1}{2^{1}}\right\rceil-\left\lceil\frac{n-1} {2^{2}}\right\rceil\right)\) rounds. Eventually, \(|\mathbb{A}|=1=\left\lceil\frac{n-1}{2^{h+1}}\right\rceil<\left\lceil\frac{n -1}{2^{h+1}}\right\rceil+1\), and he must stop.