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.

×

Problem Loading...

Note Loading...

Set Loading...