Maths Olympiad Prep

Library / /341 of 383

Combinatorics Difficulty 9.0 IMO level Prove it IMO

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 CC with the following property: Elisa can ensure that the difference between the numbers of gems in any two chests never exceeds CC, regardless of how the fairy chooses the chests to lock.

Solutions — 2

Solution 1

We will prove that such a constant CC exists when there are nn chests for nn an odd positive integer. In fact we can take C=n1C = n-1. 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 t0t \geqslant 0, let a1ta2tanta_{1}^{t} \leqslant a_{2}^{t} \leqslant \cdots \leqslant a_{n}^{t} be the numbers of gems in the nn chests at the end of the ttht^{\text{th}} day. In particular, a10==an0=0a_{1}^{0} = \cdots = a_{n}^{0} = 0 and
a1t+a2t++ant=t a_{1}^{t} + a_{2}^{t} + \cdots + a_{n}^{t} = t
For each t0t \geqslant 0, there is a unique index m=m(t)m = m(t) for which amt+1=amt+1a_{m}^{t+1} = a_{m}^{t} + 1. We know that ajt>am(t)ta_{j}^{t} > a_{m(t)}^{t} for all j>m(t)j > m(t), since am(t)t<am(t)t+1ajt+1=ajta_{m(t)}^{t} < a_{m(t)}^{t+1} \leqslant a_{j}^{t+1} = a_{j}^{t}. Elisa's strategy also guarantees that if an index jj is greater than the remainder of tt when divided by nn (i.e. the number of locked chests at the end of the ttht^{\text{th}} day), then ajtam(t)ta_{j}^{t} \geqslant a_{m(t)}^{t}, because some chest with at most ajta_{j}^{t} gems must still be unlocked at the end of the ttht^{\text{th}} day.

Recall that a sequence x1x2xnx_{1} \leqslant x_{2} \leqslant \cdots \leqslant x_{n} of real numbers is said to majorise another sequence y1y2yny_{1} \leqslant y_{2} \leqslant \cdots \leqslant y_{n} of real numbers when for all 1kn1 \leqslant k \leqslant n we have
x1+x2++xky1+y2++yk x_{1} + x_{2} + \cdots + x_{k} \leqslant y_{1} + y_{2} + \cdots + y_{k}
and
x1+x2++xn=y1+y2++yn. x_{1} + x_{2} + \cdots + x_{n} = y_{1} + y_{2} + \cdots + y_{n} .
Our strategy for proving anta1tn1a_{n}^{t} - a_{1}^{t} \leqslant n-1 is to inductively show that the sequence (ait)(a_{i}^{t}) is majorised by some other sequence (bit)\left(b_{i}^{t}\right).

