Discrete Mathematics
# Pigeonhole Principle

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$.

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.