Jtdylktuy

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<x<y<101$ 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 $ktoinfty$, 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 = leftlfloor log_2 Nrightrfloor = 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_iright) left( sum_{j in pi^{-1} (ell)} x_jright) 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}$.