Bariz - Problem

Source: JBMO Shortlist 2022

Tags: combinatorics, geometry, Junior, Balkan, shortlist

Lukaluce

27.06.2023 00:35

Let $n \ge 2$ be an integer. Alex writes the numbers $1, 2, ..., n$ in some order on a circle such that any two neighbours are coprime. Then, for any two numbers that are not comprime, Alex draws a line segment between them. For each such segment $s$ we denote by $d_s$ the difference of the numbers written in its extremities and by $p_s$ the number of all other drawn segments which intersect $s$ in its interior. Find the greatest $n$ for which Alex can write the numbers on the circle such that $p_s \le |d_s|$, for each drawn segment $s$.

Answer is $11$. Let's show that $12$ or more are impossible. There should be $6$ even number at least. And $2$ even numbers can't be neighbour. Also there should be edge between any $2$ evens. There is no even numbers between any $2$ consecutive even numbers because $(s:2k-2k+2)$, $d_s=2 \implies p_s \leq 2$. $\implies 2 - 4 - 6 - 8 - 10 - 12-$ Let's look at $3$ and $9$. $3$ and $9$ have at least $3$ edges. So $3$ can't be between any consecutive even numbers. $\implies 3$ is between $n$ and $2$. Similarly $9$ is between $n$ and $2$. Also there is no number between $3$ and $9$. Contradiction.