Difference between revisions of "1972 IMO Problems/Problem 1"

m
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>90+91+92+93+94+95+96+97+98+99=945</math>. This shows that there are 846 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>\blacksquare</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>90+91+92+93+94+95+96+97+98+99=945</math>. This shows that there are 846 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>\blacksquare</math>
 +
 +
==Solution (Cheap Way)==
 +
 +
By definition an empty set is disjoint to any other set. Therefore, our subsets will be empty set and empty set.
  
 
{{alternate solutions}}
 
{{alternate solutions}}

Revision as of 20:28, 12 July 2017

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 $2^{10}-2=1022$ 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 $90+91+92+93+94+95+96+97+98+99=945$. This shows that there are 846 attainable sums. The Pigeonhole Principle then implies that there are two distinct subsets whose members have the same sum. Let these sets be $A$ and $B$. Note that $A- (A\cap B)$ and $B- (A\cap B)$ 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. $\blacksquare$

Solution (Cheap Way)

By definition an empty set is disjoint to any other set. Therefore, our subsets will be empty set and empty set.

Alternate solutions are always welcome. If you have a different, elegant solution to this problem, please add it to this page.

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
Invalid username
Login to AoPS