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 3 of 4: Compare two triangular numbers

Previous step Next step

f(x)-f(y)=\frac{(x-y)(x+y+1)}2.

Detailed analysis

Assume n=2^a and f(x)=f(y) modulo n. Then $2^{a+1}$ divides (x-y)(x+y+1). If x and y have the same parity, the second factor is odd, so x=y modulo $2^{a+1}$ ; if they have different parity, x-y is odd and the second factor is strictly between 0 and $2^{a+1}$ , so it cannot be divisible by $2^{a+1}$ .