Maths Olympiad Prep

Library / /322 of 520

Combinatorics Difficulty 6.7 National olympiad Find the answer

A natural number nn has the following property:
For arbitrary real numbers a1,a2,,ada_{1}, a_{2}, \ldots, a_{d}, which both satisfy 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.

A number or a short expression. Spacing and $ signs are ignored.

Solution

The smallest number nn with this property is 4025.
We first show n4025n \geq 4025. For this, we choose d=4025d=4025 and 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, 4025 subsets are required.
Now we show n4025n \leq 4025. For this, we perform a case distinction based on dd.
For d4025d \leq 4025, each aia_{i} gets its own subset. Thus, all subsets, some of which may be empty, are disjoint and have sums of at most 1.
For d>4025d>4025, there must exist two numbers axa_{x} and aya_{y} such that ax+ay1a_{x}+a_{y} \leq 1. Otherwise, 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), each parenthesis would be greater than 1, and the sum of all aia_{i} would be greater than 2013, a contradiction! Therefore, we can replace axa_{x} and aya_{y} with az=ax+aya_{z}=a_{x}+a_{y} and obtain a set with d1d-1 elements that satisfies all conditions. This step can be repeated until the replacement yields a set with 4025 elements. For this set, and thus also for the original set, the desired partition exists. This completes the proof.

Note: Some of the aia_{i} may indeed be equal; two subsets are then disjoint if they do not contain the same element (with respect to the numbering). The problem statement allowed for many solution paths.

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: NuminaMath-1.5, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.