Let $n, b$ and $c$ be positive integers. A group of $n$ pirates wants to fairly split their treasure. The treasure consists of $c \cdot n$ identical coins distributed over $b \cdot n$ bags, of which at least $n-1$ bags are initially empty. Captain Jack inspects the contents of each bag and then performs a sequence of moves. In one move, he can take any number of coins from a single bag and put them into one empty bag. Prove that no matter how the coins are initially distributed, Jack can perform at most $n-1$ moves and then split the bags among the pirates such that each pirate gets $b$ bags and $c$ coins.
Problem
Source: 2021 MEMO T-3
Tags: combinatorics, Strategy, MEMO 2021, memo, induction
x3yukari
06.09.2021 02:33
Suppose the case of $n$ pirates with $b$ bags and $c$ coins works for all $b$ and $c$. The base case where $n=2$ is trivial, as you can just use one move to move half of the coins into the empty bag.
We prove $n+1,b,c$ works. This is the equivalent to adding $c$ coins to the total, adding another pirate (let this be the "new" pirate), and giving him $b$ bags, one of which is empty, for a total of $n$ empty bags. Jack has $n$ moves to use.
After the $cn+c$ coins are initially distributed throughout the $bn+b$ bags, we choose $b$ non-empty bags for the new pirate such that the total number of coins in these bags is greater than $c$. Clearly this is possible; otherwise there either would be less than $cn+c$ coins, or exactly $cn+c$ coins with each possible set of $b$ non-empty bags having $c$ coins in total, in which case we are already done. We then choose one bag to remove such that the total number of coins in the remaining bags is less than $c$.
We prove that this step is possible: Suppose the contrary. This implies that for all sets of $b-1$ non-empty bags, the total number of coins in these bags is greater than $c$. But this implies that there must be more than$\frac{bn+b}{b-1}\cdot c$ coins in total, which is greater than $cn+c$ coins in total, which is clearly absurd.
So we know we can choose $b$ non-empty bags and remove a bag to get a set of $b-1$ non-empty bags, and then we add the $n$th empty bag. Now we take coins from the bag we just removed from the set of $b$ non-empty bags, and use one move to move coins into the empty bag we just added such that the total number of coins in these $b$ bags is now $c$. (We already proved this is possible because there is a bag with enough coins to move such that we can have more than $c$ coins in these $b$ bags.) Now this pirate has $c$ coins, so we need not perform any moves involving them anymore. Out of the remaining $n$ pirates, there are $n-1$ empty bags, $cn$ coins, $bn$ bags total, and $n-1$ moves left, which is identical to our induction hypothesis. So thus the result is proved by induction.
lazizbek42
16.01.2022 18:56
we prove this by induction, n = 1 is easy.conditionally n-1 bags are empty.Let's look at the rest. $$x_1 \leq x_2 \leq x_3... \leq x_{n(b-1)+1}$$$$x_1 + x_2 + x_3 + ... + x_{n(b-1)+1} = cn$$according to the principle of the pigeonhole $$x_1 + x_2 + x_3 + ... + x_{b-1} \leq c$$$$x_{n(b-1)+1-b+2}+ ... + x_{n(b-1)+1} \ge c$$so we can choose $i$ in which the following condition is satisfied. $$x_i + x_{i+1} + x_{i+2} + ... + x_{i+b-2} = c-k $$$$x_{i+1} + x_{i+2} + ... + x_{i+b-1} \ge c = k + c-k \ge k + x_i + x_{i+1} + x_{i+2} + ... + x_{i+b-2} $$$$x_{i+b-1} \ge k + x_i $$We get $$x_i, x_{i+1},..., x_{i+b-2}$$and $x_{i+b-1}$ has at least k according to the above and we can't take k from it and put it in one empty space. So we have $c$ coins in some $b$ empty $n-2$ remaining coins $b(n-1)$ are appropriate according to this induction.