MIX PROBLEM ASSIGNMENT 1

MIX PROBLEM
1. Given twelve integers, show that two of them can be chosen whose difference is divisible by 11.
2. The city of Leningrad has five million inhabitants. Show that two of these must have the same
number of hairs on their heads, if it is known that no person has more than million hairs on his or
her head.
3. In the country of Courland there are M football teams, each of which has 11 players. All the
players are gathered at an airport for a trip to another country for an important game, but they are
traveling on “stand by’’ There are 10 flights to their destination, and it turns out that teach flight
has room for exactly M players. One football player will take his own helicopter to the game,
rather than travelling standby on a plane. Show that at least one whole team will be sure to get to
the important game.
4. Show that in any group of five people, there are two who have an identical number of friends
within the group.
5. Several football teams enter a tournament in which each team plays every other team exactly
once. Show that any moment during the tournament there will be two teams which have played,
up to that moment, an identical number of games.
6. Ten students solved a total of 35 problems in a math Olympiad. Each problem was solved by
exactly one student. There is at least one student who solved exactly one problem, at least one
student who solved exactly two problems, and at least one student who solved exactly three
problems. Prove that there is also at least one student who has solved at least five problems.
7. Five young workers received as wages 1500 rubles altogether. Each of them wants tobuy a
cassette player costing 320 rubles. Prove tha least one of them must wait for the next paycheck to
make his purchase.
8. In a brigade of 7 people, the sum of the ages of the members is 332 years. Prove that three
memebers can be chosen sothat the sum of their ages is no less than 142 years.
9. Porve that of any 52 integers, two can always be found such that the difference of their square is
divisible by 100.
10. Prove that there exists a power of three which ends with the digits 001 (in decimal notation)
MIX PROBLEM 2

Solutions
1. Given twelve integers, show that two of them can be chosen whose difference is divisible by 11.
Sol. The pigeon holes are the remainder when divided by 11. The pigeons are the numbers. If two
numbers have the same remainder when divided by 11. Their difference must be divisible by 11.
2. The city of Leningrad has five million inhabitants. Show that two of these must have the same
number of hairs on their heads, if it is known that no person has more than million hairs on his or
her head.
Sol. The pigeon holes here are the numbers of hairs on a person’s head (from 1 to 1,000,000). The
pigeons are the citizens of Leningrad.
3. In the country of Courland there are M football teams, each of which has 11 players. All the
players are gathered at an airport for a trip to another country for an important game, but they are
traveling on “stand by’’ There are 10 flights to their destination, and it turns out that teach flight
has room for exactly M players. One football player will take his own helicopter to the game,
rather than travelling standby on a plane. Show that at least one whole team will be sure to get to
the important game.
Sol. Let us sort the football players by team as they come off their airplanes. There will be 10M + 1
players to sort. The General Pigeon Hole Principle assures us that there will be one team which
has 11 players, and this team is complete.
4. Show that in any group of five people, there are two who have an identical number of friends
within the group.
Sol. There are give possible numbers of acquaintances for nay person : 0,1,2,3 or 4. So it would seem
that each could have a different number of friends. However, if any person has four
acquaintances, then no person may have zero acquaintances. Hence two people must have the
same number of acquaintances.
5. Several football teams enter a tournament in which each team plays every other team exactly
once. Show that any moment during the tournament there will be two teams which have played,
up to that moment, an identical number of games.
Sol. If there are k teams, then the number of games played by each team varies from 0 to k –1.
However, if any team has played k –1 games, then it has played every other team, and no team has
played 0 games. Hence wee are fitting k teams into k –1 pigeon holes, which are either the
number from 0 through k –2 or the number 1 through k –1
MIX PROBLEM 3

6. Ten students solved a total of 35 problems in a math Olympiad. Each problem was solved by
exactly one student. There is at least one student who solved exactly one problem, at least one
student who solved exactly two problems, and at least one student who solved exactly three
problems. Prove that there is also at least one student who has solved at least five problems.
Sol: At least 1 + 2 + 3 = 6 problems were solved by the students mentioned in the problem statement.
Therefore, there are 29 problems left to be solved, and 7 students to account for them. If each
student had solved only 4 problems, then there would have been only 28 problems solved.
Therefore, one student must have solved at least 5 problems.
7. Five young workers received as wages 1500 rubles altogether. Each of them wants tobuy a
cassette player costing 320 rubles. Prove tha least one of them must wait for the next paycheck to
make his purchase.
Sol : The sum S of their earning is 1500 rubles, so the above princple guarantees that at least one
worker earned no more than 1500/5 = 300 tubles. Such a worker must wait for his cassette player.
8. In a brigade of 7 people, the sum of the ages of the members is 332 years. Prove that three
memebers can be chosen sothat the sum of their ages is no less than 142 years.
Sol: We look at all possible triles of brigade members. If we add the three ages in each gorup, then
sum these numbers, this final sum must be 15.332 (since each person apears in a triaple 15 times).
Yet there are altogther 35 triples. This means that there is a triple of bridage members such that
the sum of their ages is not less than 15.332/35, which is grater than 142
9. Porve that of any 52 integers, two can always be found such that the difference of their square is
divisible by 100
Sol. When divided by 100, a perfect squar can give only 51 remainder, since the number x2 and
(100 – x)2 giv the same remainder. Hence of 52 integers, the squares of two must have the same
remainder when divided by 100. These two squres differ by a multiple of 100.
10. Prove that there exists a power of three which ends with the digits 001 (in decimal notation)
Sol. If 3m and 3n (where m > n) are two powers of 3 which give the same remander when divided by
1000, then 3m(3m–n –1) is divisible by 1000. Now the prime factors of 1000 are 2 and 5, and
neigher divides 3n. It follows that 1000 must divide 3m–n–1, which means that 3m–n is a power of 3
ending in the digits 001.