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}

But since c_1,c_2,\cdots,c_n is a permutation of 0,\cdots,n-1, their sum is \frac{n(n-1)}{2}. Hence

\frac{n(n-1)}{2} \equiv 0 \mod n

Since n is even, it can be written as 2m for some integer m. Then

\begin{array}{cc} m(2m-1) & \equiv 0 \mod 2m\\ 2m^2-m & \equiv 0 \mod 2m\\ m & \equiv 0 \mod 2m \end{array}

This is a contridiction. Hence the arrangement is impossible when n is even.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s