Maths Olympiad Prep

Library / Belarusian Mathematical Olympiad /177 of 208

Belarusian Mathematical Olympiad

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 a1≤a2≤⋯≤ana_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 ai≥101a_i \ge 101, and k=l=m=100k = l = m = 100, then obviously Bob

Then Sj−Si≐100S_j - S_i \doteq 100, and, on the other hand, Sj−Si<S100+a201=200S_j - S_i < S_{100} + a_{201} = 200. It follows that Sj−Si=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+1−Sj≥2S_{j+1} - S_j \ge 2, i. e. x201−k−j≥2x_{201-k-j} \ge 2. This means that among the numbers x201−kx_{201-k}, x201−k−1x_{201-k-1}, ..., x201−k−jx_{201-k-j} there are no 1's. Moreover, this means that m−Sj<x201−k−j≤x201−k≤tm - S_j < x_{201-k-j} \le x_{201-k} \le t. So
x1+⋯+xm−sj+x201−k−j+1+⋯+x201−k=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,604 problems in a working order, from Junior Challenge level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.