Japan Mathematical Olympiad Initial Round

Denote by $A$ and $B$ the set of numbers written on the blackboard $A$ and $B$, respectively. Denote also by $|X|$ the number of elements belonging to the set $X$. If we let $$A=\{2,3,4,5,6,8,9,10,12,15,16,18,20\},B=\{7,11,13,17,19\},$$ then we see that arbitrary pair of numbers $(a,b)$ with $a\in A$ and $b\in B$ are relatively prime, and that we have $|A||B|=65$. We will show in the sequel that $65$ is the maximum possible value for the product $|A||B|$.

So, suppose that for some choice of $A$ and $B$, $|A||B|\ge 66$, and we will show that this will lead to a contradiction. From $|A|+|B|\ge 2\sqrt{|A||B|}\ge 2\sqrt{66}$, it follows that we must have $|A|+|B|\ge 17$. Therefore, we conclude that there are at most $2$ numbers among the integers, greater than or equal to $2$ and less than or equal to $20$, which belong neither to $A$ nor to $B$. Hence, at least one number among $6,12,18$ must belong either to $A$ or to $B$. We may suppose without loss of generality that the former is the case. By the assumption of the problem, multiples of a same positive number cannot belong to both $A$ and $B$. Since at least one of the numbers $6,12,18$ belongs to $A$, we conclude that all the multiples of $2$ and all the multiples of $3$ must also belong to $A$. Since there are only six numbers $5,7,11,13,17,19$, among the numbers greater than or equal to $2$ and less than or equal to $20$, which are neither multiples of $2$ nor multiples of $3$, we conclude that $|B|\le 6$ must be satisfied. If we assume that $|B|\le 4$, then we get $|A||B|\le (19-|B|)|B|\le 60$, which contradicts our assumption. Therefore, we must have either $|B|=5$ or $|B|=6$.

When $|B|=5$:

In this case, we must have either $5$ or $7$ in the set $B$. But then at least one of the numbers $10$ or $14$ cannot be in the set $A$, so that we have $|A|\le 13$, which implies that $|A||B|\le 65$, which contradicts our assumption.

When $|B|=6$:

In this case, we have $B=\{5,7,11,13,17,19\}$, so neither $10$ nor $14$ can belong to the set $A$, which means that $|A|\le 9$, and this also leads to the contradiction to our assumption.

Thus we conclude that $65$ is the maximum possible value that the product $|A||B|$ can take.