Wrong Answer

The answer is $\boxed{n+1}$: Construction: BUMP! Can someone think of a strategy for Sepher for $B=n+1$? Bound: Let the elements be $E_1,E_2,\dots,E_n$. Fill the first $n-1$ cups with $2k$ grams of each of $E_1,E_2,\dots,E_{n-1}$. Then distribute the $2k$ grams of $E_n$ uniformly among the remaining elements. As $\frac{2k}{2k-(n-1)}<2$, this construction works. (I hope I did not make a mistake)

sami1618 wrote: The answer is $\boxed{n+1}$: Construction: We will proceed by induction on $n$ for a fixed $k$. The case $n=1$ is obvious. For $n\rightarrow n+1$ if we are not able to select another cup resulting in two grams of the new element we must have $2(1+(2k-n))<2k\Rightarrow k<n-1$, a contradiction. I don't think the last inequality is correct

flower417477 wrote: I don't think the last inequality is correct Why not? The inequalities seems fine

It doesn't work. It should be given in a reversed way. e.g. You get $0$ grams of the last element in the first $n$ cups selected, then if the remaining cups have the same amount of the element, you can't just choose one cup to promise that there's $2$ grams of the last element

You are right. I will try to fix my solution. I still believe that $n+1$ is the correct answer.

Is there any powerful math enthusiast who can provide a rigorous proof? Thank you.

Here is a observation (do not know if it helps at all). By induction we can assume we have $<2$ grams of each element in each cup. The case $k=n+\frac{1}{2}$ can be resolved easily as follows. We have $2n+1$ cups and if we remove the cup with the least of each element then we have at least $\frac{3(n+1)}{n+2}$ grams of each element in the remaining $n+1$ cups. I wonder if anyone can extend this strategy or induct $k\mapsto k+\frac{1}{2}$.

The answer is $n+1$ and the bound exactly comes from the method that sami1618 employed. Now here is the official solution for its construction : We preform an induction on $n+k$ ; if we have $2$ grams or more for a chemical element in one cup , then by induction hypothesis we can choose $n$ proper cups for other $n-1$ element and this one for the other and that will be all right , so we may suppose that there is less than $2$ grams from each element in each cup. Now suppose that for an element $j$ , our cups contain this element with values $a_1 , a_2 , ... , a_{2k}$ in the decreasing order ; thus while we have : $$(a_1+a_{2k})+(a_2+a_{2k-1})+...+(a_{k}+a_{k+1})=2k$$There exist an index $s \le k$ such that $a_s+a_{2k+1-s} \ge 2$ and name the minimum index with this property as $i_j$ and also suppose that we arrange the elements in a way that the values of $i_j$ are increasing. Name all cups that contains more or equal than $a_{i_j}$ grams from element $j$ as $j-$great and all cups that contains more or equal than $a_{2k+1-i_{j}}$ grams from element $j$ as $j-$good. Note that $i_j \le k$ for each element $j$ , then there exist at least $k+1$ $j-$good cups for each element ; so by peogenhole principle for each two elements $j$ and $h$ , there exist at least two cups which are both $j-$good and $h-$good. So if for two elements $j , h$ there exist a cup which is both $j-$perfect and $h-$perfect , then we have an another cup which is $j-$good and $h-$good and by picking this two cups which contains at least two grams from both $j , h$ according to our definition and by our induction hypothesis for other elements , we will be done. So we can assume that there doesn't exist a cup which is $j-$great and $h-$great at the same time. Since we created values of $i_j$ in the increasing order , for each element $j$ there exist at least $i_j+1$ $j+1-$great cups and only $i_j$ of cups are not $j-$good ; thus there exist a cup which is both $j-$good and $j+1-$great. Now we can choose the first cup as a $1-$great cup , second one as $1-$good and $2-$great and by continuing this process , at last we can pick a $n-$good cup as our $n+1$-th choise and we're done.

Does this approach work for Sepehr's strategy? Work in $\mathbb{R}^n$. Consider the cups $c_1, c_2, \dots, c_{2k}$ as vectors in $\mathbb{R}^n$, where the value in the $i^\text{th}$ index of $c_j$ represents the amount (in grams) of the $i^\text{th}$ element placed in the $j^\text{th}$ cup. Let $\textbf{u} = (1, 1, \dots, 1)$. We know that \[ c_1 + c_2 + \dots + c_{2k} = 2k \textbf{u}, \]or equivalently, that $\textbf{u}$ is the centroid of $c_1, c_2, \dots, c_{2k}$. Consider $\mathcal{C}$, the convex hull of these $2k$ points. It is well known that the centroid lies in the convex hull, so $\textbf{u} \in \mathcal{C}$. Since the convex hull can be thought of as the union of simplices, $\textbf{u}$ must be contained in one of these simplices. Thus, there exist some $d_1, d_2, \dots, d_{n+1} \in \{c_1, c_2, \dots, c_{2k}\}$ and $\theta_1, \theta_2, \dots, \theta_{n+1} \in \mathbb{R}_{\geq 0}$ with $\theta_1 + \theta_2 + \dots + \theta_{n+1} = 1$ such that \[ \theta_1 d_1 + \theta_2 d_2 + \dots + \theta_{n+1} d_{n+1} = \textbf{u}. \] If it happens that $\theta_1, \theta_2, \dots, \theta_{n+1} \leq \frac{1}{2}$, then by doubling the equation it is clear that Sepehr can simply choose the $n+1$ cups $d_1, d_2, \dots, d_{n+1}$. Otherwise, assume $\theta_{n+1} > \frac{1}{2}$. Then notice that \[ 2\textbf{u} - d_{n+1} = 2\theta_1 d_1 + 2\theta_2 d_2 + \dots + 2\theta_n d_n + (2\theta_{n+1} - 1)d_{n+1} \in \mathcal{C}. \] As $2\textbf{u} - d_{n+1}$ lies in the convex hull, there must exist some $e_1$ from the $2k$ vectors such that the first index of $e_1$ is greater than or equal to the first index of $2\textbf{u} - d_{n+1}$. We claim that we can always choose $e_1 \neq d_{n+1}$ because if $d_{n+1}$ were the only vector satisfying this condition, then the average of the first index across all the vectors would be smaller than $1$, a contradiction. Continue choosing $e_2, \dots, e_n$ similarly. If $e_i$ is equal to one of its predecessors, we can simply discard it. Then by construction, we have \[ 2\textbf{u} - d_{n+1} \preccurlyeq e_1 + e_2 + \dots + e_n \implies 2\textbf{u} \preccurlyeq e_1 + e_2 + \dots + e_n + d_{n+1}. \] Thus, Sepehr can choose these $n+1$ cups, as desired.