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 seats, and
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
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 clockwise and the seats also numbered
so that child
is matched with seat
, and so on.
Let us denote a sequence of moves by as the sequence that the children get on the ride: for example if
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
gets onto seat
, but child
gets onto seat
(modulo
), child
gets onto seat
, and so on.
Suppose that a particular sequence works at getting every child on the ride. Then
must take on every value between 0 and
modulo
. We claim that this is possible when
is odd, and impossible when
is even.
If is odd, let
. We use sums to show that this sequence indeed works, and every child gets a different seat (by every sum being different modulo
). The sums in this case are
so the sums modulo
are
. Clearly, this covers every integer modulo
exactly once.
We claim this is impossible when is even. Suppose the contrary, that this is possible, or in other words,
take on every value between 0 and
modulo
. Adding everything up gives
But since is a permutation of
, their sum is
. Hence
Since is even, it can be written as
for some integer
. Then
This is a contridiction. Hence the arrangement is impossible when is even.