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.