Nathan Karst
  • Home
  • Teaching
  • Research

Duck-duck-goose

8/9/2014

1 Comment

 
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$. 
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.$ 
1 Comment

    Archives

    June 2015
    May 2015
    February 2015
    December 2014
    October 2014
    September 2014
    August 2014
    July 2014
    May 2014
    March 2014
    February 2014
    January 2014
    December 2013
    October 2013
    July 2013
    June 2013
    May 2013
    April 2013
    March 2013
    February 2013
    January 2013

    Nathan Karst

    Doing and teaching mathematics. 

    Categories

    All

    RSS Feed

Powered by Create your own unique website with customizable templates.
Photo used under Creative Commons from ByoLogyc