Difference between revisions of "1972 IMO Problems/Problem 1"
Mathwiz0803 (talk | contribs) |
Ehuang0531 (talk | contribs) (technicality - assuming A and B must be nonempty) |
||
(5 intermediate revisions by 4 users not shown) | |||
Line 2: | Line 2: | ||
Prove that from a set of ten distinct two-digit numbers (in the decimal system), it is possible to select two disjoint subsets whose members have the same sum. | Prove that from a set of ten distinct two-digit numbers (in the decimal system), it is possible to select two disjoint subsets whose members have the same sum. | ||
− | |||
==Solution== | ==Solution== | ||
− | + | There are <math>2^{10}-2=1022</math> distinct subsets of our set of 10 two-digit numbers. The sum of the elements of any subset of our set of 10 two-digit numbers must be between <math>10</math> and <math>90+91+92+93+94+95+96+97+98+99 < 10 \cdot 100 = 1000</math>. (There are fewer attainable sums.) As <math>1000 < 1022</math>, the [[Pigeonhole Principle]] implies there are two distinct subsets whose members have the same sum. Let these sets be <math>A</math> and <math>B</math>. Now, let <math>A' = A - (A \cap B)</math> and <math>B' = B - (A \cap B)</math>. Notice <math>A'</math> and <math>B'</math> are disjoint. They are also nonempty because if <math>A = A \cap B</math> or <math>B = A \cap B</math>, then one of <math>A</math> and <math>B</math> is a subset of the other, so they are either not distinct or have different sums. Therefore <math>A'</math> and <math>B'</math> are disjoint subsets our set of 10 distinct two-digit numbers, which proves the claim. <math>\square</math> | |
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
==See Also== | ==See Also== |
Latest revision as of 16:25, 10 November 2023
Problem
Prove that from a set of ten distinct two-digit numbers (in the decimal system), it is possible to select two disjoint subsets whose members have the same sum.
Solution
There are distinct subsets of our set of 10 two-digit numbers. The sum of the elements of any subset of our set of 10 two-digit numbers must be between
and
. (There are fewer attainable sums.) As
, the Pigeonhole Principle implies there are two distinct subsets whose members have the same sum. Let these sets be
and
. Now, let
and
. Notice
and
are disjoint. They are also nonempty because if
or
, then one of
and
is a subset of the other, so they are either not distinct or have different sums. Therefore
and
are disjoint subsets our set of 10 distinct two-digit numbers, which proves the claim.
See Also
1972 IMO (Problems) • Resources | ||
Preceded by First Problem |
1 • 2 • 3 • 4 • 5 • 6 | Followed by Problem 2 |
All IMO Problems and Solutions |