If $15$ distinct integers are chosen from the set $\{1, 2, \dots, 45 \}$, some two of them differ by $1, 3$ or $4$. $\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 :).
 A: 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:

*

*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.


*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.
A: 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.
A: 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\}$.
