## 2 An \(O(n)\)-Round Strategy for [PERSON]
### When \(n\) is prime  
Let \(n>2\) be prime. Since \(n\) is prime, by Theorem 1 we have that \(f^{*}(n)=\left(\frac{n-1}{n}\right)n=n-1\). We will prove that there is a strategy for [PERSON] to visit at least \(n-1\) positions in at most \(2(n-1)\) rounds. Our key idea (which coincides with the idea in [3]) behind [PERSON] strategy is as follows. Let \(K\) denote the current position of the token, and let \(\mathbb{A}\) denote the set of unvisited positions. Notice that if \(K\) is equidistant (with distance \(d\)) from two different positions in \(\mathbb{A}\), then [PERSON] can choose magnitude \(d\) and, regardless of [PERSON]'s choice, the token will move to one of those positions. We will use this fact by constructing a nested sequence of sets \(\mathbb{A}\subseteq M(\mathbb{A})\subseteq M^{(2)}(\mathbb{A})\subseteq \cdots\subseteq M^{(\lceil\log_{2}(n)\rceil)}(\mathbb{A})=\mathbb{Z}_{n}\) with the property that for \(i>0\), each position in \(M^{(i)}(\mathbb{A})\setminus M^{(i-1)}(\mathbb{A})\) is equidistant from a pair of positions in \(M^{(i-1)}(\mathbb{A})\). Then, if \(K\in M^{(i)}(\mathbb{A})\setminus M^{(i-1)}(\mathbb{A})\) for some \(i\), [PERSON] can move the token to a position in \(M^{(i-1)}(\mathbb{A})\) in one round. Since \(K\in\mathbb{Z}_{n}=M^{(\lceil\log_{2}(n)\rceil)}(\mathbb{A})\), [PERSON] can always move the token to an unvisited position in at most \(\lceil\log_{2}(n)\rceil\) rounds. This idea may be applied repeatedly, with the set of unvisited positions \(\mathbb{A}\) decreasing in size by one each time. We will show that in this manner \(n-1\) positions can be visited. We begin with some necessary standard notations and background from additive number theory. Let \(A\) and \(B\) be two subsets of \(\mathbb{Z}_{n}\). Then the _sumset_ of \(A\) and \(B\) is  
\[A+B:=\{e\in\mathbb{Z}_{n}:\text{ there exist }a\in A,b\in B\text{ such that }e\equiv a+b\pmod{n}\}\]  
and a _q-dilate_ of \(A\) is  
\[q*A:=\{e\in\mathbb{Z}_{n}:\text{ there exists }a\in A\text{ such that }e\equiv qa \pmod{n}\}.\]  
We now define a map on the family of subsets of \(\mathbb{Z}_{n}\). **Definition 1**. : _Let \(A\subseteq\mathbb{Z}_{n}\), \(|A|\geq 2\). The set of all middles between pairs of elements of \(A\) is defined by_  
\[M(A):=\{z\in\mathbb{Z}_{n}:\text{ there exist }x,y\in A\text{ such that }2z\equiv x+y \pmod{n}\}.\]  
_When \(n\) is odd, \(2^{-1}\in\mathbb{Z}_{n}\) exists and then_  
\[M(A)=\{2^{-1}(x+y)\bmod n:x,y\in A\}.\]  
_We will use the notation \(M^{(i)}(A)\) to denote the recursive application to \(A\) of the map \(M\), \(i\) times, and define \(M^{(0)}(A)=A\). For example, \(M^{(3)}(A)=M(M(M(A)))\)._  
Thus \(A\subseteq M(A)\), and for each pair of points \(x,y\in A\), all points equidistant from \(x\) and \(y\) are contained in \(M(A)\). When \(n\) is odd, there is a unique midpoint equidistant from \(x\) and \(y\). **Remark 1**. : _If \(n\) is odd, and \(A\) is the arithmetic progression \(\{a_{0}+i\delta:0\leq i\leq m-1\}\subseteq\mathbb{Z}_{n}\) for some \(a_{0},\delta\), and \(m\), then \(M(A)=\{a_{0}+i\delta 2^{-1}:0\leq i\leq 2m-2\}\) and is consequently easy to compute._  
Bellow, we use the following well known Cauchy-Davenport Theorem [8, 9]. **Theorem 3**. : _If \(p\) is a prime, and \(A,B\) are two non-empty subsets of \(\mathbb{Z}_{p}\), then_  
\[|A+B|\geq\min\{p,(|A|+|B|-1\}\]  
**Lemma 1**. : _Let \(n>2\) be prime and \(A\subseteq\mathbb{Z}_{n}\). Then for any positive integer \(i\),_  
\[|M^{(i)}(A)|\geq\min\{n,2^{i}(|A|-1)+1\}. \tag{1}\]  
Proof. : Since \(n\) is odd, \(M(A)=2^{-1}*(A+A)\) and so \(|M(A)|=|A+A|\). By Theorem 3, \(|M(A)|=|A+A|\geq\min(n,2|A|-1)=\min(n,2(|A|-1)+1)\). Thus the lemma holds for \(i=1\). Applying the above inequality recursively, we have that \(|M^{(i)}(A)|\geq\min\{n,a_{i}\}\) where \(a_{i}\) is the \(i\)-th term of the recurrence relation  
\[a_{m}=2a_{m-1}-1,\text{ for }m=1,\ldots,i;a_{0}=|A|.\]  
By induction, it is easy to prove that for any positive integer \(i\), \(a_{i}=2^{i}(|A|-1)+1\). This is trivially true for \(i=1\).