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?
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.
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.
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.
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 computers, either they're connected or not, but in the two cases they have the same number ( or ).
Assume that a -computers network has always at least two computers with the same number. Consider a network with computers.
What about the computers whose number is ?
If they're more than , it's over.
If there is one, then the other computers form a -computers network, so there are at least computers that have the same number (our hypothesis).
Finally, if there is no computer with number , then the computers have numbers which belong to . 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 greater or equal than , a -computers netword has computers which have the same number of connections.
EDIT: ThePerfectHacker writes faster :)
Here is strong hint on #3.
Using the floor function:
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.
Originally Posted by Plato
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.
About the 1st problem, I need some time to think about that. Thanks for your answers!