Baltic Way 2020 · Problem 20

We use induction on $k = |A| + |B| - 1$. For $k = 3$ we have $|A| = |B| = 2$. Let $A = \{x, y\}$, $B = \{z, t\}$. Then $S$ consists of three numbers from the set $\{xz, yz, xt, yt\}$. Relabelling the elements of $A$ and $B$ if necessary, we can assume without loss of generality that the missing number is $yt$. Then $xz, xt, yz \in S$ and $xz \mid xt \cdot yz$ which concludes the base case of induction.

For the inductive step, suppose the thesis holds for some $k-1 \ge 3$. Since $k = |A|+|B|-1 \ge 4$, we have that $\max(|A|, |B|) \ge 3$, WLOG assume $|A| \ge 3$. Since the set $S$ consists of $k = |A|+|B|-1 > |A|$ elements, by pigeonhole principle there exists a number $x \in A$ which appears as the first of the two factors of at least two elements of $S$. So, there exist $y, z \in B$ with $xy, xz \in S$. If there exists $t \in A \setminus \{x\}$ such that $ty \in S$ then we are done because $xy \mid xz \cdot ty$. If there exists no such $t$ then apply the inductive hypothesis to the sets $A \setminus \{x\}$, $B$ and $S \setminus \{xy\}$.