Divisibility mingled with combinatorics

Art of Problem Solving

AoPS Online

High School Olympiads Regional, national, and international math olympiads

Regional, national, and international math olympiads

3 M G

BBookmark VNew Topic kLocked

High School Olympiads Regional, national, and international math olympiads

Regional, national, and international math olympiads

3 M G

BBookmark VNew Topic kLocked

No tags match your search

M

Divisibility mingled with combinatorics

G H J

Reveal topic tags

L

G H BBookmark kLocked kLocked NReply

Source: Romanian TST for 2019 IMO

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

2141 posts

#1 h Oct 1, 2019, 12:20 PM • 2 Y

Y by Adventure10, Mango247

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

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

578 posts

#2 h Oct 3, 2019, 2:12 AM • 5 Y

Y by ValidName, lvym, Adventure10, Mango247, soryn

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$

This post has been edited 2 times. Last edited by Pathological, Oct 3, 2019, 2:13 AM

Z K Y

N Quick Reply

G

H

=

© 2025 AoPS Incorporated

a