Will 75 element subset S of $\{1, 2, 3, .\ldots, 100\}$ must contain three consecutive integers?

Question

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.

Answer 1

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

Answer 2

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.

Answer 3

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.