Let be two natural numbers $ m,n, $ and $ m $ pairwise disjoint sets of natural numbers $ A_0,A_1,\ldots ,A_{m-1}, $ each having $ n $ elements, such that no element of $ A_{i\pmod m} $ is divisible by an element of $ A_{i+1\pmod m} , $ for any natural number $ i. $ Determine the number of ordered pairs $$ (a,b)\in\bigcup_{0\le j < m} A_j\times\bigcup_{0\le j < m} A_j $$such that $ a|b $ and such that $ \{ a,b \}\not\in A_k, $ for any $ k\in\{ 0,1,\ldots ,m-1 \} . $ Radu Bumbăcea
Problem
Source: Romanian TST for 2019 IMO
Tags: set theory, number theory
03.10.2019 05:12
I think that the problem should ask to determine the maximum number of ordered pairs. In this case, we claim that the answer is $\binom{m-1}{2} n^2.$ To construct, essentially just let everything in $A_i$ divide everything in $A_{i+1}$, for each $1 \le i \le m-2.$ Then just pick a huge prime $P$ and let $A_m$ consist of the numbers $\{p, p^2, \cdots, p^n\}.$ As long as $1$ is not in any of the $A_i$'s, the details can be easily worked out. Now, we'll show that this is optimal. Lemma. In any acyclic digraph on $m$ vertices labeled $1, 2, \cdots, m$ with $> \binom{m-1}{2}$ edges, there exists an $i$ so that there exists a path from $i$ to $i+1.$ (Here indices are modulo $m$). Proof. We'll prove the result by induction on $m.$ When $m = 2, 3$, this is obvious. Suppose now that it holds for $m = k.$ When $m = k+1$, assume the contrary, for contradiction. Let's define the function $f: [m] \rightarrow [m]$ as follows. For each $1 \le i \le m$, we will let $f(i) = i+k$, where $k$ is the smallest positive integer so that $i+k$ does not point to $i.$ It's easy to see that if $k > 1$, $i+1 \rightarrow i, i+2 \rightarrow i, \cdots, i +k-1 \rightarrow i.$ (Again, indices modulo $m$) We claim that there do not exist $a, b$ so that $f(a) = b, f(b) = a.$ Suppose there did exist such $a, b.$ If $b = a-1$, then use the induction on the vertices $a+1, a+2, \cdots, b$ to see that either there is a path from $i$ to $i+1$ for some $a+1 \le i \le b-1$, or there is a path from $a-1$ to $a+1.$ In the former case, the induction is complete. In the latter case, as $b \neq a+1$ ($n \ge 3$), we must have $a+1 \rightarrow a$ by the definition of $f$, and so there is a path from $a-1$ to $a+1$ to $a.$ If $a = b-1$, use a similar argument. Otherwise, suppose that $a,b, a-1, b-1$ are all distinct numbers. Then, we know that $b-1 \rightarrow a$ and $a-1 \rightarrow b.$ If $a \rightarrow a-1$, then $b-1 \rightarrow a \rightarrow a-1 \rightarrow b$, and we're done. Otherwise, if $a-1 \rightarrow a$ we are also done. Therefore, there can be no edge between $a-1$ and $a.$ Similarly, there is no edge between $b$ and $b-1.$ Now, if $b-1 \rightarrow a-1$, then $b-1 \rightarrow a-1 \rightarrow b$ and we're done. Otherwise, if $a-1 \rightarrow b-1$, then $a-1 \rightarrow b-1 \rightarrow a$ and we're done. Therefore, assume there is no edge between $a-1$ and $b-1.$ Now, call $i$ cool if $i+1 \rightarrow i.$ Let there be $x \le m$ cool integers in $1, 2, \cdots, m.$ Call a non-edge a pair of integers $(a, b)$ where $a, b$ are not connected in either direction. Then, there are $m-x$ non-edges consisting of consecutive positive integers. We wish to show that there are at least $x$ other non-edges. For each cool $a$, consider the nonedge $(a, f(a)).$ There are $x$ of these non-edges, but some of them can coincide. Let there be $2 \ell$ integers $1 \le a \le m$ where $f(f(a)) = a.$ Then, there are actually only $x- \ell$ of these non-edges, because $\ell$ of them are counted twice. Let these $\ell$ doubly counted edges be $(a_1, b_1), \cdots, (a_\ell, b_\ell).$ From the previous paragraph, we know that for each $1 \le i \le \ell$, $(a_i - 1, b_i - 1)$ is also a non-edge. These non-edges are clearly distinct from each other. They are also distinct from the $x - \ell$ cool non-edges because $a_i - 1$ is not cool ($a_i -1, a_i$ aren't connected). Finally, they also clearly don't coincide with any of the $m-x$ non-edges with consecutive positive integers, because $a_i-1, b_i - 1$ aren't consecutive. Hence, putting all of these together gives us $m-x + x- \ell + \ell = m$ non-edges. Hence, there must be at most $\binom{m}{2} - m < \binom{m-1}{2}$ non-edges, a clear contradiction. The induction is complete, and therefore the lemma is proven. $\blacksquare$ Now, our strategy is simple. Simply take a random vertex in each of the sets, construct the divisibility digraph on them, and apply the lemma. We know that each of these divisibility digraphs must have at most $\binom{m-1}{2}$ edges, and so the probabilistic method now easily yields that there are at most $\binom{m-1}{2} n^2$ edges overall. $\square$