Let $a_1,a_2,a_3,a_4$ be positive integers, with the property that it is impossible to assign them around a circle where all the neighbors are coprime. Let $i,j,k\in\{1,2,3,4\}$ with $i \neq j$, $j\neq k$, and $k\neq i $. Determine the maximum number of triples $(i,j,k)$ for which $$ ({\rm gcd}(a_i,a_j))^2|a_k. $$
Problem
Source: Turkey National Mathematical Olympiad 2018
Tags: number theory
grupyorum
03.12.2018 05:40
In what follows, I assume a triple $(i,j,k)$ and $(j,i,k)$ are the same, which is consistent with the two posts below this. Note that, the number of such triples is at most $12$. First, assume that $(a_i,a_j)>1$ for every $i \neq j$. Consider, $(a_1,a_2,a_3,a_4)=(p^{15},p^7,p^3,p)$ for some fixed prime $p$. One can easily see that, $(a_1,a_2)^2\nmid a_3,a_4$, and $(a_2,a_3)^2 \nmid a_4$, and $(a_1,a_3)^2\nmid a_4$. This gives a total of $8$. Now, assume that there is an example with $\geq 9$ triples. In particular, there is a pair, $(a_i,a_j)$ such that for $k\in \{1,2,3,4\}\setminus \{i,j\}$, $(a_i,a_j)^2\mid a_k$. In particular, take a prime $p$ which divides $a_i$ and $a_j$. Deduce that, $p\mid k$ for every $k\in\{1,2,3,4\}\setminus \{i,j\}$, thus $p\mid a_1,\dots,a_4$. Now, assume without any loss of generality that $v_p(a_1)\geq \cdots \geq v_p(a_4)$, where $v_p(x)$ is the largest power of a prime $p$ dividing $x$. Note that, $v_p((x,y))=\min\{v_p(x),v_p(y)\}$, we deduce that $(a_1,a_2)^2$ cannot divide $a_3$ and $a_4$, $(a_1,a_3)^2$ cannot divide $a_4$, and $(a_2,a_3)^2$ cannot divide $a_4$. Hence, we would have a total of $8$ triples.
The second case assumes the existence of a pair $(i,j)$ with $(a_i,a_j)=1$, and incorporate the problem's condition. Now, there is clearly a pair, that is not coprime. Suppose without loss of generality we begin with $(a_1,a_2)$. Now, put $a_1$ and $a_2$ on opposite sides. We deduce that, one of the following, $(a_1,a_3),(a_1,a_4),(a_2,a_3),(a_2,a_4)$ must be a pair that is not coprime. Suppose, without loss of generality that it is $(a_1,a_3)>1$ and $(a_1,a_2)>1$. Now, assume that, under this condition, we have at least $11$ pairs. Now, consider triples (in $(i,j,k)$ order), $(a_1,a_3,a_2),(a_1,a_3,a_4)$, $(a_1,a_2,a_3)$, and $(a_1,a_2,a_4)$. In this case, we observe that at least three of them are contained, in particular, we land on the previous case (that, there is a prime dividing all the numbers). Hence, we can get at most $10$ pairs. Now, if $10$ is the maximum, then there are a few cases to study.
$i)$ First, if both of the missing triples are among the triples above. In this case, if, say, the missing two triples share the same first two coordinates, we again arrive at the previous case.
$ii)$ Next, assume that, missing two triples do not have the same first coordinate. We deduce, say, without loss of generality $(a_1,a_3)^2\mid a_2$. This means, there is a $p$ dividing $a_1,a_2,a_3$. Now, it must be the case that $(a_2,a_3)^2 \mid a_1,a_4$, which again yields that there is a prime that divides all four, again, back to previous case.
$iii)$ Now, assume that only one of the missing triples are among the four triples above. Then, we can similarly deduce the desired contradiction.
This shows the maximum is at most $9$. I'm a bit tired at this moment to continue for $9$, but I presume this case will also be quite similar.
In my opinion, the moves that I've used for this problem are on par with the tricks used for problem 5 of IMO 2018.
Relkuyh
04.12.2018 08:48
I think the answer must be $16$ since $(2,3,5,15)$ quadruple cannot be written on a circle that satisfies the given property and this quadruple satisfies $16$ triples which are $$(2,3,5), (3,2,5), (2,3,15), (3,2,15), (2,5,3), (5,2,3), (2,5,15), (5,2,15), (3,5,2), (5,3,2), (3,5,15), (5,3,15), (2,15,3), (15,2,3), (2,15,5), (15,2,5)$$ Note: The answer is $16$ when $(a,b,c)$ and $(b,a,c)$ are considered as different triples.
Relkuyh
04.12.2018 09:49
Also we can show that maximum number is 16. I have a solution for that but it is too long for me to write it from my phone and I'm a bit lazy.
ThE-dArK-lOrD
05.12.2018 08:36
grupyorum wrote: In my opinion, the moves that I've used for this problem are on par with the tricks used for problem 5 of IMO 2018. Hmm not quite agree, I see this as just some case bash. First, note that $1,2,3,6$ gives us $16$ triples. From now on, we'll instead consider the tuple $(\{ a_i,a_j\} ,a_k)$ instead. Suppose to the contrary that there exists $a_1,a_2,a_3,a_4$ that creates at least $9$ such tuples from the total of $12$. This means there're at most three possible $(\{ a_i,a_j\} ,a_k)$ that $(\gcd (a_i,a_j))^2\nmid a_k$. We call such tuple bad. Back to the given condition of $a_1,a_2,a_3,a_4$. One can see that this is nothing more than, WLOG assumed, $\gcd (a_1,a_2)$ and $\gcd (a_1,a_3)$ are both greater than one. Now here comes the case bash. First case: there exists pairwise distinct indices $i_1,i_2,i_3$ and prime $p$ that $p\mid a_{i_1},a_{i_2},a_{i_3}$. WLOG that $\nu_p (a_{i_1})\geqslant \nu_p (a_{i_2}) \geqslant \nu_p(a_{i_3})>0$. Checking $\nu_p$s, one get that $(\{ a_{i_2},a_{i_3} \} ,a_{i_1})$ is already a bad tuple. If $p\nmid a_{i_4}$ (the other $a_i$s), we get that the tuples $(\{ a_m,a_n\} ,a_{i_4})$ are bad for all $\{ m,n\} \subset \{ i_1,i_2,i_3\}$. This results in more than three bad tuples. So, $p\mid a_{i_4}$. In other words, $p\mid a_1,a_2,a_3,a_4$. WLOG that $\nu_p (a_1)\geqslant \nu_p (a_2)\geqslant \nu_p(a_3) \geqslant \nu_p(a_4)>0$. We get that all of $( \{ a_1,a_2\} ,a_3) ,( \{ a_1,a_2\} ,a_4),( \{ a_1,a_3\} ,a_4) ,( \{ a_2,a_3\} ,a_4)$ are bad tuples, contradiction. Second case: the negation of the first one. Back to our $\gcd (a_1,a_2),\gcd (a_1,a_3)>1$. Denote $d_2=\gcd (a_1,a_2)$ and $d_3=\gcd (a_1,a_3)$. We get that, if $d_2^2\mid a_3$, there exists prime $p$ that $p\mid d_2\mid a_1,a_2,a_3$, contradiction. So $d_2^2\nmid a_3$. Similarly, $d_3^2\nmid a_2$. This already amounted to two bad tuples. Then, note that, we also can't have $d_2^2\mid a_4$. Because else we'll get that there exists prime $p$ that $p\mid d_2\mid a_1,a_2,a_4$. So, $(\{ a_1,a_2\} ,a_4)$ is another bad tuple. But then so does $(\{ a_1,a_3\} ,a_4)$. Already four bad tuples, contradiction.
egxa
27.07.2023 16:53
$1:$ Easy to see $(1,2,3,6)$ supplies $16$ $2:$ WLOG we can assume $(a_1,a_2),(a_1,a_3)>1$ $3:$ If every permutation of $(a,b,c)$ satisfies divisibility any two of them are relatively prime each other. $4:$ And examine the situations.