Difference between revisions of "1972 IMO Problems/Problem 1"
m (→Solution) |
(→Solution (Cheap Way)) |
||
| Line 7: | Line 7: | ||
Note that there are <math>2^{10}-2=1022</math> distinct subsets of our set of 10 two-digit numbers. Also note that the sum of the elements of any subset of our set of 10 two-digit numbers must be between 10 and <math>91+92+93+94+95+96+97+98+99</math>, which is less than <math>100+100+100+100+100+100+100+100+100=1000 < 1022</math>. There are even less attainable sums. The [[Pigeonhole Principle]] then implies that there are two distinct subsets whose members have the same sum. Let these sets be <math>A</math> and <math>B</math>. Note that <math>A- (A\cap B)</math> and <math>B- (A\cap B)</math> are two distinct sets whose members have the same sum. These two sets are subsets of our set of 10 distinct two-digit numbers, so this proves the claim. <math>\square</math> | Note that there are <math>2^{10}-2=1022</math> distinct subsets of our set of 10 two-digit numbers. Also note that the sum of the elements of any subset of our set of 10 two-digit numbers must be between 10 and <math>91+92+93+94+95+96+97+98+99</math>, which is less than <math>100+100+100+100+100+100+100+100+100=1000 < 1022</math>. There are even less attainable sums. The [[Pigeonhole Principle]] then implies that there are two distinct subsets whose members have the same sum. Let these sets be <math>A</math> and <math>B</math>. Note that <math>A- (A\cap B)</math> and <math>B- (A\cap B)</math> are two distinct sets whose members have the same sum. These two sets are subsets of our set of 10 distinct two-digit numbers, so this proves the claim. <math>\square</math> | ||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
==See Also== | ==See Also== | ||
Revision as of 20:31, 12 March 2018
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
Note that there are 
distinct subsets of our set of 10 two-digit numbers. Also note that the sum of the elements of any subset of our set of 10 two-digit numbers must be between 10 and 
, which is less than 
. There are even less attainable sums. The Pigeonhole Principle then implies that there are two distinct subsets whose members have the same sum. Let these sets be 
and 
. Note that 
and 
are two distinct sets whose members have the same sum. These two sets are subsets of our set of 10 distinct two-digit numbers, so this 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 | ||
