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

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.

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

Tags:

Combinatorics

Discrete Mathematics

Pigeonhole Principle

Solution Verification

Related

The way to produce a random but ordered series of numbers? Without Foundation, can axiom of choice be derived from $\forall\alpha\in\mathbf{Ord} (P(\alpha)\text{ can be well ordered})$? Inequality with a High Degree Constraint Given that $x_0$ is a real root of $x^3+px + q = 0$, how can I show that $p^2 \geq 4x_0q$? If $\lim_{x \to \infty} f(x) - xf'(x)$ exists, does $\lim_{x \to\infty} f'(x)$ exist as well? What's the difference between $v = a\cdot t$ and $\vec{v} = \int \vec{a} \, \mathrm dt$ Polynomial bijections from $\mathbb{Q}$ to $\mathbb{Q}$ Minimizing the sum of the six distances determined by four points in the plane, if each distance is at least $d$ USA TST 2018/P1: Prove that the $n^{\text{th}}$ smallest positive integer relatively prime to $n$ is at least $\sigma(n)$ Prove $\int_0^{\infty} \frac{\arctan{(x)}}{x} \ln{\left(\frac{1+x^2}{{(1-x)}^2}\right)} \; \mathrm{d}x = \frac{3\pi^3}{16}$ Find all positive integers $n$ for which $1372n^4 - 3 $ is an odd perfect square. Show that $\cos\big(\frac{2\pi}{n}\big)$ is an algebraic number

Recent Posts