## 2 An \(O(n)\)-Round Strategy for [PERSON]
### When \(n\) is composite
#### 2.3.3 Proof of the strategy  
We will prove that [PERSON] strategy allows him to visit at least \(f^{*}(n)\) positions in at most \(3(n-1)\) rounds. First notice that [PERSON] controls whether the token ever reaches \([\gamma]_{p}\). For in Section 2.2, [PERSON] controls which position remains unvisited (Remark 2), and so here controls which class remains unvisited (on the imaginary table whose positions are classes). Furthermore, each time the token is in a class \([2^{-1}(\delta_{i}+\gamma)]_{p}\) for some \(i\), [PERSON] controls whether the token moves to \([\gamma]_{p}\). We will thus make the assumption that [PERSON] visits \([\gamma]_{p}\) if and only if he does not visit any of the leftover unvisited positions in the explored classes. This assumption is justified by [PERSON]'s primary goal to minimize the number of positions visited by [PERSON]. For if [PERSON] is allowed to visit both \([\gamma]_{p}\) and at least one leftover unvisited position in the explored classes, the total number of visited positions will be greater than \(pf^{*}(n/p)\) and since \(f^{*}(n/p)\geq\frac{(p-1)(n/p)}{p}\), the total number of visited positions will be greater than \(f^{*}(n)\). **Theorem 5**. : _Let \(n=pm\) where \(p\) is the smallest odd prime factor of \(n\). If [PERSON] does not allow for more than \(f^{*}(n)\) visited positions and therefore is consistent in his choices (as stated above), then there exists a strategy for [PERSON] to visit at least \(f^{*}(n)=\left(\frac{p-1}{p}\right)n\) positions in at most \(3(n-1)\) rounds._  
Proof. : Let \(s\) denote the number of odd prime factors of \(n\). We will prove by induction on \(s\) that [PERSON] visits at least \(f^{*}(n)\) positions in at most \(3(n-1)\) rounds. 1. \(n=2^{k}\), \(k>0\). Then by Theorem 2 [PERSON] visits \(f^{*}(n)=2^{k}\) positions in \(n-1\leq 3(n-1)\) rounds. 2. \(n=p\), \(p\) prime. Then by Theorem 4 [PERSON] visits \(f^{*}(n)=p-1\) positions in at most \(2(p-1)\leq 3(n-1)\) rounds. 3. \(n=2^{k}p\), \(k>0\), \(p\) prime. Then in the first phase [PERSON] visits all \(2^{k}\) positions in each of \(p-1\) classes. He requires at most \(2(p-1)\) rounds to visit the classes, and \(2^{k}-1\) to explore each class, for a total of at most \(2(p-1)+(p-1)(2^{k}-1)\leq 3(n-1)\) rounds. No second phase is needed. We now let \(s>1\) and assume the following inductive hypothesis: If \(n\) has \(s-1\) odd prime factors then [PERSON] can visit at least \(f^{*}(n)\) positions in at most \(3(n-1)\) rounds. Let \(n=2^{k}p_{1}p_{2}\cdots p_{s}\), where \(p_{1},p_{2},\ldots,p_{s}\) are prime and listed in increasing order. Then there are \(p_{1}\) classes, each of size \(\frac{n}{p_{1}}\). [PERSON] goal is to visit at least \(f^{*}(n)=\left(\frac{p_{1}-1}{p_{1}}\right)n\) positions, or equivalently, to leave at most \(\frac{n}{p_{1}}\) positions unvisited. In the first phase of the algorithm, [PERSON] visits \(p_{1}-1\) classes and recursively applies the algorithm to explore within each class. Then by the inductive hypothesis, he leaves at most \(\frac{n}{p_{1}}-f^{*}(\frac{n}{p_{1}})=\frac{n}{p_{1}p_{2}}\) unvisited positions in each explored class. Without loss of generality, we assume the worst case of \(\frac{n}{p_{1}p_{2}}\) unvisited positions. Furthermore, \([\gamma]_{p_{1}}\) has not been visited, so a total of \((p_{1}-1)\frac{n}{p_{1}p_{2}}+\frac{n}{p_{1}}\) positions remain unvisited. [PERSON] requires at most \(2(p_{1}-1)\) rounds to visit the \(p_{1}-1\) classes (Theorem 4 as applied in the first phase). Furthermore, by the inductive hypothesis he requires at most \(3(\frac{n}{p_{1}}-1)\) rounds to recursivelyexplore each class. So by lemma 4, at the end of the first phase, at most \(2(p_{1}-1)+3(p_{1}-1)(\frac{n}{p_{1}}-1)\) rounds have occurred. For the second phase we consider two cases. 1. [PERSON] never visits \([\gamma]_{p_{1}}\). Then in order to achieve his goal [PERSON] must visit all of the leftover unvisited positions in the \(p_{1}-1\) explored classes.