Waste less time on Facebook — follow Brilliant.
Back to all chapters

Pigeonhole Principle

If you have 12 pigeons and there are only 11 roosts, then at least one roost will be quite cozy.

Pigeonhole Principle: Level 4 Challenges


If we pick 77 numbers randomly from the set \(\{1,2,3,4,...,150\}\), we are guaranteed to have at least \(k\) pairs of numbers where the difference between each pair is 19. What is the maximum possible value of \(k?\)

Please treat a pair as a combination, not a permutation.

From the set {\(1,2,3,...,n\)}, \(10\) numbers are removed such that there is no Arithmetic Progression of length \(11\) among the numbers left in the set.

Find the smallest \(n\) such that no matter which \(10\) numbers are removed, there always is one Arithmetic Progression of length \(11\).

A \(1000\times1000\) array is to be filled with integers between 1 and 1000 inclusive, with each integer appearing 1000 times. What is the maximum value of \(n\) such that there necessarily exists a row or column with at least \(n\) distinct integers?

Let \(a_0, a_1, \cdots, a_7\) be any \(8\) distinct integers. Let \(P\) be the product of their pairwise differences, that is:

\[P = \prod _ {i < j} {(a_i - a_j)} \]

What is the greatest integer which always divides \(P?\)

Determine the least positive integer \( n \) for which the following condition holds: No matter how the elements of the set of the first \(n\) positive integers, i.e. \( \{1, 2, \ldots n \}\), are colored in red or blue, there are (not necessarily distinct) integers \( x, y, z\), and \( w \) in a set of the same color such that \( x + y + z = w\).

Details and assumptions

The phrase not necessarily distinct means that the integers can be repeated. For example, if \(1, 2, 4 \) are all colored red, then we have \( 1 + 1 + 2 = 4 \) which would satisfy the condition.


Problem Loading...

Note Loading...

Set Loading...