# How to cut one hundred apples into pieces

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?

• can there be leftovers pieces (of like 8g or so)? – RiddlerNewComer Feb 16 '16 at 7:38
• In other words: is it always possible to cut pieces so that no child receives more than four pieces? – Fimpellizieri Feb 16 '16 at 8:05
• Is there limit for no of pieces for each child.? – Anbu.Sankar Feb 16 '16 at 8:35
• @RiddlerNewComer: no, there cannot be any leftover pieces (the total weight of the apples equals the total weight that the children should receive). – Gamow Feb 16 '16 at 13:14
• @Fimpellizieri: No. If the conditions of the puzzle are satisfied, then yes, every child receives at most four pieces. But if every child receives at most four pieces, then no, this does not imply that the conditions of the puzzle are satisfied. – Gamow Feb 16 '16 at 13:16

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:

• The smallest apple and the largest apple together weigh at least $125$ grams, and the smallest apple weighs no more than $75$ grams;
• The smallest apple and the largest apple together weigh less than $125$ grams;
• Every apple weighs more than $75$ grams.

### Case 1: The smallest apple and the largest apple together weigh at least $125$ grams, and the smallest apple weighs no more than $75$ grams.

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$.

### Case 2: The smallest apple and the largest apple together weigh less than $125$ grams.

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$.

### Case 3: Every apple weighs more than $75$ grams.

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.

• @f'' proved that "101 apples (total 10000 grams) can be cut into >25-gram pieces and share to 100 children". But the question asks 100 apples. Are they the same thing? Am I missing something? – wilson Feb 17 '16 at 7:11
• @wilson Note the last paragraph "The largest one is at least 100 grams, so we can safely cut it in half". so you create a 101st apple this way – Ivo Beckers Feb 17 '16 at 14:38
• @Ivo fully understand now, thanks :) – wilson Feb 18 '16 at 2:01

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.

• ugh... I think I made a mistake. In the case of >75g I actually take 200g away but reducing the apple count only by 1. But I think I'm close – Ivo Beckers Feb 16 '16 at 14:40

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!