Page 1 of 1

National Math Camp 2020 Exam 2 Problem 4

Posted: Mon Dec 07, 2020 1:37 pm
by FuadAlAlam
$2015$ positive integers are arranged on a circle. The difference between any two adjacent numbers equals their greatest common divisor. Determine the maximal value of $N$ which divides the product of all $2015$ numbers, regardless of their choice.

Re: National Math Camp 2020 Exam 2 Problem 4

Posted: Mon Mar 01, 2021 12:52 pm
by FuadAlAlam
It is easy to check that at least one of the two adjacent numbers is even. So, there are at least $1008$ even numbers on the circle. It is also easy to check that there exists at least one number which is divisible by $4$, because there exists at least one pair of consecutive numbers both of which are even. Again, if there was no positive integer divisible by 3, there would be two adjacent numbers which are both same modulo $3$, but not divisible by $3$. This leads to a contradiction. Therefore, at least one of the integers is divisible by $3$. Thus, $N \geq 3 \times 2^{1009}$.

However, the following two sequences yield that $N \leq 3 \times 2^{1009}$
$\{ 2, 4, 2, 4, 2, 4, \ldots, 2, 4, 3 \} , \{ 2, 3, 2, 3, 2, 3, \ldots, 2, 3, 4 \}$

Therefore, the maximal value of N is $3 \times 2^{1009}$.