Chapter 1: The Candy Dilemma

Picture this: I find myself seated in a circle with nine classmates, placing me in the second position. As the teacher strolls around the circle, she hands a candy to the first student, skips me, and then gives one to the third student. Continuing this pattern, she bypasses two students before reaching the sixth one…

The teacher maintains this approach, skipping one additional student each time before bestowing a candy on the next. After several rounds, I begin to feel quite despondent, wondering if I’ll ever receive a candy! 😭

My inquiry for you is…

…if the teacher persists indefinitely, will I ultimately receive a candy?

Understanding the Problem

This intriguing problem first surfaced in a similar format during the 2017 Oxford University Mathematics Admissions Test. I encountered it through an episode of Alaric Stephen's Odds and Evenings podcast. Even further back, it appears to be inspired by a comparable question from the 1991 Asia Pacific Mathematical Olympiad, which more broadly examines a circle of n students.

Start by tackling the challenge with 10 students. Will the forlorn student in position 2 ever get a candy? If you solve this, consider attempting the general case discussed in the linked APMO problem.

Video Insight: The Giant Circle Challenge

To deepen your understanding, check out this video that explores the Giant Circle Challenge and inscribed angles.

Solution to the 10-Student Puzzle

Regrettably, student 2 will not receive a candy. Here’s one way to demonstrate why.

The teacher skips 1, 2, 3, and so on. If we had an infinite line of students, the n-th candy would go to the (1 + 2 + 3 + … + n)-th student. Since the 10 students are arranged in a circle, we apply modulo n (taking the remainder after dividing by 10).

You may recall that the sum (1 + 2 + 3 + … + n) corresponds to the n-th triangular number Tₙ = n(n+1)/2.

For those unfamiliar with this formula, it can be derived by pairing terms. If you were to approach this problem, you might create a list identifying which students receive a candy.

The first 10 triangular numbers are:

{1, 3, 6, 10, 15, 21, 28, 36, 45, 55}.

When calculating these modulo 10, we get:

{1, 3, 6, 0, 5, 1, 8, 6, 5, 5}.

It’s straightforward to compute the next 10 triangular numbers modulo 10 by focusing solely on the last digit:

{6, 8, 1, 5, 0, 6, 3, 1, 0, 0}.

What’s next?

After completing two full cycles of 10, we would simply repeat the addition of 1, 2, 3, etc. Since we start from a 0 (the 10th student in the circle), this sequence continues indefinitely in cycles of 20.

Unfortunately, student 2 misses out (as do students 4, 7, and 9).

General Case (n Students)

How can we extend the findings from the 10-student scenario to determine which values of n ensure that all students receive a candy?

Referring to the repeating cycle of length 20 identified earlier, we find that the n-th triangular number is Tₙ = n(n+1)/2. The (2n)-th triangular number, (2n)(2n+1)/2 = n(n+1), is always a multiple of n. Hence, the (2n)-th candy will consistently go to the n-th (last) student in the circle. Adding (2n+1) for the subsequent triangular number is akin to adding 1 modulo n, ensuring the cycle repeats after 2n candies.

That's a reason to celebrate! 👊

Special Case: Odd Values of n

For odd n, (n+1) becomes even, meaning the n-th triangular number Tₙ = n(n+1)/2 must also be a multiple of n. Consequently, the cycle will repeat after n candies.

Let’s consider the scenario where n is odd. The only way for all students to receive a candy is if each student gets precisely one candy. However, as we established, the cycle repeats after n candies, leading to the conclusion that at least one student will get two candies.

Take the first student, for instance, who consistently receives the initial candy. We need to find a second solution to the equation k(k+1)/2 ≡ 1 mod n. Substituting k ≡ −2 mod n shows that the first student will always receive (at least) two candies, resulting in at least one student missing out.

Considering Even Values of n

Now, let’s examine what occurs when n is even.

As previously demonstrated, the pattern consistently repeats in cycles of 2n. Applying a symmetry argument similar to the one used for odd n can help clarify this situation.

The (n − 2)-th candy should go to the same student as the first candy. However, this assumption may not hold true, as illustrated when n = 10, where the 8-th candy is given to the student in position 6 modulo 10.

Despite this, we can maintain the symmetry argument by multiplying the modulo equation by 2:

(−2)(−1)/2 ≡ (1)(2)/2 mod n.

This allows us to assert that the (2n − 2)-th candy will indeed go to the same student as the first candy.

This symmetry continues until we reach the (2n − (n+1))'th = (n − 1)'th candy, which will also go to the n-th student. Thus, although the cycle takes 2n candies to repeat, the first (n − 1) candies must be distributed to the first (n − 1) students in some order.

Video Insight: The Mystery Theorem

For further exploration of these mathematical concepts, check out this enlightening video on the Mystery Theorem, which delves into the quadrant and semicircle.

Proof: Everyone Gets Candy if n is a Power of 2

If every student receives a candy, then the first (n − 1) candies must be given to different students. This leads to the conclusion that the first (n − 1) triangular numbers must be unique modulo n.

This uniqueness is equivalent to stating that the equation k(k+1)/2 ≡ m(m+1)/2 mod n only has one solution when k ≡ m mod n. By multiplying through by 2, we derive:

k(k+1) ≡ m(m+1) mod (2n).

Factorizing gives us:

k² + k − m² − m ≡ 0 mod (2n).

Consequently, if n is a power of 2, the equation can only have the solution k ≡ m mod n, ensuring that all students receive a candy!

Conclusion

This candy circle puzzle not only challenges our understanding of number theory but also provides a fascinating insight into mathematical cycles and distributions. It invites further exploration and discussion, making it a captivating topic for students and educators alike.

Source: Pixabay