Difference between revisions of "2003 IMO Problems/Problem 1"
m (Added see also box and a category) |
(Added the official solution from the shortlist) |
||
Line 1: | Line 1: | ||
<math>S</math> is the set <math>\{1, 2, 3, \dots ,1000000\}</math>. Show that for any subset <math>A</math> of <math>S</math> with <math>101</math> elements we can find <math>100</math> distinct elements <math>x_i</math> of <math>S</math>, such that the sets <math>\{a + x_i \mid a \in A\}</math> are all pairwise disjoint. | <math>S</math> is the set <math>\{1, 2, 3, \dots ,1000000\}</math>. Show that for any subset <math>A</math> of <math>S</math> with <math>101</math> elements we can find <math>100</math> distinct elements <math>x_i</math> of <math>S</math>, such that the sets <math>\{a + x_i \mid a \in A\}</math> are all pairwise disjoint. | ||
+ | ==Solution== | ||
+ | |||
+ | Consider the set <math>D=\{x-y \mid x,y \in A\}</math>. There are at most <math>101 \times 100 + 1 = | ||
+ | 10101</math> elements in <math>D</math>. Two sets <math>A + t_i</math> and <math>A + t_j</math> have nonempty intersection if and only if | ||
+ | <math>t_i - t_j</math> | ||
+ | is in <math>D</math>. So we need to choose the <math>100</math> elements in such a way that we do not use a | ||
+ | difference from <math>D</math>. | ||
+ | Now select these elements by induction. Choose one element arbitrarily. Assume that | ||
+ | <math>k</math> elements, <math>k \leq 99</math>, are already chosen. An element <math>x</math> that is already chosen prevents us | ||
+ | from selecting any element from the set <math>x + D</math>. Thus after <math>k</math> elements are chosen, at most | ||
+ | <math>10101k \leq 999999</math> elements are forbidden. Hence we can select one more element. | ||
==See Also== | ==See Also== | ||
{{IMO box|year=2003|before=|num-a=2}} | {{IMO box|year=2003|before=|num-a=2}} | ||
[[Category:Olympiad Combinatorics Problems]] | [[Category:Olympiad Combinatorics Problems]] |
Latest revision as of 16:09, 24 November 2019
is the set . Show that for any subset of with elements we can find distinct elements of , such that the sets are all pairwise disjoint.
Solution
Consider the set . There are at most elements in . Two sets and have nonempty intersection if and only if is in . So we need to choose the elements in such a way that we do not use a difference from . Now select these elements by induction. Choose one element arbitrarily. Assume that elements, , are already chosen. An element that is already chosen prevents us from selecting any element from the set . Thus after elements are chosen, at most elements are forbidden. Hence we can select one more element.
See Also
2003 IMO (Problems) • Resources | ||
Preceded by ' |
1 • 2 • 3 • 4 • 5 • 6 | Followed by Problem 2 |
All IMO Problems and Solutions |