We define this other sequence (bit)\left(b_{i}^{t}\right) as follows. Let bk0=kn+12b_{k}^{0} = k - \frac{n+1}{2} for 1kn1 \leqslant k \leqslant n. As nn is odd, this is a strictly increasing sequence of integers, and the sum of its terms is 0. Now define bit=bi0+tin+1b_{i}^{t} = b_{i}^{0} + \left\lfloor \frac{t-i}{n} \right\rfloor + 1 for t1t \geqslant 1 and 1in1 \leqslant i \leqslant n. Thus for t0t \geqslant 0,
bit+1={bit if t+1≢i(modn),bit+1 if t+1i(modn). b_{i}^{t+1} = \begin{cases} b_{i}^{t} & \text{ if } t+1 \not\equiv i (\bmod n), \\ b_{i}^{t} + 1 & \text{ if } t+1 \equiv i (\bmod n) . \end{cases}
From these properties it is easy to see that
- b1t+b2t++bnt=tb_{1}^{t} + b_{2}^{t} + \cdots + b_{n}^{t} = t for all t0t \geqslant 0, and
- bitbi+1tb_{i}^{t} \leqslant b_{i+1}^{t} for all t0t \geqslant 0 and 1in11 \leqslant i \leqslant n-1, with the inequality being strict if t≢i(modn)t \not\equiv i (\bmod n).

Claim 1. For each t0t \geqslant 0, the sequence of integers b1t,b2t,,bntb_{1}^{t}, b_{2}^{t}, \ldots, b_{n}^{t} majorises the sequence of integers a1t,a2t,,anta_{1}^{t}, a_{2}^{t}, \ldots, a_{n}^{t}.

Proof. We use induction on tt. The base case t=0t=0 is trivial. Assume t0t \geqslant 0 and that (bit)(b_{i}^{t}) majorises (ait)\left(a_{i}^{t}\right). We want to prove the same holds for t+1t+1.

First note that the two sequences (bit+1)\left(b_{i}^{t+1}\right) and (ait+1)\left(a_{i}^{t+1}\right) both sum up to t+1t+1. Next, we wish to show that for 1k<n1 \leqslant k < n, we have
b1t+1+b2t+1++bkt+1a1t+1+a2t+1++akt+1. b_{1}^{t+1} + b_{2}^{t+1} + \cdots + b_{k}^{t+1} \leqslant a_{1}^{t+1} + a_{2}^{t+1} + \cdots + a_{k}^{t+1} .
When t+1t+1 is replaced by tt, the above inequality holds by the induction hypothesis. For the sake of contradiction, suppose kk is the smallest index such that the inequality for t+1t+1 fails. Since the left hand side increases by at most 1 during the transition from tt to t+1t+1, the inequality for t+1t+1 can fail only if all of the following occur:
- b1t+b2t++bkt=a1t+a2t++aktb_{1}^{t} + b_{2}^{t} + \cdots + b_{k}^{t} = a_{1}^{t} + a_{2}^{t} + \cdots + a_{k}^{t},
- t+1j(modn)t+1 \equiv j (\bmod n) for some 1jk1 \leqslant j \leqslant k (so that bjt+1=bjt+1b_{j}^{t+1} = b_{j}^{t} + 1),
- m(t)>km(t) > k (so that ait+1=aita_{i}^{t+1} = a_{i}^{t} for 1ik1 \leqslant i \leqslant k).

The first point and the minimality of kk tell us that b1t,,bktb_{1}^{t}, \ldots, b_{k}^{t} majorises a1t,,akta_{1}^{t}, \ldots, a_{k}^{t} as well (again using the induction hypothesis), and in particular bktaktb_{k}^{t} \geqslant a_{k}^{t}.

The second point tells us that the remainder of tt when divided by nn is at most k1k-1, so aktam(t)ta_{k}^{t} \geqslant a_{m(t)}^{t} (by Elisa's strategy). But by the third point (m(t)k+1)(m(t) \geqslant k+1) and the nondecreasing property of aita_{i}^{t}, we must have the equalities akt=ak+1t=am(t)ta_{k}^{t} = a_{k+1}^{t} = a_{m(t)}^{t}. On the other hand, aktbkt<bk+1ta_{k}^{t} \leqslant b_{k}^{t} < b_{k+1}^{t}, with the second inequality being strict because t≢k(modn)t \not\equiv k (\bmod n). We conclude that
b1t+b2t++bk+1t>a1t+a2t++ak+1t, b_{1}^{t} + b_{2}^{t} + \cdots + b_{k+1}^{t} > a_{1}^{t} + a_{2}^{t} + \cdots + a_{k+1}^{t},
a contradiction to the induction hypothesis. \square

This completes the proof as it implies
anta1tbntb1tbn0b10=n1. a_{n}^{t} - a_{1}^{t} \leqslant b_{n}^{t} - b_{1}^{t} \leqslant b_{n}^{0} - b_{1}^{0} = n-1 .

Solution 2

We solve the problem when 2023 is replaced with an arbitrary integer nn. We assume that Elisa uses the following strategy:

At the beginning of the (nt+1)th(n t + 1)^{\text{th}} day, Elisa first labels her chests as C1t,,CntC_{1}^{t}, \ldots, C_{n}^{t} so that before she adds in the gem, the number of gems in CitC_{i}^{t} is less than or equal CjtC_{j}^{t} for all 1i<jn1 \leqslant i < j \leqslant n. Then for days nt+1,nt+2,,nt+nn t + 1, n t + 2, \ldots, n t + n, she adds a gem to chest CitC_{i}^{t}, where ii is chosen to be minimal such that CitC_{i}^{t} is unlocked.

Denote by citc_{i}^{t} the number of gems in chest CitC_{i}^{t} at the beginning of the (nt+1)th(n t + 1)^{\text{th}} day, so that
c1tc2tcnt c_{1}^{t} \leqslant c_{2}^{t} \leqslant \cdots \leqslant c_{n}^{t}
by construction. Also, denote by δit\delta_{i}^{t} the total number of gems added to chest CitC_{i}^{t} during days nt+1,,nt+nn t + 1, \ldots, n t + n. We make the following observations.
- We have c10=c20==cn0=0c_{1}^{0} = c_{2}^{0} = \cdots = c_{n}^{0} = 0.
- We have c1t++cnt=ntc_{1}^{t} + \cdots + c_{n}^{t} = n t, since nn gems are added every nn days.
- The sequence (cit+1)(c_{i}^{t+1}) is a permutation of the sequence (cit+δit)(c_{i}^{t} + \delta_{i}^{t}) for all t0t \geqslant 0.
- We have δ1t++δnt=n\delta_{1}^{t} + \cdots + \delta_{n}^{t} = n for all t0t \geqslant 0.
- Since Elisa adds a gem to an unlocked chest CitC_{i}^{t} with ii minimal, we have
δ1t+δ2t++δktk \delta_{1}^{t} + \delta_{2}^{t} + \cdots + \delta_{k}^{t} \geqslant k
for every 1kn1 \leqslant k \leqslant n and t0t \geqslant 0.

We now define another sequence of sequences of integers as follows.
di0=3n(in+12),dit=di0+t d_{i}^{0} = 3 n \left(i - \frac{n+1}{2}\right), \quad d_{i}^{t} = d_{i}^{0} + t
We observe that
d1t++dnt=c1t++cnt=nt d_{1}^{t} + \cdots + d_{n}^{t} = c_{1}^{t} + \cdots + c_{n}^{t} = n t
Claim 3. For each t0t \geqslant 0, the sequence (dit)(d_{i}^{t}) majorises the sequence (cit)(c_{i}^{t}).

Proof. We induct on tt. For t=0t=0, this is clear as all the terms in the sequence (cit)\left(c_{i}^{t}\right) are equal. For the induction step, we assume that (dit)(d_{i}^{t}) majorises (cit)(c_{i}^{t}). Given 1kn11 \leqslant k \leqslant n-1, we wish to show that
d1t+1++dkt+1c1t+1++ckt+1 d_{1}^{t+1} + \cdots + d_{k}^{t+1} \leqslant c_{1}^{t+1} + \cdots + c_{k}^{t+1}
Case 1: c1t+1,,ckt+1c_{1}^{t+1}, \ldots, c_{k}^{t+1} is a permutation of c1t+δ1t,,ckt+δktc_{1}^{t} + \delta_{1}^{t}, \ldots, c_{k}^{t} + \delta_{k}^{t}.

Since d1t++dktc1t++cktd_{1}^{t} + \cdots + d_{k}^{t} \leqslant c_{1}^{t} + \cdots + c_{k}^{t} by the induction hypothesis, we have
i=1kdit+1=k+i=1kditk+i=1kciti=1k(cit+δit)=i=1kcit+1 \sum_{i=1}^{k} d_{i}^{t+1} = k + \sum_{i=1}^{k} d_{i}^{t} \leqslant k + \sum_{i=1}^{k} c_{i}^{t} \leqslant \sum_{i=1}^{k} (c_{i}^{t} + \delta_{i}^{t}) = \sum_{i=1}^{k} c_{i}^{t+1}
Case 2: c1t+1,,ckt+1c_{1}^{t+1}, \ldots, c_{k}^{t+1} is not a permutation of c1t+δ1t,,ckt+δktc_{1}^{t} + \delta_{1}^{t}, \ldots, c_{k}^{t} + \delta_{k}^{t}.

In this case, we have cit+δit>cjt+δjtc_{i}^{t} + \delta_{i}^{t} > c_{j}^{t} + \delta_{j}^{t} for some ik<ji \leqslant k < j. It follows that
ckt+ncit+ncit+δit>cjt+δjtcjtck+1t. c_{k}^{t} + n \geqslant c_{i}^{t} + n \geqslant c_{i}^{t} + \delta_{i}^{t} > c_{j}^{t} + \delta_{j}^{t} \geqslant c_{j}^{t} \geqslant c_{k+1}^{t} .
Using dkt+3n=dk+1td_{k}^{t} + 3 n = d_{k+1}^{t} and the induction hypothesis, we obtain
i=1kcit+1i=1kcit>c1t++ck1t+12ckt+12ck+1tn2=12i=1k1cit+12i=1k+1citn212i=1k1dit+12i=1k+1ditn2=n+i=1kditk+i=1kdit=i=1kdit+1 \begin{aligned} \sum_{i=1}^{k} c_{i}^{t+1} & \geqslant \sum_{i=1}^{k} c_{i}^{t} > c_{1}^{t} + \cdots + c_{k-1}^{t} + \frac{1}{2} c_{k}^{t} + \frac{1}{2} c_{k+1}^{t} - \frac{n}{2} \\ & = \frac{1}{2} \sum_{i=1}^{k-1} c_{i}^{t} + \frac{1}{2} \sum_{i=1}^{k+1} c_{i}^{t} - \frac{n}{2} \\ & \geqslant \frac{1}{2} \sum_{i=1}^{k-1} d_{i}^{t} + \frac{1}{2} \sum_{i=1}^{k+1} d_{i}^{t} - \frac{n}{2} = n + \sum_{i=1}^{k} d_{i}^{t} \geqslant k + \sum_{i=1}^{k} d_{i}^{t} = \sum_{i=1}^{k} d_{i}^{t+1} \end{aligned}
This finishes the induction step.

It follows that
cntc1tdntd1t=3n(n1) c_{n}^{t} - c_{1}^{t} \leqslant d_{n}^{t} - d_{1}^{t} = 3 n (n-1)
From day nt+1n t + 1 to day n(t+1)+1n(t+1) + 1, Elisa adds nn gems, and therefore the difference may increase by at most nn. This shows that the difference of the number of gems in two chests never exceeds C=3n(n1)+nC = 3 n (n-1) + n.

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.