Puzzling Stack Exchange is a question and answer site for those who create, solve, and study puzzles. It only takes a minute to sign up.
Sign up to join this community
In a basket there are 100 apples. Every apple weighs at least 25 gram, and the total weight of all apples is 10 kilogram. The teacher wants to cut these apples into pieces and assign the pieces to 100 children, so that each child receives 100 gram.
Question: Does there always exist a cutting so that each apple piece weighs at least 25 gram?
Suppose that we have $N+1$ apples (each at least $25$ grams) with a total weight of $100N$ grams, and we want to cut them into pieces of at least $25$ grams so that we can make $N$ groups weighing $100$ grams each.
If $N=1$, this is trivial: we have two pieces totalling $100$ grams, and we just put them together.
If $N>1$, I will show that we can always reduce the situation to make $N$ smaller.
There are three possibilities:
In this case, we can cut a piece off the larger apple so that the piece and the smallest apple weigh $100$ grams together. We have gotten rid of one apple and one set of $100$ grams, so we have reduced $N$ by $1$.
Because all the apples' weights sum to $100N$, the rest of the apples must have a total weight of at least $100N-125$ grams. The average weight of these apples is at least $\frac{100N-125}{N-1}=100-\frac{25}{N-1}$, which is at least $75$. Therefore the second-largest and largest apples must each weigh at least $75$ grams, and the smallest apple must weigh less than $50$ grams. We can cut a piece off the larger apple so that the piece and the smallest apple weigh $75$ grams together, then cut $25$ grams from the second-largest apple, for a total of $100$ grams. Again, we have gotten rid of one apple and one set of $100$ grams, so we have reduced $N$ by $1$.
Let the weight of the largest apple be $x$. For each $m\le N$, let $W_m$ be the weight of the $m$-th smallest apple, let $S_m$ be the sum of the weights of the $m$ smallest apples, and let $D_m=100m-S_m$. $D_m$ represents the size of the piece that would need to be added to the first $m$ apples to make them total $100m$ grams. In particular, $D_0=0$ and $D_N=x$.
$D_m-D_{m-1}=100+S_{m-1}-S_m=100-W_m<25$, so $D_m$ cannot increase by more than $25$ grams at a time. Because $x>75$, the difference between $25$ and $x-25$ is more than $25$ grams. Because $D_0<25$ and $D_N>x-25$, some $D_m$ will necessarily have a value between $25$ and $x-25$. Then we can cut off a piece of size $D_m$ from the largest apple and combine it with the smallest $m$ apples to make $m+1$ pieces totalling $100m$ grams. The remaining $N-m+1$ pieces total $100(N-m)$ grams. This reduces our situation to two smaller situations.
Therefore, for all $N$, if we have $N+1$ apples with a total weight of $100N$ grams, we can divide them so that we have $N$ groups of $100$ grams.
We start with $100$ apples. The largest one is at least $100$ grams, so we can safely cut it in half. Then we have $101$ pieces totalling $10000$ grams. This corresponds to $N=100$. As just shown, we can cut these pieces to make $100$ groups of $100$ grams.
I think the answer is:
Yes
Proof:
Use the following strategy. Take the smallest apple. If it is <= 75 g take the largest apple and cut a piece from it to match the first one to 100g. This is always possible because the largest apple is always >= 100 g. If the smallest apple is > 75 g you cut it in half and match each piece with pieces from the two largest apples. After doing this once you end up with essentially 99 apples that are at least 25g with an average of 100g, so exactly the original problem but with less apples. So repeat this strategy until there are no apples left and your done. This also actually proofs that you can do it in a way that every kid only gets 2 pieces.
This is basically Ivo Beckers' solution. I'm not sure if the etiquette is to edit his answer or to post mine and credit him. I'm choosing the latter. Ivo, the glory goes to you!
The answer is:
Yes
Proof:
Instead of counting apples, I will count steps. At each step we will give away 100g of apple. Call the current step N, begin with N=100. As Ivo pointed out, at any point there are basically three cases. Easy case: All apples are 100g. Done. Next Easiest: The smallest apple is <= 75g Apply Ivo's solution. Take the smallest apple and cut a piece to match it from the largest apple which is guaranteed to be > 100g since the average weight of an apple is 100g. Now you have one fewer apples with an average weight of 100g thus reducing the problem set by one. Hardest case: Apples are different weights and the smallest is > 75g. Cut a 25g slice from the smallest apple and put it aside. Next, take a slice from the largest apple to combine with the (reduced) smallest apple to make 100g. We now have one 25g slice and N-1 larger pieces with a total weight of (N-1)*100 grams. Decrement N and move to the next step. If we ever have 4 25g slices, we combine them, decrement N and continue. At every step we have 100N grams of apple remaining consisting of 0 - 3 25g slices totaling at most 75g and N larger pieces. The largest piece is guaranteed to be at least 100 - 75/N grams so we can continue until N = 2. At this point, we have two pieces totaling at least 125g and at most 3 25g slices. Cut 25g slices from whichever is the largest piece until we have 4. We now have 4 25g slices and two larger pieces which also total 100g. Done.
