"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.
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.