Results 1 to 4 of 4

Thread: Basics of Counting / Pidgeonhole principle question

  1. #1
    Newbie
    Joined
    Nov 2017
    From
    tornoto
    Posts
    3

    Basics of Counting / Pidgeonhole principle question

    Hello, I'm having trouble with this question.

    36. A computer network consists of six computers. Each computer is directly connected to at least one of the other computers. Show that there are at least two computers in the network that are directly connected to the same number of other computers.

    I'm wondering about what form my solution should be in -- is it acceptable to have a written explanation or is there a specific proof method I need to use?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor

    Joined
    Apr 2005
    Posts
    19,449
    Thanks
    2892

    Re: Basics of Counting / Pidgeonhole principle question

    Suppose this were not true. That is, suppose there were no two computers connected the same number of other computers. Since each computer is connected to at least one other computer, those six computers must be connected to 1, 2, 3, 4, 5, and 6 other computers. But there are only 6 computes and we don't consider a computer connect to itself!
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor

    Joined
    Aug 2006
    Posts
    21,485
    Thanks
    2730
    Awards
    1

    Re: Basics of Counting / Pidgeonhole principle question

    Quote Originally Posted by masonD View Post
    36. A computer network consists of six computers. Each computer is directly connected to at least one of the other computers. Show that there are at least two computers in the network that are directly connected to the same number of other computers.
    Make a list $d_1,~d_2,~d_3,~d_4,~d_5,~d_6$ of integers $1\le d_k\le 5$ that tells you how many other computers the $k^{th}$ computer is connected. Can you show that list cannot contain an odd number of odd numbers?
    Then apply the pigeon-hole.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor
    Joined
    Nov 2010
    Posts
    3,014
    Thanks
    1152

    Re: Basics of Counting / Pidgeonhole principle question

    List the number of computers to which each computer is connected. You have six numbers that must be at least one and at most 5. By the Pigeonhole Principle, at least one number must be appear at least twice.

    Aww, Halls and Plato beat me to it.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Basics Of Counting - Total number of strings
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: Mar 30th 2017, 03:11 PM
  2. Basics of Counting: Induction Proof (Product Rule)
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: Nov 6th 2012, 06:46 PM
  3. Counting Principle
    Posted in the Statistics Forum
    Replies: 1
    Last Post: Sep 15th 2011, 10:41 AM
  4. Counting principle
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: May 4th 2010, 09:53 PM
  5. The Counting Principle
    Posted in the Statistics Forum
    Replies: 2
    Last Post: Aug 25th 2009, 04:04 PM

/mathhelpforum @mathhelpforum