4
$\begingroup$

Given a fixed positive integer $n$. Consider the numbers $1,2,\ldots,2n$. The GCD of any pair is one of $1,2,\ldots,n$. Suppose that all $2n$ numbers are placed around a circle. Is it possible that all $n$ possible GCDs are achieved by some pair of adjacent numbers in the circle?

For example:

$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$

In particular, note that $n$ and $2n$ always need to be adjacent, since they form the only possible pair with GCD $n$.

[Source: Russian competition problem]

$\endgroup$
1
$\begingroup$

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

So, you just need to ensure that for all integers $i \leq n$, $i$ is next to $2i$.

Arrange them as $1, 2, 4, 8, \ldots, 3, 6, 12, \ldots, 5, 10, 20, \ldots, 7, 14, 28, \ldots, 9, 18, 36, \ldots$

$\endgroup$
  • $\begingroup$ But in that arrangement, $6$ is not next to $12$, and $10$ is not next to $20$. $\endgroup$ – simmons Oct 29 '14 at 4:01
  • $\begingroup$ @simmons Opps. Typo. Fixed $\endgroup$ – Calvin Lin Oct 29 '14 at 4:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.