0
$\begingroup$

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.

Improve this question
$\endgroup$
6
  • 1
    $\begingroup$ This is not really appropriate for this site, but since I am here, the claim is false. If you name the elements $1, \dots, 115$, then the set of elements that are $1,2,3,4,$ or $5$ (mod $10$) is a counterexample. On the other hand, it is true if you take at least 61 elements. Colour the elements (mod 5). Since each colour class has 23 elements, you can choose at most 12 elements from each colour class. $\endgroup$
    – Tony Huynh
    Commented Oct 25, 2020 at 15:34
  • $\begingroup$ @TonyHuynh Elements 1 and 5 in your solution are exactly 4 apart. $\endgroup$
    – RobPratt
    Commented Oct 25, 2020 at 15:35
  • $\begingroup$ Not according to the definition, 4 elements apart means $a-b=5$ (since $A$ and $F$ are $4$ elements apart). $\endgroup$
    – Tony Huynh
    Commented Oct 25, 2020 at 15:36
  • $\begingroup$ OK, I missed that in the example. I suspect that the OP misinterpreted what 4 apart means. $\endgroup$
    – RobPratt
    Commented Oct 25, 2020 at 15:38
  • $\begingroup$ Thank you for your answer, but since there are 4 elements, namely B, C, D, E in between A and F, this makes A and F 4 elements apart. But thank you for your answer and I will be more aware to post on the appropriate site next time. $\endgroup$
    – kennysliding
    Commented Oct 25, 2020 at 15:38

1 Answer 1

Reset to default
2
$\begingroup$

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.

Improve this answer
$\endgroup$

Not the answer you're looking for? Browse other questions tagged .