Solve the problems below using the pigeonhole principle: A) How many cards must be drawn from a standard 52-card deck to guarantee 2 cards of the same suit? Note that there are 4 suits. B) Prove that if four numbers are chosen from the set {1, 2, 3, 4, 5, 6}, at least one pair must add up to 7. Hint: Find all pairs of numbers from the set that add to 7. C) Prove that for any 10 given distinct positive integers that are less than 100, there exist two different non-empty subsets of these 10 numbers, whose members have the same sum. An example of the 10 given numbers could be 23, 26, 47, 56, 14, 99, 94, 78, 83, 69. One subset of the 10 numbers could be {23, 26, 47, 56}, and another subset could be {83, 69}. The sum of the elements in the first set is 152, and it is equal to the sum of the elements in the second subset. Hint: identify how many pigeons and how many holes you have before using the pigeonhole principle.
Solve the problems below using the pigeonhole principle:
A) How many cards must be drawn from a standard 52-card deck to guarantee 2 cards
of the same suit? Note that there are 4 suits.
B) Prove that if four numbers are chosen from the set {1, 2, 3, 4, 5, 6}, at least one
pair must add up to 7.
Hint: Find all pairs of numbers from the set that add to 7.
C) Prove that for any 10 given distinct positive integers that are less than 100, there
exist two different non-empty subsets of these 10 numbers, whose members have the same
sum.
An example of the 10 given numbers could be 23, 26, 47, 56, 14, 99, 94, 78, 83, 69. One
subset of the 10 numbers could be {23, 26, 47, 56}, and another subset could be {83, 69}.
The sum of the elements in the first set is 152, and it is equal to the sum of the elements in
the second subset.
Hint: identify how many pigeons and how many holes you have before using the pigeonhole
principle.
Trending now
This is a popular solution!
Step by step
Solved in 3 steps
