Results 1 to 3 of 3

Math Help - Generalized and contrapositive form of Pigeonhole principle and a math problem

  1. #1
    Senior Member x3bnm's Avatar
    Joined
    Nov 2009
    Posts
    300
    Thanks
    16

    Generalized and contrapositive form of Pigeonhole principle and a math problem

    A math problem:

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

    One kind of proof using an argument by contradiction:

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

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

    My question 1:

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

    Another kind of proof using a direct argument:

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

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

    Another question 2:

    Why's that "The remaining 12 - k computers are each used by at most 2 students."?
    Last edited by x3bnm; August 27th 2011 at 12:01 PM.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,537
    Thanks
    778

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

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

    My question 1:

    How did the author deduce that "Then 8 or more computers are used by 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.

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

    Another question 2:

    Why's that "The remaining 12 - k computers are each used by at most 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.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Senior Member x3bnm's Avatar
    Joined
    Nov 2009
    Posts
    300
    Thanks
    16

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

    Quote Originally Posted by emakarov View Post
    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.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. pigeonhole principle problem
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: October 20th 2011, 03:46 PM
  2. Replies: 2
    Last Post: August 27th 2011, 08:26 AM
  3. Generalized second order chained form (Lie Bracket problem)
    Posted in the Advanced Applied Math Forum
    Replies: 0
    Last Post: July 7th 2011, 06:33 PM
  4. Pigeonhole principle.
    Posted in the Number Theory Forum
    Replies: 0
    Last Post: October 9th 2010, 06:24 AM
  5. help me with pigeonhole principle #1
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: October 31st 2009, 03:58 PM

/mathhelpforum @mathhelpforum