Given a set S of positive real numbers, let Σ(S)={∑x∈Ax:∅≠A⊂S}.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 Σ(S) into n subsets Σ1,…,Σn so that the ratio between the largest and smallest element of each Σ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≥2, take {1,x,x2,⋯,xn−1} for x such that 1+x+x2+⋯+xn−1=xn, for n sufficiently large. Then, among 1,x,x2,⋯,xn−1,1+x+x2+⋯+xn−1, there are two in the same group, and hence L≥x. For n big, x approaches 2 and so hence L≥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≥3. When n=k, let our set consist of a1<a2<⋯<an. For a natural number k>2, we will call k a big boi if ak>a1+a2+⋯+ak−1. If there are no big bois, then considering the intervals [a1,a1],[a2,a2+a1],[a2+a1,a2+a1+a3],[a2+a1+a3,a2+a1+a3+a4],⋯,[a2+a1+a3+⋯+an−1,a2+a1+a3+⋯+an] 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 {a1,a2,⋯at−1} If t=n, then we simply finish by creating the interval [at,at+a1+a2+⋯+at−1]. Otherwise, consider denote by br the sum a1+a2+⋯+ar, and consider the n−t+1 intervals [at,bt],[bt,bt+1],[bt+1,bt+2],⋯,[bn−1,bn]. It's clear that these n−t+1 intervals have a union of [at,bn], and so hence they contain the sum of elements of any subset of {a1,a2,⋯,an} which isn't a subset of {a1,a2,⋯,at−1}. Therefore, combining these n−t+1 intervals with the t−1 intervals guaranteed by induction finish.
◻
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+x2+⋯+xn−1=xn.