# Generalized and contrapositive form of Pigeonhole principle and a math problem

• Aug 27th 2011, 09:54 AM
x3bnm
Generalized and contrapositive form of Pigeonhole principle and a math problem
A math problem:

There are \$\displaystyle 42\$ students who are to share \$\displaystyle 12\$ computers. Each student uses exactly \$\displaystyle 1\$ computer and no computer is used by more than \$\displaystyle 6\$ students. Show that at least \$\displaystyle 5\$ computers are used by \$\displaystyle 3\$ or more students.

One kind of proof using an argument by contradiction:

Suppose not. Suppose that \$\displaystyle 4\$ or fewer computers are used by \$\displaystyle 3\$ or more students.[A contradiction will be derived.]Then \$\displaystyle 8\$ or more computers are used by \$\displaystyle 2\$ or fewer students.

.........
(End of first proof)

My question 1:

How did the author deduce that "Then \$\displaystyle 8\$ or more computers are used by \$\displaystyle 2\$ or fewer students"?

Another kind of proof using a direct argument:

Let \$\displaystyle k\$ be the number of computers used by \$\displaystyle 3\$ or more students.[We must show that \$\displaystyle k \geq 5\$] Because each computer is used by at most \$\displaystyle 6\$ students, these computers are used by at most \$\displaystyle 6k\$ students(by the contrapositive form of the generalized pigeonhole principle). The remaining \$\displaystyle 12 - k\$ computers are each used by at most \$\displaystyle 2\$ students.

.........
(End of this proof)

Another question 2:

Why's that "The remaining \$\displaystyle 12 - k\$ computers are each used by at most \$\displaystyle 2\$ students."?
• Aug 27th 2011, 02:22 PM
emakarov
Re: Generalized and contrapositive form of Pigeonhole principle and a math problem
Quote:

Originally Posted by x3bnm
Suppose not. Suppose that \$\displaystyle 4\$ or fewer computers are used by \$\displaystyle 3\$ or more students.[A contradiction will be derived.]Then \$\displaystyle 8\$ or more computers are used by \$\displaystyle 2\$ or fewer students.

My question 1:

How did the author deduce that "Then \$\displaystyle 8\$ or more computers are used by \$\displaystyle 2\$ or fewer students"?

Let U be the set of all computers and let A be the set of all computers used by 3 or more students. The problem asks to prove that |A| (the cardinality of A) is >= 5. Suppose this is not the case, i.e., |A| <= 4. Then |U \ A| = |U| - |A| = 12 - |A| >= 8. Also, each computer in U \ A is used by at most two students by the definition of A.

Quote:

Let \$\displaystyle k\$ be the number of computers used by \$\displaystyle 3\$ or more students.[We must show that \$\displaystyle k \geq 5\$] Because each computer is used by at most \$\displaystyle 6\$ students, these computers are used by at most \$\displaystyle 6k\$ students(by the contrapositive form of the generalized pigeonhole principle). The remaining \$\displaystyle 12 - k\$ computers are each used by at most \$\displaystyle 2\$ students.

Another question 2:

Why's that "The remaining \$\displaystyle 12 - k\$ computers are each used by at most \$\displaystyle 2\$ students."?
Again, k is the number of all computers with at least 3 users; the other 12 - k computers have at most 2 users by the definition of k.
• Aug 28th 2011, 02:19 AM
x3bnm
Re: Generalized and contrapositive form of Pigeonhole principle and a math problem
Quote:

Originally Posted by emakarov
Let U be the set of all computers and let A be the set of all computers used by 3 or more students. The problem asks to prove that |A| (the cardinality of A) is >= 5. Suppose this is not the case, i.e., |A| <= 4. Then |U \ A| = |U| - |A| = 12 - |A| >= 8. Also, each computer in U \ A is used by at most two students by the definition of A.

Again, k is the number of all computers with at least 3 users; the other 12 - k computers have at most 2 users by the definition of k.

Thank you emakarov. That answers my question.