Pigeonhole principle

Printable View

January 31st 2009, 10:12 AM
drthea

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.
January 31st 2009, 02:00 PM
ThePerfectHacker

Quote:

Originally Posted by drthea

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.
January 31st 2009, 02:03 PM
clic-clac

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 :)
January 31st 2009, 02:43 PM
Plato

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.
January 31st 2009, 03:59 PM
drthea

Quote:

Originally Posted by Plato

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!