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."?

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.

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.