Maths Olympiad Prep

Library / /105 of 105

Number theory Difficulty 5.9 AIME, harder Prove it United States

Problem:

nn boxes initially contain 1,2,,n1, 2, \ldots, n marbles respectively (n1n \geq 1). Charlotte first adds a marble to each box. Then she adds a marble to each box in which the number of marbles is divisible by 22, then a marble to each box in which the number of marbles is divisible by 33, and so on, until she adds a marble to each box in which the number of marbles is divisible by nn. For which values of nn does the procedure end with exactly n+1n+1 marbles in every box?

Solution

Solution:

The answer is: all nn such that n+1n+1 is prime.

Lemma 1. If box AA is to the left of box BB (we can arrange the boxes so that they initially contain 1,,n1, \ldots, n marbles respectively from left to right), then at no stage of the process can box AA have more marbles than box BB.

Proof. At the outset box AA certainly has fewer marbles than box BB. Each subsequent stage adds at most one marble to each box, with one of two outcomes: (1) AA still has fewer marbles than BB; (2) AA and BB have the same number of marbles, at which point the rules force AA and BB to have the same number of marbles throughout the process. This proves the lemma.

In view of this lemma, for all the boxes to end up with n+1n+1 marbles, it is necessary and sufficient for the first box and the last box to end up with n+1n+1 marbles. The first box will certainly have n+1n+1 marbles because Charlotte adds a marble to it on every turn. The last box, which begins with nn marbles, will have n+1n+1 after the first turn. If n+1n+1 is prime, then since it is not divisible by any of the numbers 2,3,4,,n2, 3, 4, \ldots, n, the box will not pick up any more marbles and thus will end up with n+1n+1. Then the intervening boxes, being sandwiched between two boxes with n+1n+1 marbles, will also have n+1n+1 marbles.

If n+1n+1 is composite, then it is divisible by one of the numbers 2,3,4,,n2, 3, 4, \ldots, n. Hence the box will pick up another marble and will finish with at least n+2n+2 marbles.

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.