For each of the following questions, identify the pigeons and the holes. Then, u

Question

For each of the following questions, identify the pigeons and the holes. Then, using the Pigeonhole Principle, prove that the following statements are true. Prove that if seven distinct numbers are selected from [2, 3, 4,..., 12], then some two of these numbers will add up to 14. Prove that a grouping of any ten distinct integers, there exists integers x and y such that x - y is a multiple of 9. Prove that if 12 integers are selected from among [1, 2, 3,..., 22], then from the 12 integers selected there exists integers a and b such that a = b + 1. Prove that there will always be two people at a party who will have the same number of friends as each other. (We assume parties must be at­ ended by more than one person and that friendship is a symmetric rela­tionship).

Explanation / Answer

Part 1

Two holes:

First is selected numbers less than 7

Second is selected numbers greater than or equal to 7

Pigeons are the given numbers from: 2 to 12

There are only 5 numbers less than 7 ie 2,3,4,5,6

Hence out of the selected numbers at most 5 go into the first hole

and at least two go into the second hole.

In second hole numbers are greater than or equal to 7

Hence sum of any two numbers in second hole is at least 14

Hence proved.

Part 2

9 holes. Each corresponding to a remainder modulo 9 ie 0,1,2,....,8

A number ,x,goes into a hole corresponding to m remainder modulo 9 if: x=m mod 9

Pigeons are the given 10 distinct integers.

9 holes and 10 pigeons hence at least 2 pigeons ie two distinct integers must go into the same hole ie have same remainder modulo 9

Let those two integers be x,y

Hence, x=y mod 9

Hence, x-y =0 mod 9

Hence proved.

Part 3

11 holes. Each holes corresponds to one of the set of integers: {1,2},{3,4},{5,6} .... {21,22}

Pigeon are the given numbers from 1 to 22

So a selected integer goes into a hole if it is one of the numbers corresponding to that hole.

12 numbers are there and 11 holes so at least 2 of the numbers must go into one common hole.

Note each hole has consecutive integers.

Hence proved.

Related Questions

Navigate

• Browse (All)
• Browse F
• Subjects

---

---

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