Thread: Basics of Counting / Pidgeonhole principle question

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

2. 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!

3. Re: Basics of Counting / Pidgeonhole principle question

Originally Posted by masonD
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.

4. 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.