Given a set $S$ of positive real numbers, let $$\Sigma (S) = \Bigg\{ \sum_{x \in A} x : \emptyset \neq A \subset S \Bigg\}.$$be the set of all the sums of elements of non-empty subsets of $S$. Find the least constant $L> 0$ with the following property: for every integer greater than $1$ and every set $S$ of $n$ positive real numbers, it is possible partition $\Sigma(S)$ into $n$ subsets $\Sigma_1,\ldots, \Sigma_n$ so that the ratio between the largest and smallest element of each $\Sigma_i$ is at most $L$.
Problem
Source: 2018 Brazil 3rd TST #4
Tags: algebra, combinatorics, Subsets, inequalities, boundary conditions
Pathological
25.03.2019 00:15
Is $n$ fixed here? If not, then the below works:
We claim that the answer is $2.$ Firstly, to see that $L \ge 2,$ take $\{1, x, x^2, \cdots, x^{n-1}\}$ for $x$ such that $1 + x + x^2 + \cdots + x^{n-1} = x^n,$ for $n$ sufficiently large. Then, among $1, x, x^2, \cdots, x^{n-1}, 1 + x + x^2 + \cdots + x^{n-1},$ there are two in the same group, and hence $L \ge x.$ For $n$ big, $x$ approaches $2$ and so hence $L \ge 2.$
Now, we'll show that $L = 2$ always works for any $n$ by strong induction on $n$. It suffices to create $n$ intervals of positive reals, each of which has its upper bound at most twice the lower bound and so that each subset sum is in some interval. When $n = 1, 2$, the problem is trivial. Else, let's suppose that $n < k$ all work, for some $k \ge 3.$ When $n = k,$ let our set consist of $a_1 < a_2 < \cdots < a_n.$ For a natural number $k > 2,$ we will call $k$ a $\mathbf{big}$ $\mathbf{boi}$ if $a_k > a_1 + a_2 + \cdots + a_{k-1}.$ If there are no big bois, then considering the intervals $[a_1, a_1], [a_2, a_2 + a_1], [a_2 + a_1, a_2 + a_1 + a_3], [a_2 + a_1 + a_3, a_2 + a_1 + a_3 + a_4], \cdots, [a_2 + a_1 + a_3 + \cdots + a_{n-1}, a_2 + a_1 + a_3 + \cdots + a_n]$ and observing that every set belongs to at least one of these intervals finishes.
Otherwise, let's consider the largest big boi $t$. By induction, we can create $t-1$ intervals to take care of all the subsets of $\{a_1, a_2, \cdots a_{t-1}\}$ If $t = n,$ then we simply finish by creating the interval $[a_t, a_t + a_1 +a_2 + \cdots + a_{t-1}]$. Otherwise, consider denote by $b_r$ the sum $a_1 + a_2 + \cdots + a_r$, and consider the $n-t+1$ intervals $[a_t, b_t], [b_t, b_{t+1}], [b_{t+1}, b_{t+2}], \cdots, [b_{n-1}, b_n].$ It's clear that these $n-t+1$ intervals have a union of $[a_t, b_n]$, and so hence they contain the sum of elements of any subset of $\{a_1, a_2, \cdots, a_n\}$ which isn't a subset of $\{a_1, a_2, \cdots, a_{t-1}\}.$ Therefore, combining these $n-t+1$ intervals with the $t-1$ intervals guaranteed by induction finish.
$\square$
However if $n$ is fixed then the problem is much harder. I suspect that the answer in that case is that the least possible $L$ is the unique positive root of $1 + x + x^2 + \cdots + x^{n-1} = x^n.$