Assuming we have a ordered list of 115 elements, if we select 60 elements from the list, prove that the interval for **at least** 2 selected elements are *exactly* 4 elements apart.


Example:


`A B C D E F G...`


Then A and F are 4 elements apart


I tried to find the probability that an element being selected, which is $12/23$ and I tried to do ${12/23}^{60}$ to prove the interval but end up no luck.


I also tried to do counter proof to find the combination of $1, 2, 3, 5, ...$ intervals but I don't think that direction is correct.


Can anyone help and thanks in advance.



Prove the the interval of selected elements in a list is exactly 4
You can solve the problem via integer linear programming as follows. For $i\in\{1,\dots,115\}$, let binary decision variable $x\_i$ indicate whether $i$ is selected. For $i\in\{1,\dots,111\}$, let binary decision variable $y\_i$ represent $x\_i x\_{i+4}$. The problem is to minimize $\sum\_{i=1}^{111} y\_i$ subject to
\begin{align}
\sum\_{i=1}^{115} x\_i = 60 \tag1 \\
x\_i + x\_{i+4} - 1 &\le y\_i &&\text{for $i\in\{1,\dots,111\}$} \tag2
\end{align}
Constraint $(1)$ selects $60$ elements.
Constraint $(2)$ enforces $x\_i \land x\_{i+4} \implies y\_i$.


The minimum turns out to be $1$, even if you relax integrality, and the linear programming dual variables provide a certificate of optimality.




---


For the clarified interpretation of *four apart*, change $4$ to $5$ and $111$ to $110$ above. The resulting minimum is instead $0$, as in @TonyHuynh's counterexample.


