
Problem 3. There are given 100 distinct positive integers. We call a pair of integers among them good if the ratio of its elements is either 2 or 3 . What is the maximum number $g$ of good pairs that these 100 numbers can form? (A same number can be used in several pairs.)


Solution. Like so often in Russian problems, numbers are used instead of generic symbols. Let us therefore denote $10=n>1,2=k>1,3=\ell>1$, with the extra condition both $k$ and $\ell$ aren't powers of a same number. Consider the digraph $G$ whose set of vertices $V(G)$ is made of $v=n^{2}$ distinct positive integers, and whose set of edges $E(G)$ is made by the pairs $(a, b) \in V(G) \times V(G)$ with $a \mid b$. For each positive integer $m$ consider now the (not induced) spanning subdigraph $G_{m}$ of $G$ (with $V\left(G_{m}\right)=V(G)$ and so $v_{m}=v=n^{2}$ vertices), and whose edges are the pairs $(a, b) \in G \times G$ with $b=m a$. Moreover, it is clear that $E\left(G_{m^{\prime}}\right) \cap E\left(G_{m^{\prime \prime}}\right)=\emptyset$ for $m^{\prime} \neq m^{\prime \prime}$ (since if $(a, b) \in E(G)$ then $(a, b) \in E\left(G_{b / a}\right)$ only), and also $\bigcup_{m \geq 1} E\left(G_{m}\right)=E(G)$ (but that is irrelevant). Since the good pairs are precisely the edges of $G_{k}$ and $G_{\ell}$ together, we need to maximize their number $g$.

A digraph $G_{m}$ is clearly a union of some $n_{m}$ disjoint (directed) paths $P_{m, i}$, with lengths $\lambda\left(P_{m, i}\right)=\lambda_{m, i}, 0 \leq \lambda_{m, i} \leq n^{2}-1$, such that $\sum_{i=1}^{n_{m}}\left(\lambda_{m, i}+1\right)=n^{2}$, and containing $e_{m}=\sum_{i=1}^{n_{m}} \lambda_{m, i}$ edges (zero-length paths, i.e. isolated vertices, are possible, allowed, and duly considered). The defect of the graph $G_{m}$ is taken to be $v-e_{m}=n_{m}$. We therefore need to maximize $g=e_{k}+e_{\ell}$, or equivalently, to minimize the defect $\delta=n_{k}+n_{\ell}$.

Using the model $V(G)=V_{x}=\left\{k^{i-1} \ell^{j-1} x \mid 1 \leq i, j \leq n\right\}$, we have $n_{k}=n_{\ell}=n$, therefore $\delta=2 n$, so $g=2 n(n-1)$. To prove value $2 n$ is a minimum for $\delta$ is almost obvious. We have $\lambda_{k, i} \leq n_{\ell}-1$ for all $1 \leq i \leq n_{k}$ (by the condition on $k$ and $\ell$, we have $\left|P_{k, i} \cap P_{\ell, j}\right| \leq 1$ for all $1 \leq i \leq n_{k}$ and $\left.1 \leq j \leq n_{\ell}\right),{ }^{2}$ so $n^{2}-n_{k}=e_{k}=\sum_{i=1}^{n_{k}} \lambda_{k, i} \leq \sum_{i=1}^{n_{k}}\left(n_{\ell}-1\right)=n_{k} n_{\ell}-n_{k}$, therefore $n^{2} \leq n_{k} n_{\ell}$, and so $\delta=n_{k}+n_{\ell} \geq 2 \sqrt{n_{k} n_{\ell}}=2 n$. Moreover, we see equality occurs if and only if $n_{k}=n_{\ell}=n$ and $\lambda_{k, i}=\lambda_{\ell, i}=n-1$ for all $1 \leq i \leq n$, thus only for the sets $V_{x}$ described above. Răspunsul este deci $g=180$.

Comentarii. Odată ce ideea vine, problema este aproape trivială, cu detaliile tehnice fiind aproape "forţate". Valorile particulare folosite aruncă doar un văl de umbră asupra situaţiei de fapt (mai ales ocultul $100=10^{2}$ )! Laticea de divizibilitate a celor $n^{2}$ numere este considerată în mod natural, şi conduce la facila numărătoare de mai sus.[^1]

## Second Day - Solutions
