Maliyah Robles

2022-07-14

Find out whether this sequence can be obtained in this particular order:
Each number from 1 to 2021 occurs twice (1,1,2,2,3,3,....so on). Can we arrange it in such a way that between first occurrence and second occurrence of k there are exactly k numbers?
I can see that numbers 1,1,2,2,3,3 can be arranged like 312132. But I am not able to proceed any further. Please help me here as early as possible. Thank you in advance.

toriannucz

Expert

Step 1
Such a Langford sequence can not exist for $n\equiv 1\phantom{\rule{0.444em}{0ex}}\left(\mathrm{mod}\phantom{\rule{0.333em}{0ex}}4\right)$ or for $n\equiv 2\phantom{\rule{0.444em}{0ex}}\left(\mathrm{mod}\phantom{\rule{0.333em}{0ex}}4\right)$.
To see this, for each number $k\in \left\{1,2,3,\dots ,n\right\}$ define ${P}_{k}$ as the position of the first occurrence of k in the sequence.Per the required condition on our sequence, it follows that ${P}_{k}+k+1$ will be the position of the second occurrence of k in the sequence.
Now... if we were to add up all of the indices of the positions of each number in our sequence, on the one hand adding up the positions of the 1's followed by the positions of the 2's followed by the positions of the 3's and so on... we will have
$\sum _{k=1}^{n}\left({P}_{k}+{P}_{k}+k+1\right)=\frac{1}{2}n\left(n+3\right)+2\sum _{k=1}^{n}{P}_{k}$
On the other hand we could have just added up the indices from left to right within the sequence which is of course $\sum _{k=1}^{2n}k=n\left(2n+1\right)$
Step 2
Now... since both expressions count the sum of the indices they must be equal, and must of course be integers. Let us rearrange the sum so that we have solved for the summation $\sum _{k=1}^{n}{P}_{k}$. In doing so we are left with: $\sum _{k=1}^{n}{P}_{k}=\frac{n\left(3n-1\right)}{4}$
As the summation is a sum of integers, it follows that the RHS must be an integer as well. This happens if and only if $n\equiv 0\phantom{\rule{0.444em}{0ex}}\left(\mathrm{mod}\phantom{\rule{0.333em}{0ex}}4\right)$ or $n\equiv 3\phantom{\rule{0.444em}{0ex}}\left(\mathrm{mod}\phantom{\rule{0.333em}{0ex}}4\right)$.
As a result, since $2021\equiv 1\phantom{\rule{0.444em}{0ex}}\left(\mathrm{mod}\phantom{\rule{0.333em}{0ex}}4\right)$ it follows that no such Langford sequence can exist.
This proved the necessity of the condition that $n\equiv 0\phantom{\rule{0.444em}{0ex}}\left(\mathrm{mod}\phantom{\rule{0.333em}{0ex}}4\right)$ or $n\equiv 3\phantom{\rule{0.444em}{0ex}}\left(\mathrm{mod}\phantom{\rule{0.333em}{0ex}}4\right)$ for the existence of a Langford sequence. It turns out the condition is sufficient as well. For the sufficiency, follow links in the earlier mentioned wiki article.

Do you have a similar question?