If $15$ distinct integers are chosen from the set $\{1, 2, \dots, 45 \}$, some two of them differ by $1, 3$ or $4$.

Question

$\blacksquare~$ Problem: If $15$ distinct integers are chosen from the set $\{1, 2, \dots, 45 \}$, some two of them differ by $1, 3$ or $4$.

$\blacksquare~$ My Approach:

Let the minimum element chosen be $n$. Then $n + 1 , n + 3 , n + 4 $ can't be taken.

We make a small claim.

---

---

$\bullet~$ Claim: In a set of $~7$ consecutive numbers at most $2$ numbers can be chosen.

---

$\bullet~$ $\textbf{Proof:}$ Let us name the elements of the set as $\{ 1,2,3,\dots,7 \}$.

Now let's consider the least element is chosen. If the least element is $1$, then $2,4,5$ can't be chosen.

So we are left with $3, 6, 7$.

$\circ~$ If $~3~$ is chosen, then $6, 7$ can't be in the set. And if $~3~$ is not chosen, then only any one of the 2 elements $\{ 6, 7 \}$ be chosen. So, a maximum of $2$ elements can be chosen in this case.

$\circ \circ~$ If the least element is $2,$ then $3, 5, 6$ can't be there in the set. So, possible elements are 4, 7. So, one of these two can be chosen. Then, a maximum of 2 elements can be chosen in this case.

$\circ \circ~$ If the least element is $3$, then $4,6,7$ gets cancelled. so only $5$ is left in the set i.e., $2$ elements at most.

$\circ \circ~$ If the least element is $4,$ then $5,7$ gets cancelled. So the only element left is $6$.

Similarly,

$\circ \circ~$ If $5$ is the least element then $6$ gets cancelled and only $7$ is left. i.e., two elements. If the least element is either $6$ or $7$, then there is only one element.

So a maximum of two elements in a set of $7$ consecutive elements can be chosen.

Hence, the proof of the claim is done!

---

---

So, for $42$ elements, a maximum of $2 \times 6 = 12$ can be taken. However, $3$ more elements are required from $3$ more consecutive elements, which is not possible since only 2 elements at most can be chosen from a set of 3 consecutive elements.

So, a $14$ element subset can be formed such that, no two of them differ by $1, 3, 4$. Hence the $15$th element is one of the cancelled elements, that is, there exists a pair with their difference being $1, 3$ or $4.$

Hence, done!

---

Please check the solution for glitches and give new ideas too :).

Answer 1

It is a nice argument, and you have explained it very clearly, so well done.

If you are looking for improvements, and you want it to be a bit more formal, I would make two suggestions:

1. You are very thorough proving the claim, going through all the cases, which is great. However you could shorten the proof of the claim by saying:

"If the least element is $x$, then we may subtract $x-1$ from all the numbers without changing their differences or the number of integers. Thus without loss of generality we may assume the least element is $1$."

Then you do not need to consider the other cases.

2. The last part of the proof (after the claim is proved) is not as thorough as the proof of the claim. You assume that for $k=0,\cdots,5$ the numbers $7k+1,7k+3$ are selected, without justifying that this is optimal. It is obvious in a way, but for a formal proof you should justify this by saying something like:

"Pick the smallest $k$ where $7k+1, 7k+3$ are not picked. Then replace the numbers in $\{7k+1,\cdots 7k+7\}$ that are picked with $7k+1, 7k+3$. From the claim we know that we have not reduced the number of integers. Also, we have not created any new differences of $1,3,4$."

Then finish the argument with your second to last paragraph. I would reword the first sentence slightly: "So of the first $42$ elements, we may assume these $12$ are picked."

I would lose the last paragraph as it is not needed.

Answer 2

Nice proof!

In the optimal case, go up in $2$s wherever possible. You would start with $1$ and pick the smallest possible number, that is, $3$. We can't add $2$ again as that would be $1+4$, therefore we add the next smallest possible, $5$ to get our next number $8$. We can then add $2$ again, and the pattern continues:

$$1,3,8,10,15,17,22,24,29,31,36,38,43,45$$

Via this strategy we only pick $14$ numbers, so $15$ is impossible without violating the $1,3,4$ difference.

Answer 3

Here's a shorter version which however relies on the same ideas as your and Rhys Hughes' approach.

Let's assume we can choose $15$ integers whose mutual differences are never $0,1,3$ or $4$, and call them $x_1 <x_2 < \dots < x_{15}$ in ascending order.

Claim: For all $1 \le i \le 13$, we have $x_i +7 \le x_{i+2}$.

Proof of claim: Let's make a case distinction about what $x_{i+1}-x_i$ is. Since it cannot be $0,1,3$ or $4$, the only cases are:

• First case, $x_{i+1} - x_{i} =2$. Then if we also had $x_{i+2} - x_{i+1} = 2$ we would have $x_{i+2}-x_i =4$ which was excluded. So $x_{i+2}-x_{i+1}$, since it cannot be $0,1,2,3,4$ must be $\ge 5$ which implies the claim.
• Second case, $x_{i+1}-x_i \ge 5$. Then since $x_{i+2}-x_{i+1} \neq 0,1$ it must be $\ge 2$ and the claim follows.

The claim is proven.

Now it follows iteratively that $x_3 \ge x_1 +7$, $x_5 \ge x_3+7 \ge x_1+14$, ..., $$x_{15} \ge x_1+49$$ which of course contradicts $1 \le x_1 \le x_{15} \le 45$. Actually this shows that you cannot even select $15$ such integers from the set $\{1, ..., 49\}$.