The maximum of (Minimum $\times$ Cardinality) Over all Subsets

50 Views Asked by At

We are given a set of positive reals $S$ and also a subset $S'$ of the $k$ largest numbers in $S$ such that $\min(S') \times k$ is maximum, where $\min(S')$ is the minimum number in $S'$.

Let $sum(S)$ be the sum of numbers in $S$. What can we say about the ratio $R=\frac{\min(S') \times k}{sum(S)}$?

Can we claim $R$ is lower bounded by a constant?

First Attempt

Choose $S'$ as the subset of numbers in $S$ at least half the average in $S$.

Here are some examples.

For $S = \{ 1,1,1,5 \}$, half of average is 1 and we get $S'=S$ and $R=4/8 = 1/2$.

For $S = \{ 1,1,5 \}$, we get $S'=\{ 5 \}$ and $R=5/7 > 1/2$.

For $S = \{ 1,1,4 \}$, we get $S'=S$ and $R=3/6 = 1/2$.

Is it always $R \geq 1/2$?

1

There are 1 best solutions below

0
On BEST ANSWER

No, $R$ can get smaller than any given positive value.

Consider

$$S_n=\{1, \frac1{2\times 2}, \frac1{2\times 3}, \ldots , \frac1{2\times n}\}.$$

The $k$-th maximum value equals $1$ for $k=1$, otherwise it is $\frac1{2k}$, so $k\times \min(S')$ is $1$ for $k=1$ and $\frac12$ for $k>1$. That means the extremal value is taken for $k=1$ and $S'=\{1\}.$ That means for $S_n$ the value of $R$ is

$$R=\frac{1}{1+\sum_{i=2}^n\frac1{2i}},$$

and since the denominator is basically half the partial sum of the harmonic series up to $n$, it can be made arbitrary large for large $n$, so $R$ gets arbitrary small.