Use the pigeonhole principle (or generalized pigeonhole principle) explicitly to

Question

Use the pigeonhole principle (or generalized pigeonhole principle) explicitly to solve these simple brain-teasers. (a) Your bureau drawer contains 10 pairs of loose socks, each pair a different color. How many socks must you take out of the drawer without looking to be sure of getting a matched pair? (b) Your bureau drawer contains 10 loose red socks and 10 loose blue socks. How many socks must you take out of the drawer without looking to be sure of getting a matched pair? Show that there are more than 10,000 people in the United States who all have the same height (to the nearest half-inch) and the same weight (to the nearest pound). Ten thousand dollars is available for raises this year in a company with nine employees. Show that at least one of the employees will get less than a $1200 raise. Determine the value of the Ramsey number R(2). Explain how Theorem 5 is a special case of Theorem 6. Show that the configuration that the computer in Example 2 is in after 2^N + 1 units of time have passed is a state that it was previously in. (This is saying slightly more than was claimed in the discussion in Example 2.) Show that if S is a set containing 10 positive integers less than 54, then at least two different (not necessarily disjoint) four-element subsets of S have the same sum. Show that if S is a set containing 10 positive integers less than 118, then at least two different (not necessarily disjoint) subsets of S have the same sum. Show that any subset of {1, 2, ..., 2n} having cardinality n + 1 contains two distinct elements that are relatively prime (i.e., have a greatest common divisor of 1).

Explanation / Answer

S = set of 10 positive numbers less than 118

eg: (5,10,15,20,25,30,35,40,45,50) is an example of set containing 10 ositive numbers less than 118

Subset of S {(5,45),(10,40),(15,35),(20,30)} all these subsets of S have the same sum =50

Related Questions

Navigate

• Browse (All)
• Browse U
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.