Difference between revisions of "1972 IMO Problems/Problem 1"
(→Solution (Cheap Way)) |
Ehuang0531 (talk | contribs) (technicality - assuming A and B must be nonempty) |
||
(One intermediate revision by one other user 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 15: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 |