National Math Camp 2020 Exam 2 Problem 4

Discussion on Bangladesh National Math Camp
User avatar
FuadAlAlam
Posts: 23
Joined: Wed Sep 16, 2020 11:10 am
Location: Dhaka, Bangladesh
Contact:

National Math Camp 2020 Exam 2 Problem 4

Unread post by FuadAlAlam » Mon Dec 07, 2020 1:37 pm

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

User avatar
FuadAlAlam
Posts: 23
Joined: Wed Sep 16, 2020 11:10 am
Location: Dhaka, Bangladesh
Contact:

Re: National Math Camp 2020 Exam 2 Problem 4

Unread post by FuadAlAlam » Mon Mar 01, 2021 12:52 pm

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

Post Reply