Let $A$ and $B$ be two non-infinite sets of natural numbers, each of which contains at least 3 elements. Two numbers $a\in A$ and $b\in B$ are called "harmonious", if they are not coprime. It is known that each element from $A$ is not harmonious with at least one element from $B$ and each element from $B$ is harmonious with at least one from $A$. Prove that there exist $a_1,a_2\in A$ and $b_1,b_2\in B$ such that $(a_1,b_1)$ and $(a_2,b_2)$ are harmonious but $(a_1,b_2)$ and $(a_2,b_1)$ are not.
Problem
Source: V International Festival of Young Mathematicians Sozopol 2014, Theme for 10-12 grade
Tags: combinatorics, Sets, relations