Generalized and contrapositive form of Pigeonhole principle and a math problem

**A math problem:**

There are students who are to share computers. Each student uses exactly computer and no computer is used by more than students. Show that at least computers are used by or more students.

**One kind of proof using an argument by contradiction:**

Suppose not. Suppose that or fewer computers are used by or more students.[A contradiction will be derived.]Then or more computers are used by or fewer students.

.........

(End of first proof)

**My question 1:**

How did the author deduce that "Then or more computers are used by or fewer students"?

**Another kind of proof using a direct argument:**

Let be the number of computers used by or more students.[We must show that ] Because each computer is used by at most students, these computers are used by at most students(by the contrapositive form of the generalized pigeonhole principle). The remaining computers are each used by at most students.

.........

(End of this proof)

**Another question 2:**

Why's that "The remaining computers are each used by at most students."?

Re: Generalized and contrapositive form of Pigeonhole principle and a math problem

Quote:

Originally Posted by

**x3bnm** Suppose not. Suppose that

or fewer computers are used by

or more students.[A contradiction will be derived.]Then

or more computers are used by

or fewer students.

**My question 1:**
How did the author deduce that "Then

or more computers are used by

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

be the number of computers used by

or more students.[We must show that

] Because each computer is used by at most

students, these computers are used by at most

students(by the contrapositive form of the generalized pigeonhole principle). The remaining

computers are each used by at most

students.

**Another question 2:**
Why's that "The remaining

computers are each used by at most

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.