-1
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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}$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.