Given positive integer $n (n \geq 2)$, find the largest positive integer $\lambda$ satisfying : For $n$ bags, if every bag contains some balls whose weights are all integer powers of $2$ (the weights of balls in a bag may not be distinct), and the total weights of balls in every bag are equal, then there exists a weight among these balls such that the total number of balls with this weight is at least $\lambda$.
Problem
Source: China TST 2005-2
Tags: combinatorics unsolved, combinatorics
KuMing
29.08.2005 08:39
\[\lambda = \lfloor \frac{n}{2} \rfloor + 1\]
Pathological
06.04.2019 04:16
We claim that the answer is $\lambda = \left \lfloor \frac{n}{2} \right \rfloor + 1$. First, we will establish that this is a lower bound. Firstly, we observe that any sum of $m$ as a sum of powers of two can be obtained from $m$'s binary representation by applying the operation $2^i \rightarrow 2^{i-1} + 2^{i-1}$ repeatedly. For example, $7 = 2^1 + 2^1 + 2^1 + 2^0$ can be obtained from $7$'s binary representation $2^2 + 2^1 + 2^0$ by simply replace $2^2$ with $2^1 + 2^1$. The proof of this is easy by induction. Notice that this claim allows us to assume, WLOG, that the sum of the weights of the balls in every bag is a power of $2$. The reason we can do this is because if not, we can just take the balls which "split off" of one of the powers of two in the binary representation (as in the result above) of the common sum of the bags. So suppose that the sum of the balls in every bag has weight $2^k$. Then, we know that $\lambda ( 2^k + 2^{k-1} + \cdots + 2^1 + 2^0) \ge n * 2^k \Rightarrow \lambda \ge \frac{2^kn}{2^k + 2^{k-1} + \cdots + 2^1 + 2^0} > \frac{n}{2}$, hence establishing that $\lambda \ge \left \lfloor \frac{n}{2} \right \rfloor + 1$.
Now, all that remains is to construct an example where $\lambda = \left \lfloor \frac{n}{2} \right \rfloor + 1$ is achieved for all $n \in \mathbb{N}$. Write $2^k \le n < 2^{k+1}$, and let $\lambda' = \left \lfloor \frac{n}{2} \right \rfloor + 1$. Then, consider writing $2^k$ $\lambda'$ times in a row, and then $2^{k-1}$ $\lambda'$ times in a row, $\cdots$, and finally writing $2^0$ $\lambda'$ times in a row. Then, let's draw a divider so that between any two dividers the sum is zero. It's easy to show that this "works" since $2^i \lambda' > n$ for $i \in \mathbb{N}$ and $\lambda' (2^0 + 2^1 + \cdots + 2^k) = \lambda' (2^{k+1} - 1) \ge \frac{n+1}{2} (2^{k+1} - 1) \ge n * 2^k$. The last part follows since $\frac{n+1}{2n} = \frac12 + \frac{1}{2n} \ge \frac12 + \frac{1}{2(2^{k+1}-1)} = \frac{2^k}{2^{k+1}-1}$.
Example:
$$8|8|8|8|8|44|44|422|22211|111$$$\square$