Pigeonhole Principle (Dirichlet's principle) is a simple, intuitive, and often useful method for proving statements about a finite set. This principle is often used in discrete mathematics, where it establishes a connection between objects (“rabbits”) and containers (“cells”) when certain conditions are met.
1. The school has 400 students. Prove that at least two of them were born on the same day of the year.
2. There are 40 students in the class. Is there a month in the year in which at least 4 students in this class celebrate their birthday?
3. There are 30 students in the class. In the dictation, Vova made 13 mistakes, the rest less. Prove that at least three students made an equal number of mistakes.
4. Of any three integers, you can choose two whose sum is even. Prove it.
5. Among any six integers, there are two numbers whose difference is a multiple of 5. Prove this.
6. Prove that from any n + 1 integers you can choose two numbers whose difference is divisible by n.
7. Given 12 different two-digit numbers. Prove that you can choose two numbers from them, the difference of which is a two-digit number written in two identical digits.
8. From any hundred integers, can you choose two numbers whose sum is a multiple of 7?
9. Are there a) fifty; b) more than fifty different two-digit numbers, the sum of no two of which is not equal to 100?
10. Of any a) 51; b) 52 integers, can you choose two numbers whose sum or difference is a multiple of 100?
11. There are 44 queens on the chessboard. Prove that each of them beats some other queen.
12. Is it possible to arrange the numbers 0, 1 and –1 in a 6x6 table so that all the sums of the numbers along the verticals, horizontals and two main diagonals are different?
Be up-to-date with our recent updates, new problems and answers!
