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.

-
How many rounds are played? $n-1$? – Abel Apr 19 '13 at 13:07
Why on earth would two infinitely smart people play such an annoying game? :P – Sh3ljohn Apr 19 '13 at 13:16
I don't know. In quote is the exact problem description. @Abel – Robin Apr 19 '13 at 13:19

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 $k$. If there isn't one, $n=2^k$ and $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.
{"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 1, "mathjax_display_tex": 0, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0, "katex": 0, "math-container": 0, "wp-katex-eq": 0, "align": 0, "equation": 0, "x-ck12": 0, "texerror": 0, "url": "http://math.stackexchange.com/questions/366410/circular-table-game", "fetch_time": 1469689077000000000, "content_mime_type": "text/html", "warc_filename": "crawl-data/CC-MAIN-2016-30/segments/1469257828009.82/warc/CC-MAIN-20160723071028-00009-ip-10-185-27-174.ec2.internal.warc.gz", "warc_record_offset": 162121005, "warc_record_length": 17404, "token_count": 645, "char_count": 2061, "score": 4.0, "int_score": 4, "crawl": "CC-MAIN-2016-30", "snapshot_type": "latest", "language": "en", "language_score": 0.9443622827529907, "file_path": "/sailhome/yjruan/project/latent-lm/data/processed/finemath-4plus/finemath-4plus/train-00052-of-00064.parquet"}