26th Turkish Mathematical Olympiad

Answer: 16. Note that if $(a_1,a_2,a_3,a_4)=(1,2,3,6)$, there are 16 triples satisfying conditions: (1, 2, 3), (1, 2, 6), (1, 3, 2), (1, 3, 6), (1, 6, 2), (1, 6, 3), (2, 3, 6), (2, 3, 1), (2, 1, 3), (2, 1, 6), (3, 1, 2), (3, 1, 6), (6, 1, 2), (6, 1, 3), (3, 2, 6), (3, 2, 1). Now we will show that the number of triples satisfying the conditions can not be 17. The total number of ordered triples is $4\cdot 3\cdot 2=24$. We can partition these triples into 8 disjoint sets each of the form $\{(i,j,k),(j,k,i),(k,i,j)\}$ where $i,j,k$ are pairwise distinct. By Pigeonhole Principle, among 17 triples there are all triples from at least one of these sets. Therefore, for a permutation $(a,b,c,d)$ of $(a_1,a_2,a_3,a_4)$, we get $$(\text{gcd}(a,b){)}^2\mid c,(\text{gcd}(b,c){)}^2\mid a,(\text{gcd}(c,a){)}^2\mid b.$$ Let us prove that $\text{gcd}(a,b)=\text{gcd}(b,c)=\text{gcd}(c,a)=1$. For a prime number $p$ and a nonnegative integer $\alpha$, let $p^{\alpha }\mid \text{gcd}(a,b)$. In this case, we get $$\begin{array}{rlr}{p}^{2\alpha }\mid c& \Rightarrow p^{\alpha }\mid \text{gcd}(b,c)\Rightarrow p^{2\alpha }\mid a& \Rightarrow p^{\alpha }\mid \text{gcd}(c,a)\\ & \Rightarrow p^{2\alpha }\mid b\Rightarrow p^{2\alpha }\mid \text{gcd}(a,b)& \end{array}$$

and hence $\alpha =0$. Therefore, $\gcd (a,b)=1$. In a similar way, we can show that $\gcd (b,c)=\gcd (c,a)=1$. If $d$ is coprime with two of $a,b,c$ then we can arrange $a,b,c,d$ on a circle so that neighbors are coprime. (Firstly we put $a,b,c$ arbitrarily. Then we put $d$ between the ones which are coprime with $d$.) Consider the case where $d$ is not coprime with at least two of $a,b,c$. Without the loss of generality, we assume that $\gcd (b,d)>1$ and $\gcd (c,d)>1$. Then we have $$(\gcd (b,d){)}^2\mid a\Rightarrow \gcd (a,b)>1$$ $$(\gcd (b,d){)}^2\mid c\Rightarrow \gcd (b,c)>1$$ $$(\gcd (c,d){)}^2\mid a\Rightarrow \gcd (a,c)>1$$ $$(\gcd (c,d){)}^2\mid b\Rightarrow \gcd (b,c)>1.$$ This means that there are at least 8 many $(i,j,k)$ triples not satisfying $(\gcd (a_i,a_j){)}^2\mid a_k$. It follows that the number of triples satisfying the conditions can not be greater than 16.