Existence of a particular partition of a set of integers

Question

Given an integer $\ell\ge1$, prove that for all even integers $n\ge 2\ell$ there exist a partition of the set $\{1,\dots,n\}$ into sets $A_1,\dots,A_{\frac{n}{2}}$, $A_i=\{a_{2i-1},a_{2i}\}$ such that $|A_i|=2$ and $|a_{2i}-a_{2i-1}|\ge\ell$ for all $i=1,\dots,\frac{n}{2}$.

I managed to prove the case $n=2\ell$, in such case we can consider the sets $A_i=\{i,i+\ell\}$, for all $i=1,\dots,\frac{n}{2}=\ell$. Then I thought to proceed by induction, but I don't see how to proceed from here.

Finally, one could consider the generalized problem: consider two integers $k,\ell\ge 1$, and prove that for integers $n\ge k\ell$ such that $k$ divides $n$ there exist a a partition of the set $\{1,\dots,n\}$ into sets $A_1,\dots,A_{\frac{n}{k}}$, $A_i=\{a_{ki-(k-1)},a_{ki-(k-2)},\dots,a_{ki}\}$ such that $|A_i|=k$ and $|a_{ki-(k-1)}-a_{ki-(k-2)}|,|a_{ki-(k-2)}-a_{ki-(k-3)}|,\dots,|a_{ki-1}-a_{ki}|\ge\ell$ for all $i=1,\dots,\frac{n}{k}$. In such case, one could consider for $n=k\ell$ the sets $A_i=\{i,i+\ell,\dots,i+(k-1)\ell\}$ and then proceed by induction.

Any help is appreciated.

Answer 1

In the first case, you can induct by shifting a partition of $\{1,\dots,n-2\}$ to partition $\{2, \dots, n-1\}$ instead, then taking $A_{n/2} = \{1,n\}$.

But it's probably easier to copy your construction and let $A_i = \{i, i+n/2\}$ for $i=1, \dots, n/2$, which works for all even $n \ge 2\ell$.

Similarly, for the general problem, we could let $A_i = \{i, i+n/k, \dots, i + (k-1)n/k\}$ and check that this satisfies the condition you want once $n \ge k\ell$.

Another inductive step that works for both problems is to

1. Let $A_{n/k}$ be an arbitrary set satisfying the condition, and
2. Define $A_1, \dots, A_{n/k-1}$ by taking a partition of $\{1, \dots, n-k\}$ but replacing each value $i$ by the $i^{\text{th}}$ element of $\{1, \dots, n\} \setminus A_{n/k}$.

This operation can only increase gaps between elements, so the result is a valid partition.