Elisa has 2023 treasure chests, all of which are unlocked and empty at first. Each day, Elisa adds a new gem to one of the unlocked chests of her choice, and afterwards, a fairy acts according to the following rules:
- if more than one chests are unlocked, it locks one of them, or
- if there is only one unlocked chest, it unlocks all the chests.
Given that this process goes on forever, prove that there is a constant with the following property: Elisa can ensure that the difference between the numbers of gems in any two chests never exceeds , regardless of how the fairy chooses the chests to lock.
Solutions — 2
Solution 1
We will prove that such a constant exists when there are chests for an odd positive integer. In fact we can take . Elisa's strategy is simple: place a gem in the chest with the fewest gems (in case there are more than one such chests, pick one arbitrarily).
For each integer , let be the numbers of gems in the chests at the end of the day. In particular, and
For each , there is a unique index for which . We know that for all , since . Elisa's strategy also guarantees that if an index is greater than the remainder of when divided by (i.e. the number of locked chests at the end of the day), then , because some chest with at most gems must still be unlocked at the end of the day.
Recall that a sequence of real numbers is said to majorise another sequence of real numbers when for all we have
and
Our strategy for proving is to inductively show that the sequence is majorised by some other sequence .
We define this other sequence as follows. Let for . As is odd, this is a strictly increasing sequence of integers, and the sum of its terms is 0. Now define for and . Thus for ,
From these properties it is easy to see that
- for all , and
- for all and , with the inequality being strict if .
Claim 1. For each , the sequence of integers majorises the sequence of integers .
Proof. We use induction on . The base case is trivial. Assume and that majorises . We want to prove the same holds for .
First note that the two sequences and both sum up to . Next, we wish to show that for , we have
When is replaced by , the above inequality holds by the induction hypothesis. For the sake of contradiction, suppose is the smallest index such that the inequality for fails. Since the left hand side increases by at most 1 during the transition from to , the inequality for can fail only if all of the following occur:
- ,
- for some (so that ),
- (so that for ).
The first point and the minimality of tell us that majorises as well (again using the induction hypothesis), and in particular .
The second point tells us that the remainder of when divided by is at most , so (by Elisa's strategy). But by the third point and the nondecreasing property of , we must have the equalities . On the other hand, , with the second inequality being strict because . We conclude that
a contradiction to the induction hypothesis.
This completes the proof as it implies
Solution 2
We solve the problem when 2023 is replaced with an arbitrary integer . We assume that Elisa uses the following strategy:
At the beginning of the day, Elisa first labels her chests as so that before she adds in the gem, the number of gems in is less than or equal for all . Then for days , she adds a gem to chest , where is chosen to be minimal such that is unlocked.
Denote by the number of gems in chest at the beginning of the day, so that
by construction. Also, denote by the total number of gems added to chest during days . We make the following observations.
- We have .
- We have , since gems are added every days.
- The sequence is a permutation of the sequence for all .
- We have for all .
- Since Elisa adds a gem to an unlocked chest with minimal, we have
for every and .
We now define another sequence of sequences of integers as follows.
We observe that
Claim 3. For each , the sequence majorises the sequence .
Proof. We induct on . For , this is clear as all the terms in the sequence are equal. For the induction step, we assume that majorises . Given , we wish to show that
Case 1: is a permutation of .
Since by the induction hypothesis, we have
Case 2: is not a permutation of .
In this case, we have for some . It follows that
Using and the induction hypothesis, we obtain
This finishes the induction step.
It follows that
From day to day , Elisa adds gems, and therefore the difference may increase by at most . This shows that the difference of the number of gems in two chests never exceeds .