1. Prove that among every 1000 people there are two which selebrate their
birthday on the same day. Can one find a day when 3 people selebrate their
birthdays? How about 4 people?
2. Prove that among any 101 numbers one can find two numbers whose difference is divisible by 100.
3. A city has 10000 different telephone lines numbered by 4-digit
numbers. More than half of the telephone lines are in the downtown.
Prove that there are two telephone numbers in the downtown whose sum is
again the number of a downtown telephone line.
4. Thirty members of the Cannibal Club had a joint dinner. After the
dinner, it became known that among every six members of the club, one ate ]
another one. Prove that there are at least 6 members of the club which are
inside one another (the first member is inside the second one, the second
member is inside the third one and so on).
5. There are 1091 small bugs on a table of size 2 ft by 3 ft. Prove that
at any time you can catch at least 6 of them by covering them with a
cylindrical drinking glass of diameter 3 in.
6. A student solves math problems every day. It is known that he never
solves more than 12 problems per week. Prove that there are several
consecutive days in one year when he solved exactly 20 problems.
7. There are 6 people at a party. Prove that either 3 of them knew each
other before the party or 3 of them were complete strangers before the
party.
1. A typical year consists of 365 days. We have 1000 people.
Since 1000 is greater than 365*2+1=731, the pigeon-hole principle says
that there is
always a day when (at least) three of the people have their birthdays.
(Note: we don't know which particular day those three people selebrate their
birthdays. We only know that such a day does exist.) Since
1000 less than 365*3, it is perfectly possible that there is no day
such that four people have their birthdays at this day. For example, it
can happen that each day from January,1 through October,1 exactly three of
the people have their birthdays and each day from October,1 through December,
31 no more than two of them have their birthdays.
2. There are exactly 100 possible remainders when we divide a number
by 100. These are 0, 1, 2, 3, 4, 5, 6, ..., 97, 98, 99. The pigeon-hole
principle says that since we have 101 numbers and only 100 possible
remainders, there are (at least) two numbers among them which have the same
remainders. Then the difference of two such numbers has remainder 0 and
therefore is divisible by 100.
3. We know that there are at least 5001 different telephone numbers
in the downtown. It may happen that the number 0000 is in the downtown. In
this case we can add this number to any other downtown number, get the same
downtown number and we are done. Suppose that the number 0000 is not in the
downtown. Take the smallest telephone number N in the downtown and consider
all possible differences between downtown telephone numbers and N. There
are at least 5000 distinct positive values for these differences and there
are at least 5001 positive downtown telephone numbers. Since there are
only 9999 positive telephone numbers in all, by the pigeon-hole principle,
there is a telephone number M in the downtown which is also the difference of
two downtown telephone numbers, say T-N. So, M=T-N and T=M+N. We are done.