Mathcamp 2011

This year I got invited to Mathcamp, a five week summer camp for “mathematically talented high school students”. The camp will run from July 3 to August 7 this year, in Reed College in Portland, Oregon. This means I will be leaving three days from the time of writing!

The camp is quite expensive — $4000 for normal students — but thankfully, Mathcamp has given me a pretty generous scholarship.

Application to Mathcamp required, among other things, a eight question qualifying quiz. After working on them for one week, I managed to solve six of the problems and half of a seventh problem. One of my favorite problems in the quiz is the third:

In a park there is a merry go round with $n$ seats, and $n$ kids waiting to get on (the kids are evenly spaced around the merry go round). The kids climb on one by one in some order, only taking the seat in front of them and only if the seat is empty; however, each time a kid climbs on, the merry go round rotates counterclockwise by one position. For what values of $n$ is it possible for every kid to get a seat?

My solution goes as follows (I’m assuming that it’s okay to discuss solutions by now as the deadline for submitting solutions has passed more than two months ago):

Let the children be numbered $0,1,2,\cdots,n-1$ clockwise and the seats also numbered $0,1,2,\cdots,n-1$ so that child $0$ is matched with seat $0$ , and so on.

Let us denote a sequence of moves by $c_1,c_2,\cdots,c_n$ as the sequence that the children get on the ride: for example if $c_1,c_2,c_3 = 0,2,1$ then child 0 gets on, followed by child 2 then child 1. Each time a child gets on, the seats shift counterclockwise by one, so child $c_1$ gets onto seat $c_1$ , but child $c_2$ gets onto seat $c_2+1$ (modulo $n$ ), child $c_3$ gets onto seat $c_3+2$ , and so on.

Suppose that a particular sequence $c_1,\cdots,c_n$ works at getting every child on the ride. Then $c_1,c_2+1,\cdots,c_n+(n-1)$ must take on every value between 0 and $n-1$ modulo $n$ . We claim that this is possible when $n$ is odd, and impossible when $n$ is even.

If $n$ is odd, let $c_1,\cdots,c_n=0,1,2,\cdots,n-1$ . We use sums to show that this sequence indeed works, and every child gets a different seat (by every sum being different modulo $n$ ). The sums in this case are $0,2,4,\cdots,n-1,n+1,n+3,\cdots,2n-2$ so the sums modulo $n$ are $0,2,4,\cdots,n-1,1,3,5,\cdots,n-2$ . Clearly, this covers every integer modulo $n$ exactly once.

We claim this is impossible when $n$ is even. Suppose the contrary, that this is possible, or in other words, $c_1,c_2+1,\cdots,c_n+(n-1)$ take on every value between 0 and $n-1$ modulo $n$ . Adding everything up gives

$\begin{array}{l} (c_1+c_2+\cdots+c_n)+(1+2+\cdots+(n-1)) \\ \hspace{50 px} \equiv (1+2+\cdots+(n-1)) \mod n \end{array}$