6
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ I took the liberty of fixing an issue in your ninth line: $\gcd(k,j)=1$ does not imply that any divisor $d \mid kj$ either has $d \mid k$ and $d \nmid j$ or $d \mid j$ and $d \nmid k$; for instance, $\gcd(5,6) = 1$ yet $15 \mid 30$ does not divide either 5 nor 6. This is true about prime divisors, however, which is enough to conclude $\gcd(kj, k+j) = 1$. $\endgroup$ Mar 29, 2020 at 18:58
  • $\begingroup$ Thanks I understood the problem $\endgroup$
    – aman
    Mar 30, 2020 at 7:20

2 Answers 2

3
$\begingroup$

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

$\endgroup$
3
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ Thanks, I am wondering how you came up with the 222 possibilities? $\endgroup$
    – aman
    Mar 30, 2020 at 7:25
  • 1
    $\begingroup$ Just by brute force in Python. I put the 23 problem pairs (as sets) in a list pairs, then made allp = set.union(*pairs), the set of all integers in any pair. After from itertools import combinations, you can find the number of sets which hit each pair with sum(all(set(blockers) & p for p in pairs) for blockers in combinations(allp, 12)) $\endgroup$ Mar 30, 2020 at 17:08

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .