$a+b \mid ab$ from CMO 1996

It seems you missed listing the problem pairs $(30,45)$ for $d=15$, with $30 + 45 \mid 30\cdot45$, and $(12,36)$ for $d=12$, with $12 + 36 \mid 12\cdot36$.

Your proposed subset $S = \{1,\dotsc,50\} - \{6,12,15,18,20,24,28,35,42,45,48\}$ contains the pair $(10,40)$ with $10 + 40 \mid 10\cdot40$, so doesn't provide a counterexample.

Additionally removing 40 is enough to leave no problem pair, so there is a set $S'$ of 38 elements with no $a, b \in S'$ such that $a + b \mid ab$.

No choice of 11 elements hits all 23 problem pairs, so $K = 39$ should suffice to guarantee such a pair $(a,b)$.

There are many other choices of 12 numbers which you can remove to leave a problem-pair-free set, e.g. $\{3, 5, 7, 9, 10, 12, 14, 16, 21, 24, 30, 36\}$; in fact there are 222 possibilities.


Your approach is good, but you have missed some pairs of numbers in your list. Perhaps it would help to further characterise the pairs $(a,b)$ for which $a+b\mid ab$ as follows:

You have $d:=\gcd(a,b)>1$, and writing $a=rd$ and $b=sd$ for coprime positive integers $r$ and $s$ you indeed find that $r+s\mid d$. This means $d=(r+s)t$ for some positive integer $t$. Conversely, if $r$, $s$ and $t$ are positive integers and $r$ and $s$ are coprime, then the pair $(a,b)$ where $$a:=r(r+s)t\qquad\text{ and }\quad b:=s(r+s)t,$$ satisfies $a+b\mid ab$. So this parametrization covers all pairs. Now listing all pairs is easy:

Without loss of generality $a<b$, or equivalently $r<s$, and so $$b=s(r+s)t\geq s^2+s.$$ Because $b\leq50$ we have $s\leq 6$ as well as $1\leq r<s$, and we find the pairs $$\begin{array}{r|rrrrr} (r,s)&(1,2)&(1,3)&(2,3)&(1,4)&(3,4)\\ \hline (a,b)&(3,6)&(4,12)&(10,15)&(5,20)&(21,28)\\ \\ (r,s)&(1,5)&(2,5)&(3,5)&(4,5)&(1,6)\\ \hline (a,b)&(6,30)&(14,35)&(24,40)&(36,45)&(7,42)\\ \end{array}$$ and multiples thereof. I have omitted the last pair with $(r,s)=(5,6)$ because then $(a,b)$ is out of range. From the above you should find a total of $23$ pairs, where of course some integers are contained in more than one pair. Now indeed the problem is equivalent to finding the smallest set that contains at least one integer from each pair.


Suppose $S$ is such a minimal set. The integers $14$ and $35$ only occur in the pair $(14,35)$, so one of both is contained in $S$ and replacing one by the other yields another minimal set, so without loss of generality $14\in S$, and there remain $22$ pairs. There are $8$ integers that occur in precisely one of these $22$ pairs. If $S$ contains one of these integers, then replacing it by its partner yields another minimal set, so without loss of generality $$6,12,18,20,21,24,42,48\in S.$$ This leaves only the five pairs $$(10,15),\quad (10,40),\quad(15,30),\quad(30,45),\quad(36,45).$$ No integer is contained in more than two of these pairs, so $S$ contains at least three more integers. And indeed with $10,30,45\in S$ we see that $S$ contains one integer from each pair. This shows that $|S|=12$, and hence $K=39$.