Maths Olympiad Prep

Library / /4 of 6

Combinatorics Difficulty 8.4 Shortlist Prove it Germany

A natural number nn has the following property: For arbitrary real numbers a1,a2,,ada_{1}, a_{2}, \ldots, a_{d} satisfying both a1+a2++ad=2013a_{1}+a_{2}+\ldots+a_{d}=2013 and 0ai10 \leq a_{i} \leq 1 for i=1,2,,di=1,2, \ldots, d, there exists a partition of the set of these real numbers into nn pairwise disjoint subsets (some of which may be empty), such that the sum of the numbers in each subset is at most 1. Determine the smallest number nn with this property.

Solution

The smallest number nn with this property is 40254025.

We first show n4025n \geq 4025. For this we choose d=4025d=4025 as well as a1==a4025=20134025>12a_{1}=\ldots=a_{4025}=\frac{2013}{4025}>\frac{1}{2}. Then a1++a4025=2013a_{1}+\ldots+a_{4025}=2013 and since ai+aj=40264025>1a_{i}+a_{j}=\frac{4026}{4025}>1 for all 1ij40251 \leq i \neq j \leq 4025, 40254025 subsets are needed here.

Now we show n4025n \leq 4025. For this we perform a case distinction according to dd.

For d4025d \leq 4025, each aia_{i} receives its own subset. Thus all subsets, some of which may be empty, are disjoint and have element sums of at most 11.

For d>4025d>4025, there must exist two numbers axa_{x} and aya_{y} with ax+ay1a_{x}+a_{y} \leq 1. Otherwise, already in the sum (a1+a2)+(a3+a4)++(a4025+a4026)\left(a_{1}+a_{2}\right)+\left(a_{3}+a_{4}\right)+\ldots+\left(a_{4025}+a_{4026}\right) every bracket would be greater than 11 and the sum of all aia_{i} would be greater than 20132013, contradiction! Thus we can replace axa_{x} and aya_{y} by az=ax+aya_{z}=a_{x}+a_{y} and obtain a set with d1d-1 elements satisfying all conditions. This step can be repeated until the replacement yields a set with 40254025 elements. For this set, and hence also for the original set, the desired partition exists. This proves everything.

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 translated into English from de; metadata (topic, difficulty) added by this project.