Results 1 to 5 of 5

Math Help - Pigeonhole principle

  1. #1
    Newbie
    Joined
    Oct 2008
    From
    @home
    Posts
    17

    Pigeonhole principle

    Hi, I need help to understand how to solve problems based on the pigeonhole principle. I need hints on solving them. Could you help me please?

    1.
    A computer network consists of 6 computers. Every computer is connected to 0 or more computers. Prove that there are 2 computers, that are connected to the same number of computers.

    2.
    Suppose that we have cables to connect computers to printers. Find the smallest number of cables that guarantee that if we connect 8 computers to 4 printers, there are at least 4 computers that are connected to 4 different printers. Calculate the smallest number of cables for 100 computers and 20 printers, such as 20 computers are connected to 20 different printers.

    3.
    The population of Greece is 11.000.000. Prove that there exists a day in the year that at least 50 people have birthday and that all of them have the same initial letters (name and surname). *alphabet consists of 24 letters.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Global Moderator

    Joined
    Nov 2005
    From
    New York City
    Posts
    10,616
    Thanks
    9
    Quote Originally Posted by drthea View Post
    A computer network consists of 6 computers. Every computer is connected to 0 or more computers. Prove that there are 2 computers, that are connected to the same number of computers.
    This problem can be generalized. Prove that in a network of n computers there are two which are connected to the same number of computers. The proof goes by induction. Of course it is true for n=2 so let us assume it is true for k\geq 2 network of computers. Say we have k+1 network. There are two cases: every computer is connected; there exists a computer not connected to the rest of the other computers. In the first case if every computer is connected then it means the # of connected computers for each computer is between 1 and k. But there are k+1 computers, so there exist two computers that have the same number of connections. In the second case isolate the computer not connected to anything else. Then we are left with a k-computer network. But then it follows by induction that there exists two computers in this network that are connected to the same number of computers.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Senior Member
    Joined
    Nov 2008
    From
    Paris
    Posts
    354
    A general solution for 1) to show a way to use the principle. We give to every computer a number, which is its number of connections.
    If they are 2 computers, either they're connected or not, but in the two cases they have the same number ( 1 or 0).

    Assume that a n-computers network has always at least two computers with the same number. Consider a network with n+1 computers.
    What about the computers whose number is 0?
    If they're more than 2, it's over.
    If there is one, then the n other computers form a n-computers network, so there are at least 2 computers that have the same number (our hypothesis).
    Finally, if there is no computer with number 0, then the n+1 computers have numbers which belong to \{1,...,n\}. Therefore if you want to sort computers by numbers, the pigeonhole principle states that at least two computers will have the same number.

    Therefore for all integer n greater or equal than 2, a n-computers netword has 2 computers which have the same number of connections.


    EDIT: ThePerfectHacker writes faster
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,395
    Thanks
    1481
    Awards
    1
    Here is strong hint on #3.
    Using the floor function: \left\lfloor {\frac{{\frac{{11\left( {10^6 } \right)}}{{24^2 }}}}{{365}}} \right\rfloor  = 52

    BTW: If your discrete mathematics course includes a section on graph theory then #1 above is an important theorem. In any simple graph of order two or more there are at least two vertices with the same degree.
    Last edited by Plato; January 31st 2009 at 03:01 PM.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Newbie
    Joined
    Oct 2008
    From
    @home
    Posts
    17
    Quote Originally Posted by Plato View Post
    Here is strong hint on #3.
    Using the floor function: \left\lfloor {\frac{{\frac{{11\left( {10^6 } \right)}}{{24^2 }}}}{{365}}} \right\rfloor  = 52

    BTW: If your discrete mathematics course includes a section on graph theory then #1 above is an important theorem. In any simple graph of order two or more there are at least two vertices with the same degree.
    OK, about this I understand that the function gives the correct answer, but I wonder how you can get there.
    This is how I think of the problem:

    There are 11.000.000 people and 365 days of possible birthdays.
    11.000.000/365= 30136 people have birthday at 365 different days but none of them share the same birthday.
    If I want 2 people who have the same birthday then I should choose 30137 people among 11.000.000.
    But I want 50 people who share the same birthday, so I should choose 30137 x 25 = 753425 people.

    In addition to that, there are 24x24=576 possible initial letters.
    Among 11.000.000 people there are 11.000.000/576 = 19097 people who have unique initials.
    If I want 2 who have the same initials, I need 19098 people.
    But I want 50, so I need 19098x25 = 477450 people from 11.000.000.

    But I cannot connect the birthdays to the initial letters
    About graphs, there is a chapter at my notes and I think that the next week we'll be doing that.

    Edit:
    About the 1st problem, I need some time to think about that. Thanks for your answers!
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. help me with pigeonhole principle #2
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: October 31st 2009, 11:23 PM
  2. help me with pigeonhole principle #1
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: October 31st 2009, 03:58 PM
  3. Pigeonhole principle?
    Posted in the Advanced Math Topics Forum
    Replies: 3
    Last Post: December 9th 2007, 08:58 AM
  4. Pigeonhole Principle
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: August 30th 2007, 03:15 PM
  5. Pigeonhole Principle
    Posted in the Advanced Algebra Forum
    Replies: 0
    Last Post: January 23rd 2006, 06:09 PM

Search Tags


/mathhelpforum @mathhelpforum