Maths Olympiad Prep

Library / /189 of 224

Combinatorics Difficulty 6.9 National Olympiad 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 300 grams.
Find the smallest possible value of nn for which Bob always (independently of coin's weights) can partition his collection into three groups so that the total weight the coins in each of the groups is equal to 100 grams.

Solution

Answer: 201.
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

Then SjSi100S_j - S_i \doteq 100, and, on the other hand, SjSi<S100+a201=200S_j - S_i < S_{100} + a_{201} = 200. It follows that SjSi=100S_j - S_i = 100. Therefore, ai+1++aj=100a_{i+1} + \dots + a_j = 100, and the corresponding coins combine into the second group. The remaining coins combine into the third group.

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 equaled ll. Otherwise, there exists an 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 1'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 equaled 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 reproduced verbatim; metadata (topic, difficulty) added by this project.