, 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.

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 \max_{1 \le k \le n-1} \{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}$ for the set. One can easily see that number of pairs whose quotient is prime is exactly $\sum_{k=0}^{n-1} g(k)$.