GCD de pares adyacentes asume todos los valores posibles

Question

Dado un entero positivo fijo $n$. Considerar el número $1,2,\ldots,2n$. El MCD de cualquier pareja es uno de los $1,2,\ldots,n$. Supongamos que todos los $2n$ números se colocan alrededor de un círculo. Es posible que todos los $n$ posible GCDs son alcanzados por algún par de adyacentes de números en el círculo?

Por ejemplo:

$n=1$: $1$ $2$

$n=2$: $1$ $3$ $2$ $4$

$n=3$: $1$ $5$ $2$ $4$ $3$ $6$

$n=4$: $1$ $7$ $2$ $5$ $3$ $6$ $4$ $8$

En particular, tenga en cuenta que $n$ e $2n$ siempre deben ser adyacentes, ya que la única forma posible pareja con MCD $n$.

[Fuente: la competencia rusa problema]

Answer 1

Sugerencia: $\gcd (k, 2k) = k$.

Por lo tanto, solo debe asegurarse de que para todos los enteros$i \leq n$,$i$ esté al lado de$2i$.

Organízalos como$1, 2, 4, 8, \ldots, 3, 6, 12, \ldots, 5, 10, 20, \ldots, 7, 14, 28, \ldots, 9, 18, 36, \ldots$