Difference between revisions of "2003 IMO Problems/Problem 1"
(Typed in the problem from official pdf) |
(Added the official solution from the shortlist) |
||
(3 intermediate revisions by the same user not shown) | |||
Line 1: | Line 1: | ||
− | <math>S</math> is the set <math>\ | + | <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. |
− | \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== | ||
+ | {{IMO box|year=2003|before=|num-a=2}} | ||
+ | [[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 |