Library / /26 of 27

, 2015

Number theory Difficulty 6.5 National Olympiad Prove it Singapore

There are 30 children, $a_1, a_2, \dots, a_{30}$ , seated clockwise in a circle on the floor. The teacher walks behind the children in the clockwise direction with a box of 1000 candies. She drops a candy behind the first child $a_1$ . She then skips one child and drops a candy behind the third child, $a_3$ . Now she skips two children and drops a candy behind the next child, $a_6$ . She continues this way, at each stage skipping one child more than at the preceding stage before dropping a candy behind the next child. How many children will never receive a candy? Justify your answer.

Solution

When the $k^{\text{th}}$ candy is dropped, the teacher has skipped $1+2+\dots+(k-1) = \dfrac{k(k-1)}{2}$ children. Then it is dropped behind $a_i$ , where $i = k + \dfrac{k(k-1)}{2} = \dfrac{k(k+1)}{2}$ (mod 30). Thus $2i = k(k+1)$ (mod 60). From here it is clear that the $i^{\text{th}}$ and $j^{\text{th}}$ candies are given to the same child if $i \equiv j$ (mod 60). Thus the sequence of children receiving candies is periodic with period 60. Note that $k(k+1) \equiv (60-k-1)(60-k) \pmod{60}$ . Thus the $k^{\text{th}}$ and $(60-k-1)^{\text{th}}$ are given to the same child. Thus we only need to compute $\dfrac{k(k+1)}{2}$ (mod 30) for $k = 1, \dots, 29$ . This yields the following sequence of children receiving the first 29 candies. Thus 18 children never receive any candy.

1, 3, 6, 10, 15, 21, 28, 6, 15, 25, 6, 18, 1, 15, 30
16, 3, 21, 10, 30, 21, 13, 6, 30, 25, 21, 18, 16, 15

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.