SELECTION TESTS FOR THE 2019 BMO AND IMO

The required maximum is $\left(\genfrac{}{}{0ex}{}{m-1}{2}\right)n^2$, and is achieved if, for instance $$A_k=\{a^{(k-1)n+1},a^{(k-1)n+2},\dots ,a^{kn}\},k=1,\dots ,m-1,$$

For brevity, an ordered pair $(a,b)$ satisfying the conditions in the statement will be called suitable. We show that the number of suitable pairs does not exceed $\left(\genfrac{}{}{0ex}{}{m-1}{2}\right)n^2$. For every $m$-tuple $(a_1,\dots ,a_m)$, where $a_k$ is a member of $A_k$, $k=1,\dots ,m$, let $k(a_1,\dots ,a_m)$ be the number of suitable pairs $(a_i,a_j)$ it contains. We show by induction on $m$ that $k(a_1,\dots ,a_m)\le \left(\genfrac{}{}{0ex}{}{m-1}{2}\right)$. Since there are exactly $n^m$ $m$-tuples, and each suitable pair is contained in exactly $n^{m-2}$ such, the conclusion follows. The case $m=3$ is easily dealt with. Let $m\ge 4$ and fix an $m$-tuple $(a_1,\dots ,a_m)$, $a_k\in A_k$, $k=1,\dots ,m$; without loss of generality, we may and will assume that $a_1$ is the largest entry. The $(m-1)$-tuple $(a_1,\dots ,a_{m-1})$ then satisfies the induction hypothesis: $a_2$ does not divide $a_1$, $a_3$ does not divide $a_2$, and so on and so forth, $a_{m-1}$ does not divide $a_{m-2}$, and, by maximality, $a_1$ does not divide $a_{m-1}$. We show that the number of suitable pairs containing $a_m$ does not exceed $m-2$. It then follows that $k(a_1,\dots ,a_m)\le k(a_1,\dots ,a_{m-1})+m-2\le \left(\genfrac{}{}{0ex}{}{m-2}{2}\right)+m-2=\left(\genfrac{}{}{0ex}{}{m-1}{2}\right)$, as desired. Notice that, for each $k$ in the range $1$ through $m-1$, at most one of the pairs $(a_k,a_m)$, $(a_m,a_k)$ is suitable. If neither $(a_k,a_m)$ nor $(a_m,a_k)$ is suitable for some $k$, then the number of suitable pairs containing $a_m$ is clearly at most $m-2$. Otherwise, since the pairs $(a_m,a_k)$ and $(a_{k+1},a_m)$, $k=1,\dots ,m-2$, are not simultaneously suitable, and the pair $(a_1,a_m)$ is certainly not suitable, by maximality of $a_1$, it follows that the pairs $(a_m,a_k)$, $k=1,\dots ,m-1$, are all suitable, contradicting the fact that $a_m$ does not divide $a_{m-1}$. This ends the proof.