August 26–September 8, 2008

Problem

During a break, n children at school sit in a circle around their teacher to play a game. The teacher walks clockwise around the children and hands out candy to some of them according to the following procedure:

  1. Start by picking a child and give them a piece of candy
  2. Skip 1 child and give a piece of candy to the next
  3. Skip 2 children, give a piece of candy to the next
  4. Skip 3 children, give a piece of candy to the next
  5. etc.
Determine the values of n for which all children will eventually receive some candy.

Solution

This was a difficult problem; very few people had complete proofs. Here's the shortest/simplest solution I could come up with (partially due to Mike Goff).

List of solvers

Dustin Moody (graduate); Kate Smith, Steve Wilmarth, Lloyd Sakazaki, Mike Goodman (outside).

Kate Smith wins the prize!