×

## Pigeonhole Principle

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

# Level 4

If we pick 77 numbers randomly from the set $$\{1,2,3,4,...,150\}$$, we are guaranteed to have at least $$k$$ pairs where the difference between the two numbers 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.

×