Practice (Category=PigeonholePrinciple(133))

back to index  |  new

177
Find that largest integer $A$ that satisfies the following property: in any permutation of the sequence $1001$, $1002$, $1003$, $\cdots$, $2000$, it is always possible to find $10$ consecutive terms whose sum is no less than $A$.

309
Prove: randomly select 51 numbers from $1, 2, 3, \cdots, 100$, at least two of them must be relatively prime to each other.

341
Let $a_1$, $a_2$, $a_3$, $\cdots$, $a_n$ be a random permutation of $1$, $2$, $3$, .., $n$, where $n$ is an odd number. Prove $$(a_1-1)(a_2-2)\cdots(a_n-n)$$ is an even number.

Prove: randomly select $51$ numbers from $1$, $2$, $3$, $\dots$, $100$, there must exist two numbers for which one is a multiple of the other.

There are $52$ people in a room. what is the largest value of $n$ such that the statement "At least $n$ people in this room have birthdays falling in the same month" is always true?

Place 9 points in a unit square. Prove it is possible to select 3 points from them to create a triangle whose area is no more than $\frac{1}{8}$.

The first and last initials of the 348 students form a unique ordered letter pair. We must find how many more students are required to guarantee that there are two students whose initials form the same ordered letter pair.

Prove: any convex pentagon must have three vertices $A$, $B$, and $C$ satisfying $\angle{ABC} \le 36^\circ$.

Given any four points on a plane, prove the ratio of the farthest distance between any two points over the shortest distance must be at least $\sqrt{2}$. What if the number of points is 5?

There are $99$ points on a plane. Among any three points, at least two of them are not more than $1$ unit length apart. Prove: it is possible to cover $50$ of these points using a unit circle.

Let $a_1, a_2, a_3, \cdots a_n$ be a randomly ordered sequence of 1, 2, 3, . . . , $n$. Prove the following product is an even number if $n$ is an odd integer: $$(a_1 -1)(a_2-2)(a_3-3)\cdots(a_n-n)$$

What is the smallest integer n for which any subset of {1, 2, 3, . . . , 20} of size $n$ must contain two numbers that differ by 8?

Colour all the points on a plane either white or black randomly. Show that it is always possible to find a triangle whose vertices have the same colour and its side length is either $1$ or $\sqrt{3}$.

Tom and Jerry are playing a game. In this game, they use pieces of paper with $2014$ positions, in which some permutation of the numbers $1, 2,\cdots, 2014$ are to be written. (Each number will be written exactly once). Tom fills in a piece of paper first. How many pieces of paper must Jerry fill in to ensure that at least one of her pieces of paper will have a permutation that has the same number as Tom's in at least one position?

Show that: (a) It is possible to divide all positive integers into three groups $A_1$, $A_2$, and $A_3$ such that for every integer $n\ge 15$, it is possible to find two distinct elements whose sum equals $n$ from all of $A_1$, $A_2$, and $A_3$. (b) Dividing all positive integers into four groups, then regardless of the partition, there must exists an integer $n\ge 15$ such that it is impossible to find two distinct numbers whose sum is $n$ in at least one of these four groups.

Alice places down $n$ bishops on a $2015\times 2015$ chessboard such that no two bishops are attacking each other. (Bishops attack each other if they are on a diagonal.)

  • Find, with proof, the maximum possible value of $n$.
  • For this maximal $n$, find, with proof, the number of ways she could place her bishops on the chessboard.

Show that among any $6$ people in the world, there must exist $3$ people who either know each other or do not know each other.

There are $6$ points in the $3$-D space. No three points are on the same line and no four points are one the same plane. Hence totally $15$ segments can be created among these points. Show that if each of these $15$ segments is colored either black or white, there must exist a triangle whose sides are of same color.

Seventeen people correspond by mail with one another - each one with all the rest. In their letters only three different topics are discussed. Each pair of correspondents deals with only one of these topics. Prove that there are at least three people who write to each other about the same topic.

There are $100$ guests attending a party. If everyone knows at least $67$ other guests, show that there must exist $4$ guests who know each other.

Show that among any four randomly selected integers, there must exist two whose difference is a multiple of 3.

Show that it is possible to find an integer whose digits are all 4 and it is a multiple of 2016.

There are 13 randomly selected points inside a square of side length 2. Show that there must exist quadrilateral whose vertice are among these 13 points and area is no more than 1.

Joe randomly selects 50 different numbers from 1, 2, $\cdots$, 97, 98, and finds there are always two of them whose difference is a multiple of 7. Can you explain why?

Among nine randomly selected even numbers from $2$, $4$, $6$, $\cdots$, $28$, $30$, show that at least two of them whose sum is $34$.