The question is from the 1996 Chinese Mathematical Olympiad. I can't find the solutions anywhere online.
Find the smallest value of $K$ such that any $K$-element subset of $\{1,2,\ldots,50\}$ contains two elements $(a,b)$ such that $a+b \mid ab$.
My first inclination was to find the conditions under which $a+b \mid ab$.
$ a+b \mid ab+b^2$ and $a+b \mid ab+a^2$ for all $(a,b)$.
If $a+b \mid ab$, then $a+b \mid a^2$ and $a+b \mid b^2$, which is not possible if $\gcd(a,b)=1$.
Therefore $\gcd(a,b)>1$.
Let $d = \gcd(a,b)$, $a=kd$, and $b=jd$. Then $\gcd(k,j)=1$.
Then $a+b \mid ab \implies (k+j)d \mid kjd^2 \implies (k+j) \mid kjd$.
$\gcd(k,j)=1$, so any prime divisor $f \mid kj \implies (f \mid k$ and $f \nmid j$) or ($f \mid j$ and $f \nmid k$), so $f\nmid(k+j)$.
Thus $\gcd((kj),(k+j))=1$, so $k+j \mid d$.
If $d>=25$, then either $kd$ or $jd$ must exceed $50$, so we need only consider the possibilities for $0<d<25$.
$d=1,2\implies\emptyset$
$d=3\implies(3,6)$
$d=4\implies (4,12)$
$d=5\implies(5,20),(10,15)$
$d=6\implies(6,12),(6,30)$
$d=7\implies(7,42),(14,35),(21,28)$
$d=8\implies(8,24),(24,40)$
$d=9\implies(9,18),(36,45)$
$d=10\implies(20,30),(10,40)$
$d=11\implies\emptyset$
$d=12\implies(12,24)$
$d=13,14\implies\emptyset$
$d=15\implies(15,30)$
$d=16\implies(16,48)$
$d=17\implies\emptyset$
$d=18\implies(18,36)$
$d=19,20\implies\emptyset$
$d=21\implies(21,42)$
$d=22,23\implies\emptyset$
$d=24\implies(24,48)$
Now, to solve the problem, we need to create the largest possible set containing no $2$ elements from a single set.
This would be equivalent to eliminating as few elements as possible such that no two elements are chosen from the same pair.
Now, from the eleven pairs $(3,6),(4,12),(5,20),(10,15),(7,42),(14,35),(21,28),(8,24),(9,18),(36,45),(16,48)$ there are no elements common to two pairs. Thus, at least $11$ elements must be eliminated.
If ${6,12,20,15,42,35,28,24,18,45,48}$ are eliminated, then every pair has had at least one element eliminated.
Thus, the largest possible subset $S$ such that there are no $a,b\in S : (a+b) \mid ab$ has $50-11=39$ elements.
Thus, the answer is $40$.
Can someone verify if this is a valid method? I am a bit confused if there are any exceptions I have missed.
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$.