Maths Olympiad Prep

Library / /53 of 61

Combinatorics Difficulty 7.2 National olympiad, round 2 Prove it Belarus

Bob has the collection of nn coins. Each of them weights an integer number of grams, and their total weight is equal to 300300 grams. Let k,l,mk, l, m be positive integers such that k+l+m=300k + l + m = 300.
Find the smallest possible number of nn for which Bob always (independently of coin's weights and for all possible k,l,mk, l, m) can partition his collection into three groups so that the total weight of the coins in the first, second, and third groups is equal to k,lk, l, and mm grams, respectively.

Solution

Answer: 201201.

Let a1a2ana_1 \le a_2 \le \dots \le a_n be the weights of the coins in Bob's collection. If there exists an ii such that ai101a_i \ge 101, and k=l=m=100k = l = m = 100, then, obviously, Bob cannot partition his collection into three equally weighted groups. It is easy to see that if n200n \le 200, then there can exist an ai101a_i \ge 101 (e.g., a1==an1=1a_1 = \dots = a_{n-1} = 1, an=300(n1)300200=100a_n = 300 - (n-1) \ge 300 - 200 = 100). Therefore, n201n \ge 201.

We now show that the smallest possible value of nn is 201201.

First, note that if n=201n = 201, then a1==ai=1a_1 = \dots = a_i = 1, where i102i \ge 102. Indeed, if i101i \le 101, then 2ai+1an2 \le a_{i+1} \le \dots \le a_n, and in this case a1++an1i+2(201i)=402i402101=301a_1 + \dots + a_n \ge 1 \cdot i + 2 \cdot (201 - i) = 402 - i \ge 402 - 101 = 301, contrary to the problem condition.

Without loss of generality, we suppose that klmk \le l \le m. Thus k100k \le 100. So the first kk coins combine into the first group (a1++ak=ka_1 + \dots + a_k = k).

We renumber the remaining 201k201-k weights: 1=x1=x2==xt<xt+1x201k1 = x_1 = x_2 = \dots = x_t < x_{t+1} \le \dots \le x_{201-k}. The total weight of these coins is equal to
300kx201k+(201k1t)2+t 300 - k \le x_{201-k} + (201 - k - 1 - t) \cdot 2 + t
which implies
tx201k+100k. t \ge x_{201-k} + 100 - k.
In particular, tx201kt \ge x_{201-k} since k100k \le 100.

Now we show how to form the third group with the weight equal to mm.

Consider the sums:
S1=a201k,S2=a201k+a201k1,,Si=a201k+a201k1++a201ki+1,i=1,2, S_1 = a_{201-k}, \quad S_2 = a_{201-k} + a_{201-k-1}, \quad \dots, \\ S_i = a_{201-k} + a_{201-k-1} + \dots + a_{201-k-i+1}, \quad i = 1, 2, \dots
If one of these sums is equal to mm, then the corresponding coins combine into the third group, and the remaining coins combine into the second group with the weight equal to ll. Otherwise, there exists a jj, such that Sj<mS_j < m and Sj+1>mS_{j+1} > m. In particular, Sj+1Sj2S_{j+1} - S_j \ge 2, i.e. x201kj2x_{201-k-j} \ge 2. This means that among the numbers x201kx_{201-k}, x201k1x_{201-k-1}, ..., x201kjx_{201-k-j} there are no 11's. Moreover, this means that mSj<x201kjx201ktm - S_j < x_{201-k-j} \le x_{201-k} \le t. So
x1++xmSj+x201kj+1++x201k=m, x_1 + \dots + x_{m-S_j} + x_{201-k-j+1} + \dots + x_{201-k} = m,
and the corresponding coins combine into the third group. The remaining coins combine into the second group with weight equal to ll.

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 and solution reproduced as published; topic and difficulty added by this site.