Team Selection Test for IMO 2024

Answer: $20$.

Example: $S=\{1,2,3,5,6,7,10,14,15,21,30,42\}$.

Construct a graph $G$ whose vertex set is $S$ and edge set consists of noble pairs. We will show that $|E(G)|=e\le 20$.

We first prove that $G$ is bipartite. Assume that $G$ has an odd cycle. Start from one of the vertices and move along the cycle in clockwise direction. For any prime number $p$ as we pass through an edge we either multiply the number by $p$, divide the number by $p$ or do an operation with some other prime. As we come back to the starting point, number of multiplications by $p$ must be equal to the number of divisions by $p$. Therefore, contribution of any prime $p$ to the cycle is even, and hence the cycle must be an even cycle, contradiction.

Let parts of $G$ be $A$ and $B$ with $|A|=a$, $|B|=b$, $a\le b$. Now consider a $K_{2,2}$ in $G$ with vertices $a_1,a_2\in A$ and $b_1,b_2\in B$. It is easy to see that $\{a_1,a_2\}=\{n,npq\}$ and $\{b_1,b_2\}=\{np,nq\}$ (or vice versa) for some positive integer $n$ and distinct primes $p$ and $q$. Also note that we have $a_1{a}_2=b_1{b}_2$.

Suppose that a $K_{2,3}$ exists in $G$ with vertices $a_1,a_2\in A$ and $b_1,b_2,b_3\in B$. Then $a_1{a}_2=b_1{b}_2=b_1{b}_3$ which implies that $b_1=b_3$, contradiction. Thus $G$ has no $K_{2,3}$. Consequently, sum of degrees of any two vertices in $A$ is at most $b+2$, and hence, we get $e\le a(b+2)/2$. Then, when $a=1,2,3,4$ we get $e\le 20$.

Case 1: $a=5$ and $b=7$. Let $m$ be the largest degree in $A$. If $m=7$, then $e\le 7+4\cdot 2=15$. If $m=6$, then $e\le 6+4\cdot 3=18$. If $m=5$, then the other degrees are at most $4$ and hence $e\le 5+4\cdot 4=21$ and $e=21$ holds only if the remaining four vertices all have degree $4$.

Let $B=\{b_1,\dots ,b_7\}$ and suppose that $b_1,\dots ,b_5$ are adjacent to a vertex in $A$. Then, as $G$ has no $K_{2,3}$, any vertex in $A$ of degree $4$ must be adjacent to both of $b_6$ and $b_7$. But then there occurs to be a $K_{2,3}$, contradiction. Thus, we have $e\le 20$. Finally, if $m\le 4$, then obviously $e\le 20$.

Case 2: $a=b=6$. If $m=6$, then $e\le 6+5\cdot 2=16$. If $m=5$, then $e\le 5+5\cdot 3=20$. If $m\le 3$, then clearly $e\le 18$. Finally, let us consider the case when $m=4$. We will show that $A$ can not have three vertices of degree $4$. Assume $a_1,a_2,a_3\in A$ all have degree $4$. Let the neighbors of $a_1$ be $b_1,b_2,b_3,b_4$. Since $G$ has no $K_{2,3}$, $a_2$ is adjacent to $b_5$ and $b_6$. Let the other two neighbors of $a_2$ be $b_3$ and $b_4$. Again as $G$ has no $K_{2,3}$, we easily see that neighbors of $a_3$ are $b_1,b_2,b_5,b_6$. Note that $a_1,a_2,a_3$ do not have a common neighbor and any two of them belong to some $K_{2,2}$. Suppose $a_1<a_2<a_3$. The ratio $a_1/a_j$ where $1\le j<i\le 3$ is either product or quotient of two distinct primes. As $a_3/a_1=(a_3/a_2)\cdot (a_2/a_1)$, we obtain that $\{a_1,a_2,a_3\}=\{np,nq,nr\}$ or $\{n,npq,npr\}$ for some positive integer $n$ and distinct primes $p,q,r$. But then $a_1,a_2,a_3$ are all adjacent to $n$ or $np$, contradiction.

---

Alternative solution.

Let $f(n)$ be the maximum number of such pairs in a set with $n$ positive integers. We will show that $f(12)\le 20$. By the example in the first solution, then we can conclude that $f(12)=20$.

Note that we can assume that the greatest common divisor of all the numbers in the set is $1$. Let $a/b=p$ be a prime and $a$ and $b$ be from the set. Divide the set into two sets, $A$ consisting of the ones not divisible by $p$, and $B$ consisting of the ones divisible by $p$. Let $x/y=q$ be a prime number. Then we can not have $x\in A$ and $y\in B$. Also note that $x\in B$ and $y\in A$ implies $q=p$ and there exists a unique $x$ for given $y$ and vice versa. Therefore, we obtain the following inequality $$f(n)\le \underset{1\le k\le n-1}{\max }\{f(k)+f(n-k)+\min (k,n-k)\}.$$

Clearly $f(1)=0$ and $f(2)=1$. By using that inequality one can easily obtain $f(12)\le 20$ as desired.

Remark: By using the inequality above one can determine the exact value of $f(n)$. Let $g(k)$ be the number of ones in the binary representation of $k$. Then $$f(n)=\sum _{k=0}^{n-1}g(k).$$ And the example is as follows: Suppose that $n-1$ has $m$ digits in its binary representation. Let $p_1,p_2,\dots ,p_m$ be distinct prime numbers. By adding zeros to the left extend binary representations of $0,1,\dots ,n-2$ to be with $m$ digits. Then for any $0\le k\le n-1$, if its binary representation is $a_1{a}_2\dots a_m$ pick the number ${\prod }_{i=1}^m{p}_i^{a_i^{\prime }}$ for the set. One can easily see that number of pairs whose quotient is prime is exactly ${\sum }_{k=0}^{n-1}g(k)$.