Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
    
How many rounds are played? $n-1$? –  Abel Apr 19 '13 at 13:07
1  
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
add comment

1 Answer

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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.