If $S$ is a set which consists of $12$ elements, what is the maximum number of pairs $(a,b)$ such that $a, b\in S$ and $\frac{b}{a}$ is a prime number?
Problem
Source: 2024 Turkey TST P3
Tags: combinatorics
19.03.2024 00:52
Here is my solution. The answer is 20. Represent the elements of $S$ with the vertices of a graph $G$ and connect two vertices $a$ and $b$ if $(a,b)$ satisfies the condition. Use prime power representations of the numbers, for example $84=2^2\cdot 3^1\cdot 7^1\equiv (2,1,0,1,0,0,\cdots)$. Two vertices are connected if and only if their prime power representations differ by 1 in exactly one position and are the same in all other positions. Example. Two cubes next to each other in 3D, or in other words, divisors of 60 $$\{(i,j,k,0,\cdots): i=0,1,2;j=0,1;k=0,1\}$$ Lemma. $G$ is bipartite. Proof. Sum of the numbers in the prime power representations change parity when moving along an edge in $G$ therefore it can not have an odd cycle. Lemma. $G$ does not contain $K_{2,3}$ as a subgraph. Proof. Assume $a$ and $b$ both have edges with $c,d,e$. Since $a$ and $b$ have at least one common friend, $\frac{a}{b}$ is in one of the form $\frac{p}{q}, \frac{1}{pq}, pq$. $\{\frac{a}{p}=\frac{b}{q},aq=bp\}$, $\{ap=\frac{b}{q},aq=\frac{b}{p}\}$, $\{\frac{a}{p}=bq,\frac{a}{q}=bp\}$ are the possible values for the common friends in these cases respectively. Since none of them contains at least three elements for $c,d,e$, it is a contradiction. I think there are better ways to finish this, but I investigated the few cases which are long to write but easy to think on paper. Case 1: $G$ is 1x11 or 2x10: Even if it is complete, the number of edges does not go over 20. Case 2: $G$ is 3x9: Take the vertices on the 3-vertex side. If the sum of degrees of any two of them exceeds 11, then they would have at least 3 common friends, so there is at most $\left\lfloor\frac{11+11+11}{2}\right\rfloor=17$ edges. Case 3: $G$ is 4x8: Take the vertices on the 4-vertex side. If none of them has at least 6 friends, there would at most $4\times 5=20$ edges. If one of them has at least 6 friends, the each of other three would have at most 4 friends, since otherwise 3 common friends would be formed. In this case, there is at most $6+4+4+4=18$ edges. Case 4: $G$ is 5x7: Take the vertices on the 5-vertex side. If none of them has at least 5 friends, there would at most $5\times 4=20$ edges. If one of them has at least 5 friends, the each of other four would have at most 4 friends, since otherwise 3 common friends would be formed. In this case, there is at most $5+4+4+4+4=21$ edges. However, this case is impossible because the two vertices on the 7-vertex side that are not connected to the vertex of degree 5 on the other side have now 4 common friends. Case 5: $G$ is 6x6: If there is a vertex with degree 5, then at most $5+3+3+3+3+3=20$ edges can be formed. Take a vertex $a$ with degree 4. Any other vertex of degree 4 has to be connected to the two vertices that are not connected to $a$ on the other side. For these two vertices to not have three common friends, the number of vertices with degree 4 on one side can at most be three. In this situation, at most $4+4+4+3+3+3=21$ edges can be formed. This situation is impossible. Since 4-degree vertices are 2 step away from each other, and since adding or subtracting the same thing from every vertex does not change anything, they are either of the form $\{(0,0,0,\cdots),(1,1,0,\cdots),(1,0,1,\cdots)\}$ or $\{(0,0,0,\cdots),(1,1,0,\cdots),(2,0,0,\cdots)\}$. In both cases, $(1,0,0,\cdots)$ has to exists on the other side but it is connected to all three of these 4-degree vertices which is a contradiction.
19.03.2024 11:55
Here is another way to solve this problem. Change $12$ with $n$ and let $f(n)$ be the maximum possible number of pairs. One can see that $f(0)=f(1)=0, f(2)=1, f(3)=2$. Now, let's prove that $$f(m)\leq max_{1\leq x\leq m-1}(f(x)+f(m-x)+\min{(x, m-x)})\text{ for }m\ge 3\text{ ............ }\star$$ Let $S$ be a set with $m$ elements so that there are $f(m)$ such pairs. Take any prime number $p$ dividing at least one element of $S$. We can assume that $p$ does not divide at least one element of $S$ because otherwise you can divide all elements of $S$ by $p$ and repeat this process. Let $H$ be the set of numbers from $S$ that are divisible by $p$. Let $|H|=x$ where $1\leq x\leq m-1$. Let $T=S\setminus H$. Call a pair $(a,b)$ good if $\dfrac ba$ is prime. We can see that there are at most $f(x)$ good pairs $(a,b)$ for which $a,b\in H$ and at most $f(m-x)$ good pairs $(a,b)$ for which $a,b\in T$. Clearly, there is no good pair for which $a\in H$ and $b\in T$. Call a pair $(a,b)$ super good if $\dfrac ba$ is prime and $a\in T, b\in H$. Let's see at most how many super good pairs there can be. Since $p|b$ and $p\not | a$, if the number $\dfrac ba$ is prime, then it must be equal to $p$. Hence, $b$ must be equal to $pa$. Therefore, every element of $H$ can be in at most $1$ super good pair. Similarly, every element of $T$ can be in at most $1$ super good pair. Hence, there are at most $\min{(x, m-x)}$ good pairs. This finishes the proof of $\star$. Now, using $\star$, one can check that $f(4)\leq 4, f(5)\leq 5, f(6)\leq 7, f(7)\leq 9, f(8)\leq 12, f(9)\leq 13, f(10)\leq 15, f(11)\leq 17$ and $f(12)\leq 20$. Finally, for the following set of $12$ numbers, there are $20$ good pairs so the answer is $20$. $$1$$$$2, 3, 5, 7$$$$6, 10, 15, 14, 21$$$$30, 42$$
28.04.2024 02:15
My solution is the same as AnSoLiN except you must scale all the connected portions of $G$ so that all the entries are integral and if their is a negative portion negate it and then multiply by a very big number.