I heard of this fun little combinatorics problem from David Dralle, who (I think) heard about it from Sean Rule.
Imagine a group of $n$ people is sitting in a circle. Let's label the participants from 1 to $n$ counterclockwise. A person on the outside of the circle begins by eliminating person 1. She then skips one remaining person and eliminates the next remaining person. She repeats this process until only one person remains. For a given value of $n$, where is the last person to be eliminated sitting? Let's denote the position of this person $f(n)$.
Let's do an example to get our bearings. Here's one with $n = 8$ people. If the first person chosen is in position 1 and we number people counterclockwise, then we have $f(8) = 7$.
Imagine a group of $n$ people is sitting in a circle. Let's label the participants from 1 to $n$ counterclockwise. A person on the outside of the circle begins by eliminating person 1. She then skips one remaining person and eliminates the next remaining person. She repeats this process until only one person remains. For a given value of $n$, where is the last person to be eliminated sitting? Let's denote the position of this person $f(n)$.
Let's do an example to get our bearings. Here's one with $n = 8$ people. If the first person chosen is in position 1 and we number people counterclockwise, then we have $f(8) = 7$.
Here's another with $n = 20$ people. Here we have $f(20) = 8$.
Notice that the last remaining person is located in very different parts of the circle in the two examples.
One thing you might have noticed is during the first pass around the circle, we simply eliminate alternating people without much fuss. Once we're done with this first pass, we're left with $\lceil n/2 \rceil$ remaining people in the circle. We could also confirm that if $n$ is odd, then we begin the next revolution around the circle by skipping person 2, and if $n$ is even, we begin by eliminating person 2.
Let's continue with the $n$ even case first. There are now $n/2$ remaining people in the circle, namely those indexed 2,4,$\ldots$,n. Since all eliminated people are ignored in the choosing process, this setup is nearly identical to starting a new game of duck-duck-goose with $n/2$ people. The only difference is the indexing; the fresh game as people indexed $1,2,\ldots, n~/~2$ and the original game has participants index $2,4,\ldots,n$. If we imagine starting a fresh game with $n/2$ people and finishing with a goose at position $f(n/2)$, then the goose will have been sitting at position $2 f(n/2)$ in the original game. So for $n$ even, we have the recursive definition $f(n) = 2 f(n/2)$.
What if $n$ is odd? Here, we skip person 2 at the beginning of our second pass around the circle. Again, since eliminated participants are ignored when choosing the next person to eliminate, we can consider starting a new game with $n/2$ with participants index $1,2,\ldots,\lfloor n/2 \rfloor -1, \lfloor n/2 \rfloor$. Note that these new indices correspond to indices $4,6,\ldots,n,2$ in the original game. The conversion between new indices and old indices is $i \mapsto 2(i + 1 \bmod \lfloor n/2 \rfloor).$ So, if we finish the fresh game on a goose at position $f(\lfloor n/2 \rfloor)$, then the goose will have been sitting in position $2(f(\lfloor n/2 \rfloor) + 1 \bmod \lfloor n/2 \rfloor)$.
To see the strange floor functionality at work, consider the case of $n = 9$. We could easily verify that $f(9) = 2$. Our result claims that $f(9) = 2(f(4) + 1 \bmod 4)$. A quick execution of the algorithm shows that $f(4) = 4$, and so $f(9) = 2(4 + 1\bmod 4) = 2.$
One thing you might have noticed is during the first pass around the circle, we simply eliminate alternating people without much fuss. Once we're done with this first pass, we're left with $\lceil n/2 \rceil$ remaining people in the circle. We could also confirm that if $n$ is odd, then we begin the next revolution around the circle by skipping person 2, and if $n$ is even, we begin by eliminating person 2.
Let's continue with the $n$ even case first. There are now $n/2$ remaining people in the circle, namely those indexed 2,4,$\ldots$,n. Since all eliminated people are ignored in the choosing process, this setup is nearly identical to starting a new game of duck-duck-goose with $n/2$ people. The only difference is the indexing; the fresh game as people indexed $1,2,\ldots, n~/~2$ and the original game has participants index $2,4,\ldots,n$. If we imagine starting a fresh game with $n/2$ people and finishing with a goose at position $f(n/2)$, then the goose will have been sitting at position $2 f(n/2)$ in the original game. So for $n$ even, we have the recursive definition $f(n) = 2 f(n/2)$.
What if $n$ is odd? Here, we skip person 2 at the beginning of our second pass around the circle. Again, since eliminated participants are ignored when choosing the next person to eliminate, we can consider starting a new game with $n/2$ with participants index $1,2,\ldots,\lfloor n/2 \rfloor -1, \lfloor n/2 \rfloor$. Note that these new indices correspond to indices $4,6,\ldots,n,2$ in the original game. The conversion between new indices and old indices is $i \mapsto 2(i + 1 \bmod \lfloor n/2 \rfloor).$ So, if we finish the fresh game on a goose at position $f(\lfloor n/2 \rfloor)$, then the goose will have been sitting in position $2(f(\lfloor n/2 \rfloor) + 1 \bmod \lfloor n/2 \rfloor)$.
To see the strange floor functionality at work, consider the case of $n = 9$. We could easily verify that $f(9) = 2$. Our result claims that $f(9) = 2(f(4) + 1 \bmod 4)$. A quick execution of the algorithm shows that $f(4) = 4$, and so $f(9) = 2(4 + 1\bmod 4) = 2.$
RSS Feed
