Let $a_{1}, a_{2}, \ldots, a_{2018}$ be non-negative real numbers whose sum is 1. Determine the maximum possible value of

$$
S=\sum_{i \neq j, i \mid j} a_{i} a_{j}
$$

where $i \mid j$ denotes that $i$ divides $j$.
I. Solution. First, we will show that the largest sum can be achieved with such $a_{i}$ numbers for which the following is true: if $a_{i}$ and $a_{j}$ are positive numbers, and $i0$ and $a_{j}>0$.

We will define a "swap" that does not decrease the sum $S$. Let $s_{i}$ and $s_{j}$ be the sum of those $a_{k}$ numbers whose indices are in a proper divisor or multiple relationship with $i$ and $j$, respectively, that is,

$$
s_{i}=\sum_{\substack{k \neq i \\(i|k \vee k| i)}} a_{k}, \quad \text { and } \quad s_{j}=\sum_{\substack{k \neq j \\(j|k \vee k| j)}} a_{k}
$$

Then, because $i \nmid j$ and $j \nmid i$, $a_{j}$ does not appear in $s_{i}$, and $a_{i}$ does not appear in $s_{j}$.

Let $s_{i} \geq s_{j}$. The sum

$$
S=\sum_{\substack{k \neq l \\ k \mid l}} a_{k} a_{l}
$$

can be broken into three parts; the first part will contain those two-factor products where one of the factors is $a_{i}$, the second part will contain those where one of the factors is $a_{j}$, while the third "remainder" part will consist of those products where neither factor is $a_{i}$ or $a_{j}$, that is,

$$
S=a_{i} s_{i}+a_{j} s_{j}+\sum_{\text {“remainder" }} a_{k} a_{l}
$$

If we now swap $a_{i}$ to $a_{i}^{\prime}=a_{i}+a_{j}$, and $a_{j}$ to $a_{j}^{\prime}=0$, then for the new sum $S^{\prime}$ (since the remainder, independent of $i, j$, does not change),

$$
S^{\prime}-S=a_{i}^{\prime} s_{i}+a_{j}^{\prime} s_{j}-a_{i} s_{i}-a_{j} s_{j}=\left(a_{i}+a_{j}\right) s_{i}-a_{i} s_{i}-a_{j} s_{j}=a_{j}\left(s_{i}-s_{j}\right) \geq 0
$$

thus we have not decreased the sum $S$.

As long as there are $i$ and $j$ such that $i \nmid j, j \nmid i$, but $a_{i}>0$ and $a_{j}>0$, we will perform the swap defined above. The swaps cannot continue indefinitely, because the number of positive $a_{k}$ decreases by 1 with each swap; therefore, after at most 2017 steps, we cannot swap any more. At that point, it is indeed true that if $a_{i}$ and $a_{j} 0$ are different numbers, and $i2018$ because there is no number among us for which the number of prime divisors (counted with multiplicity) is more than 10.

If for the numbers $i \neq j$, $i \mid j$, then $i$ and $j$ will fall into different groups, since $i$ has fewer prime divisors (counted with multiplicity) than $j$.

Let $0 \leq i \leq 10$ and $b_{i}=\sum_{j \in H_{i}} a_{j}$. (For example, $b_{0}=a_{1}, b_{1}=a_{2}+a_{3}+a_{5}+a_{7}+\ldots+a_{2017}$, while $b_{10}=a_{1024}+a_{1536}$.)

Consider the sum

$$
B=\sum_{0 \leq k<l \leq 10} b_{k} b_{l}=b_{0} b_{1}+b_{0} b_{2}+b_{0} b_{3}+\ldots+b_{9} b_{10}
$$

Let $i \in H_{k} ; j \in H_{l} ; i \neq j ; i \mid j$. Then the two-factor product $a_{i} a_{j}$ is one of the terms in the expanded form of $b_{k} b_{l}=\left(\ldots+a_{i}+\ldots\right)\left(\ldots+a_{j}+\ldots\right)$. Therefore,

$$
S \leq B=\sum_{0 \leq k<l \leq 10} b_{k} b_{l}=\frac{\left(b_{0}+b_{1}+\ldots+b_{10}\right)^{2}-\left(b_{0}^{2}+b_{1}^{2}+\ldots+b_{10}^{2}\right)}{2}
$$

For this sum (as described in the previous solution),

$$
S \leq \frac{\left(b_{0}+b_{1}+\ldots+b_{10}\right)^{2}-\left(b_{0}^{2}+b_{1}^{2}+\ldots+b_{10}^{2}\right)}{2} \leq \frac{1-\frac{1}{11}}{2}=\frac{5}{11}
$$

On the other hand, $S=\frac{5}{11}$ can be achieved with the choice $a_{1}=a_{2}=a_{4}=a_{8}=\ldots=a_{2^{n}}=\ldots=a_{1024}=\frac{1}{11}$.

Based on the work of Jedlovszky Pál (Budapesti Fazekas M. Gyak. Ált. Isk. és Gimn., 11th grade) and Szabó Dávid (Budapesti Fazekas M. Gyak. Ált. Isk. és Gimn., 12th grade)

Note. In his own solution equivalent to the second solution, Jedlovszky Pál defined the sets $H_{0}, H_{1}, \ldots, H_{10}$ such that $H_{0}=\{1\} ; H_{1}=\{2 ; 3\} ; H_{2}=\{4 ; 5 ; 6 ; 7\} ; \ldots ; H_{10}=\{1024 ; 1025 ; \ldots ; 2018\}$, while Tóth Balázs (Budapesti Fazekas M. Gyak. Ált. Isk. és Gimn., 11th grade) colored the vertices of a 2018-vertex (1-2018 labeled) graph with 11 colors according to the number of prime divisors (counted with multiplicity) of the corresponding label numbers.