Problem 4

During a break, n children sit in a circle. A teacher chooses one child and gives a candy, skips the next child and gives one to the following child, then skips 2 children, then 3, and so on. For which n will every child eventually receive at least one candy?

Step 4 of 4: Conclude the powers-of-two criterion

Previous step Next step

f\text{ is injective on }\mathbb Z/2^a\mathbb Z\Longrightarrow f\text{ is bijective}.

Detailed analysis

The comparison proves injectivity on the finite set of residues modulo 2^a, hence bijectivity. Combined with the odd-factor obstruction, the required values of n are precisely n=2^a (including n=1).