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{align*} 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{align*}$$

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.