circular table game "Suppose there are $n$ chairs around a circular table that are labelled from $0$ to $n-1$ in order. So chair $i$ is in between chairs $i-1$ and $i+1$ mod $n$. There are two infinitely smart players that play the following game. Initially Player 1 is sitting on chair $0$. The game proceeds in rounds. In each round Player 1 chooses a number $i$ from $\{1, 2, \ldots, n-1\}$, and then Player 2 chooses a direction left or right. Player 1 moves in that direction $i$ steps and sits on the corresponding chair. Player 1's goal is to sit on as many different chairs as possible while Player 2 is trying to minimize this quantity. Let $f(n)$ denote the maximum number of different chairs that Player 1 can sit on. What is $f(n)$?"
"Here are the solutions for some special cases. $f(2)=2$, $f(3)=2$, $f(4)=4$, $f(5)=4$, $f(7)=6$, $f(8)=8$, $f(p)=p-1$ for $p$ prime, $f(2^k)=2^k$"
This is a puzzle from Muthu's lecture notes on data stream algorithms. Let's assume that infinite rounds can be played. 
 A: Under the assumption that the game goes on forever, I believe that if $n$ has an odd prime factor, $f(n)=n-p^m$ where $p$ is prime and $p^m$ is the highest odd prime power such that $p^{m}$ is a proper divisor of $n$, including $1=p^0$.  If  $n=2^k$ then $f(n)=n=2^k$.  For $2^k$, player $1$ can get all the seats in $2^k$ sittings.  He starts at $0$ and on move $i$ chooses $2^{k-1-ord_2i}$ where $ord_2i$ is the highest power of $2$ dividing $i$.  If $n$ is an odd prime, player 2 can easily choose some seat to avoid.  I don't have a nice proof that player 1 can get all the rest.  Similarly, if $p^m$ divides $n$, player 2 can pick a set of evenly spaced seats and keep player 1 out of them.  Again no proof that player 1 can get all the rest, but a bit of playing has me believing it.
A: If $n$ is even we can use that $f(2k) = 2f(k)$ which can be proved by adapting the optimal strategies for players 1 and 2 for $k$ seats.
Suppose then that n is odd, and let $p$ be the smallest prime dividing $n$, so $n = kp$ for some $k$. Then it is possible to show that $f(pk) \le (p-1)k$ by showing that player 2 has a strategy whereby player 1 is allowed to visit all chairs except those which are congruent to $-1 \pmod{p}$, i.e. $p-1,2p-1,\dots kp-1$. 
In such a case where n is odd, I believe this is the best player 1 can do also however I can't quite manage it myself.
