For which integers $n \geq 4$ is the following procedure possible? Remove one number of the integers $1,2,3,\dots,n+1$ and arrange them in a sequence $a_1,a_2,\dots,a_n$ such that of the $n$ numbers \[ |a_1-a_2|,|a_2-a_3|,\dots,|a_{n-1}-a_n|,|a_n-a_1| \]no two are equal.
Problem
Source: Bundeswettbewerb Mathematik 2017, Round 2 - #1
Tags: combinatorics, combinatorics unsolved, Sequence, bundeswettbewerb
05.09.2017 13:43
05.09.2017 13:54
quangminhltv99 wrote: and by removing one of them, there are at most $n-1$ differences left, so it is impossible No! You are removing one of the numbers, but that does not necessarily mean that you remove one possible difference. Of course, if you remove $1$ or $n+1$, this would be true, but e.g. for $n=4$, we can remove $4$ and are left with $1,2,3,5$ which we can arrange as $a_1=1, a_2=3, a_3=2, a_4=5$ and we are fine. In fact, by considering the sum of these differences $\mod 2$, we easily get that $n \equiv 0 \mod 4$ or $n \equiv 3 \mod 4$ and the hard part of the problem is to find the constructions for these cases.
05.09.2017 16:37
I was asked to post a solution, so here we go. Quite difficult for a #1.
29.12.2017 23:13
Kezer wrote: I was asked to post a solution, so here we go. Quite difficult for a #1.
Could you please explain your comparison modulo 2 ?
29.12.2017 23:18
omarius wrote: Could you please explain your comparison modulo 2 ? Note that modulo $2$ we have $\vert x\vert=x$. So $\vert a_1-a_2\vert+\dotsc+\vert a_n-a_1\vert$ is even. So $n(n+1)$ must be divisible by $4$ which is the case iff $4 \mid n$ or $4 \mid n+1$.