Will 75 element subset S of $\{1, 2, 3, .\ldots, 100\}$ must contain three consecutive integers? Intuition says that it should be correct. Trying to see this from pigeonhole principle, I say that there are only 98 combinations of pair possible from (1,2,3) to (98,99,100) which will have to be in subset S. So I take those 98 pairs as pigeons and 75 elements of S as pigeons. I am not sure if my thinking is correct.
 A: In order to not have three consecutive integers, every two consecutive integers must be followed by a gap. Suppose your set was as dense as possible (i.e. your set consisted entirely of pairs of consecutive integers separated by one, e.g. $\{1,2,4,5,7,8,...\}$). In this way, we have constructed the largest possible set of integers on $\{1,...,100\}$ which does not contain any three consecutive numbers. It's easy to convince yourself that there cannot be more than 67 elements in this set (as this set occupies at most 2/3 of the integers from 1 to 100). So, for any number of elements larger than 67, you can't avoid having three consecutive integers.
This statement can be generalized: the maximum number of integers one can pick from $1$ to $N$ without having any set of $n$ consecutive integers is
$$\left\lceil\frac{n-1}{n}N\right\rceil$$
A: Let the selected integers be $y_1,...,y_{75}$, where
$$1 \le y_1 < y_2 < y_3 < \cdots < y_{75} \le 100$$
Note that
\begin{align*}
&(y_3-y_1)\\[2pt]
+\;&(y_5-y_3)\\[2pt]
+\;&(y_7-y_5)\\[2pt]
&\;\;\;\;\;\;\,\vdots\\[2pt]
+\;&(y_{73}-y_{71})\\[2pt]
+\;&(y_{75}-y_{73})\\[-10pt]
&{\underline{\qquad\qquad\;\;\,}}\\[2pt]
=\;&y_{75}-y_1\\[2pt]
\le\;&100-1\\[2pt]
=\;&99
\end{align*}
Hence, since there are $37$ summands, whose total is at most $99$, they can't all be at least $3$ (since $37{\times}3 = 111 > 99$).

But since $y_1,...,y_{75}$ are distinct, each of those summands is at least $2$.

So some summand, say $y_{k+2}-y_k$, must equal $2$. It follows that $y_k,y_{k+1},y_{k+2}$ are consecutive integers.
A: Yes it must we can see it by pigeon hole principle. You pick $1,2$ and skip $3$ this way every number is consecutive to another. This way you can pick $66$ numbers. Any number after that must we from the gaps that you left behind.
