# 100 children think numbers and multiply

Given 100 children, let’s call them $$c_1, c_2, \dots c_{100}$$. Every child thinks of a nonnegativ real number, such that the sum of these numbers is 1. Then for every pairs of integers $$(x,y)$$ such that $$0 and $$y/x$$ is an integer, children $$c_x,c_y$$ meet and multiply their numbers and they write down the result onto a paper. For example if $$c_3$$ thought of the number $$0.5$$ and $$c_9$$ thought of the number $$0.2$$ then they write down the number $$0.1$$.

Let $$N$$ be the sum of the numbers on the paper. Find the maximum possible value of $$N$$.

This problem is based on an Argenteen problem.

This question is also quite similar to a problem in a Hungarian mathematics contest (which ended by now): https://www.komal.hu/feladat?a=honap&h=201809&t=mat&l=en

I don't know how to prove this, but I'm pretty sure that the answer must be that the seven children whose numbers are powers of $2$ write $\frac17$ and everyone else writes $0$, for a sum of $\frac37$.

The reason I think so is that if you have $k$ numbers that add up to $1$ and add all their pairwise products, the optimum is attained when all numbers are $\frac1k$, and then the sum of the pairwise products is

$$\frac{\binom k2}{k^2}=\frac{k-1}{2k}\;.$$

This goes to $\frac12$ as $k\to\infty$, so adding more numbers into the mix yields diminishing returns. The powers of $2$ are the largest subset of which all pairwise products are included; taking any larger set would only slightly increase the all-pair bound $\frac{k-1}{2k}$, while including lots of pairs that aren't included in the sum.

The maximum is $$\frac{3}{7}$$, given by $$c_1 = c_2 = c_4 = c_8 = c_{16} = c_{32} = c_{64} = \frac{1}{7}$$ and all other $$c_i = 0$$.

Now a proof. Replace $$100$$ with an arbitrary constant $$N$$. We are maximizing the function $$f: \mathbb{R}^{N} \to \mathbb{R}$$ given as $$f(x_1, \ldots, x_N) = \sum_{\substack{1 \leq m < n \leq N} \\ \text{m divides n}} x_m x_n$$ subject to the constraints $$(\forall i) x_i \geq 0$$ and $$\sum_{i=1}^N x_i = 1$$.

Lemma. Let $$(x_1, \ldots, x_N) \in \mathbb{R}^N$$ be arbitrary. Let $$\pi(n)$$ be the sum of exponents in the prime factorization of $$n$$. (For example, $$\pi(180) = \pi(2^2 3^2 5) = 2^{2+2+1} = 64.$$ Note that $$2^{\pi(n)} < n$$.) Let $$\pi^{-1}(k)$$ denote the set of integers $$n \leq N$$ such that $$\pi(n) = k$$. Finally, define $$y_1, \ldots, y_N$$ as follows: if $$n = 2^k$$, then $$y_n = \sum_{i \in \pi^{-1}(k)} x_i$$; otherwise, $$y_n = 0$$. Then $$f(x_1, \ldots, x_N) \leq f(y_1, \ldots, y_N)$$.

Proof. Let $$K = \left\lfloor \log_2 N\right\rfloor = \max_{1 \leq n \leq N} \pi(n)$$. Note that $$\pi(m) < \pi(n)$$ is a necessary, but not sufficient, condition for $$m$$ to divide a distinct integer $$n$$. Then:

\begin{align} f(y_1, \ldots, y_N) &= \sum_{\substack{1 \leq m < n \leq N& \\ \text{m divides n}}} y_m y_n &\text{(definition of f)}& \\ &= \sum_{0 \leq k < \ell \leq K} y_{2^k} y_{2^\ell} &\text{(y_n = 0 unless n is a power of 2)} \\ &= \sum_{0 \leq k < \ell \leq K} \left[\left( \sum_{i \in \pi^{-1} (k)} x_i\right) \left( \sum_{j \in \pi^{-1} (\ell)} x_j\right) \right]&\text{(definition of y_i)} \\ &= \sum_{0 \leq k < \ell \leq K} \sum_{\substack{i \in \pi^{-1}(k) \\ j \in \pi^{-1}(\ell)}} x_i x_j &\text{(simple rearrangement)}\\ &\geq \sum_{0 \leq k < \ell \leq K}\sum_{\substack{i \in \pi^{-1}(k) \\ j \in \pi^{-1}(\ell) \\ \text{i divides j}}} x_i x_j&\text{(fewer terms in inner sum)} \\ &= \sum_{\substack{1 \leq i < j \leq N \\ \text{i divides j}}} x_i x_j&\text{(double sum includes every possible (i, j) pair once)} \\ &= f(x_1, \ldots, x_N). &\text{(definition of f)}\\ \end{align}

So if $$f$$ has a maximum $$(c_1, \ldots, c_N)$$, then the maximum must have $$c_n = 0$$ except where $$n$$ is a power of $$2$$. To show that $$f$$ has a maximum, simply note that it is concave and the region of $$\mathbb{R}^N$$ allowed by the constraints is convex. QED.

The essential idea of the lemma is this: Suppose that, for example, $$x_2, x_3, x_4, x_9$$ are all nonzero. Then the only terms that contribute to $$f(x_1, \ldots, x_N)$$ are $$x_2 x_4$$ and $$x_3 x_9$$. But if we define $$y_2 = x_2 + x_3$$ and $$y_4 = x_4 + x_9$$, then the $$y_2 y_4$$ term includes $$x_2 x_4$$ and $$x_3 x_9$$, but also includes $$x_2 x_9$$ and $$x_3 x_4$$.

We've reduced the question to maximizing $$g(x_1, \ldots, x_{K+1}) = \sum_{1 \leq i < j \leq K+1} x_i x_j$$ subject to the constraints $$(\forall i) x_i \geq 0$$ and $$\sum_{i = 1}^{K+1} x_i = 1$$. (Here, $$x_i$$ corresponds to the old $$x_{2^i}$$.) To see that the maximum here is given by $$x_1 = \cdots = x_{K+1} = \frac{1}{K+1}$$. suffices to note that $$g$$ is concave and symmetric (as every unordered pair $$\{i, j\}$$ is included once), so if $$g$$ has a maximum at $$(x_1, x_2, \ldots, x_{K+1})$$ where $$x_i \neq x_j$$, then interchanging the values of $$x_i$$ and $$x_j$$ gives another maximum, contradicting the concavity of $$g$$. Therefore, $$g$$ (and thus $$f$$) have a maximum value of $$\frac{\binom{K+1}{2}}{K+1} = \frac{K}{2(K+1)}.$$ In the original case $$N = 100$$, $$K = 6$$, the maximum value is $$\frac{3}{7}$$.