Let be two natural numbers m,n, and m pairwise disjoint sets of natural numbers A0,A1,…,Am−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