8
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ can there be leftovers pieces (of like 8g or so)? $\endgroup$ – RiddlerNewComer Feb 16 '16 at 7:38
  • $\begingroup$ In other words: is it always possible to cut pieces so that no child receives more than four pieces? $\endgroup$ – Fimpellizieri Feb 16 '16 at 8:05
  • $\begingroup$ Is there limit for no of pieces for each child.? $\endgroup$ – Anbu.Sankar Feb 16 '16 at 8:35
  • $\begingroup$ @RiddlerNewComer: no, there cannot be any leftover pieces (the total weight of the apples equals the total weight that the children should receive). $\endgroup$ – Gamow Feb 16 '16 at 13:14
  • 3
    $\begingroup$ @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. $\endgroup$ – Gamow Feb 16 '16 at 13:16
9
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ @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? $\endgroup$ – wilson Feb 17 '16 at 7:11
  • 2
    $\begingroup$ @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 $\endgroup$ – Ivo Beckers Feb 17 '16 at 14:38
  • $\begingroup$ @Ivo fully understand now, thanks :) $\endgroup$ – wilson Feb 18 '16 at 2:01
4
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ 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 $\endgroup$ – Ivo Beckers Feb 16 '16 at 14:40
4
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Your proof doesn't work. Every time four 25-gram pieces go together, you decrement N but don't decrease the number of larger pieces, so there could be more than N large pieces. Try starting with 9 76-gram pieces and 8 127-gram pieces. $\endgroup$ – f'' Feb 17 '16 at 15:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.