1. ## Partitions and sets

a) what is the smallest number of integers that must be selected from {1,2....,30} in order to guarantee that the selection contains five numbers X1, X2,.....,X5 such that 3| < (Xi-Xj), 1<= i, j<= 5? (prove the answer)

b) Generalize the statement in (a): given positive integers n,k and t, such that n>=tk, what is the smallest number of integers that must be selected from {1,2,...,n} in order to guarantee that the selection contains t numbers X1, X2, .....,Xt such that k|
(Xi-Xj), 1<= i, j<= t? (no proof needed)

2. For (a)

$\displaystyle \mathbb{Z}/3\mathbb{Z}$ contains 3 equivalence-classes. If we have 2 numbers $\displaystyle x,y$ such that $\displaystyle 3|x-y$ that is $\displaystyle x-y\equiv 0$ mod 3.

Hence by the pigeon-hole principle we must choose $\displaystyle 3\cdot 4 + 1$ numbers from $\displaystyle \left\{1,\cdots, 30\right\}$ such that at least 5 of these numbers are in the same residu-class modulo 3.

For (b) that must be $\displaystyle t(k-1)+1$ since $\displaystyle \mathbb{Z}/k\mathbb{Z}$ contains k residu-classes.

Or did I misunderstand your question perhaps?