Rotten apples

salem_ohio · 2017-03-07 01:15:34

Our local greengrocer had two bags with 17 apples in each. In the first bag, all apples are good, while in the other one, 5 of them are rotten to the core, but seem good to the outside. All the good apples weight the same and all the rotten also weight the same (but have different weight from the good ones). The greengrocer has sold one of the two bags, but without knowing which one! Now he is left with the other bag and wants to find out whether it contains all good apples, or it is the one with the 5 rotten. Using only a balance scale, what is the minimum number of weighings required to determine which bag he has?

phrontister · 2017-03-07 20:05:38

Hi salem_ohio;

How have you gone with this so far?

I'm down to 4 weighings (hope they're right!), but feel that it can be lowered further. Not too sure about my prospects, though, because I've tried for a while...

salem_ohio · 2017-03-07 21:57:01

Dear phrontister,
All I know is that it can be done with 3.
I have tried several ways: For example, 8+8+1 and we weigh the two sets of 8 together. If they balance, it can be either of the 2:
1. We have the bag with good apples
2. We have the bag with the rotten, and the 1 that was left out is a rotten one, and also that the other 4 are split 2+2.
Second weighting: We pick any of the two sets of 8 (which obviously are identical) and split them into 2 (4+4). If they balance, again it means that each subgroup has 2 rotten (or that we have the bag with the good apples).
But then again we have to make 2 more weightings to deduce... Thus a total of 4

I don't know!

Another idea would be to remove 3 instead of 1, and then split the remaining 14 into 2 groups. If they balance, again it means that the rotten are evenly split into the 2 groups, which means that in the remaining 3, we have an odd number of rotten (either 3 or 1). Then what?

thickhead · 2017-03-08 05:02:03

Beautiful concept!!
I think 2 weighings are enough.First weigh 5 and 5, leaving out 6.The rest is obvious. I hope it is not homework.

Last edited by thickhead (2017-03-08 05:09:29)

salem_ohio · 2017-03-08 06:18:32

thickhead wrote:

Beautiful concept!!
I think 2 weighings are enough.First weigh 5 and 5, leaving out 6.The rest is obvious. I hope it is not homework.

Dear thickhead,

I wish I were a bit younger, even if I had to do some tough homework I am already 36+

But the total number is 17; if we weigh 5 and 5, we leave out 7. Is this what you mean?

thickhead · 2017-03-08 07:08:18

It was an error,not typing but conceptual.I was trying 6,6,5 combination without success. Then I reduced the first and second to 5 but increased the third to 6 only.It should be seven. But my logic was based on 6.I was trying to weigh 3 and 3 of group C.Of course with total of 16 one weighing is enough.Now let us say A and B group 5 each weigh equally. Then weigh B against C but numbers are not same. Transfer 2 from A to B and weigh against C.you find b has already greater rotten apples than B or A is not having enough rotten applies to give to B to equalize with C. this logic had failed when I tried 6,6,5 combination because you had to remove one from B and the possession of A did not matter.

thickhead · 2017-03-08 17:59:00

phrontister · 2017-03-08 21:00:47

Xlnt, thickhead! Can't see anything wrong with that!

I was still at the stage of moving just 1 apple over, and then saw your post.

I'd got 4 min in nothing flat and it all seemed so open, so I was pretty sure there'd be a lower min...but not right down to 2!

salem_ohio · 2017-03-08 22:40:49

Guys, you are geniuses
I could not make it with less than 4...

Thank you!!

salem_ohio · 2017-03-08 23:32:02

thickhead wrote:

So, just to clarify:
After moving the 2 apples from A to B, it is ALWAYS unbalanced, unless we are in the bag with the good apples, right?

So, in essence, we can do it in 2 weighings?

phrontister · 2017-03-08 23:41:30

salem_ohio wrote:

So, just to clarify:
After moving the 2 apples from A to B, it is ALWAYS unbalanced, unless we are in the bag with the good apples, right?
So, in essence, we can do it in 2 weighings?

Exactly! To both questions.

Btw, thickhead's the genius, not me!

Here's my spreadsheet image of thickhead's answer, just looking at it a little differently (but essentially the same).

thickhead · 2017-03-09 04:24:14

Hi Salem_ohio,
As I had written earlier I had a wrong start.6:6:5 combination. but you had a better start. 8:8:1
on first weighing if A and B are equal, you conclude either it is all good apples or both lots have 2 rotten apples each.
Go for second weighing 4:4 of any of the lots. Split verdict indicates 1 rotten apple on each side. the third weighing 2:2 is the decider as this apple can not be divided.
My start with 6:6:5 combination was bad as it gave rise to 0:0:5,1:1:3 or 2:2:1 distribution of rotten apples.on second weighing C lot had to be weighed against A or B with one apple removed.It failed against 2:2:1 distribution. But wait, this also looks plausible.Let us say on second weighing we remove one from B and weigh the remaining 5 with C. a 0:0:5 or 1:1:3 distribution will make it unbalanced.If they are balanced it means it is 2:2:1 distribution and the one removed is a rotten apple. Add it to A to make make it 7 apple lot with 3 rotten apples in it.Add 2 apples from C to B. Now B may at the most contain 2 rotten apples and will be unbalanced against A in the third weighing.

Last edited by thickhead (2017-03-09 18:16:51)

phrontister · 2017-03-09 11:02:03

After first weighing A:B in a 6:6:5 combination and then transferring 1 apple from A to C, the second weighing, this time with B:C in a 5:6:6 combination, identifies that the transferred apple is bad.

I tried to use that information to solve the puzzle at the third weighing, but was unsuccessful. It might be possible, but I gave up looking when I saw thickhead's solution.

EDIT: Hi, thickhead. I just read your last post, where you gave the solution to the place where I'd got stuck with the 6:6:5, with the outcome that this combination can be solved in 3 weighings. Well done! I hadn't seen that the opportunity was there to increase a group's bad apple count to 3, which would always result in an imbalance.

Last edited by phrontister (2017-03-09 12:31:28)

phrontister · 2017-03-09 21:00:17

salem_ohio wrote:

So, just to clarify:
After moving the 2 apples from A to B, it is ALWAYS unbalanced, unless we are in the bag with the good apples, right?
So, in essence, we can do it in 2 weighings?

I don't think we've accounted properly for the possibility of the greengrocer having the bag of good apples...which I suspect would add a minimum of one weighing to each of the earlier results (but I haven't checked them all). That possibility should be eliminated before looking at the rotten apple options...unless it can be accounted for some other way.

I've tried to allow for this as follows:

Groups {A,B,C} = {7,7,3}.

Weigh A:B (7:7):

If not balanced, the bag has the rotten apples.

If balanced, remove 4 from A and weigh A:C (3:3).
EDIT: That line should read: If balanced, transfer 2 from A to C and weigh A:C (5:5).

If A:C (3:3) is also balanced, the greengrocer has the bag of good apples, otherwise he has the bag with the rotten apples (because, after having returned the 2 transferred apples to A, all other weighing combinations would yield an unbalanced result - which can be shown without any further weighing/s).

By this method, the minimum number of weighings required for the greengrocer to determine which bag he has is 2.

Last edited by phrontister (2017-03-10 21:13:15)

thickhead · 2017-03-10 03:47:34

With 7,7,3 how do you deal with 2:2:1 break of rotten apples?

phrontister · 2017-03-10 10:19:21

This was my reasoning for all possible rotten apple combinations and their respective weighings:

We have {A,B,C} = {7,7,3}.
That gives 2 options of rotten apple combinations: {1,1,3} and {2,2,1}.

Transferring 2 apples from A to C yields the following rotten apple options:
For {1,1,3}, it's {1,1,3} and {0,1,4}.
For {2,2,1}, it's {2,2,1}, {1,2,2} and {0,2,3}.

Weighing A:C is as follows:
For {1,1,3}, it's {1:3} and {0:4).
For {2,2,1}, it's {2:1}, {1:2} and {0:3}.

None of these weighings give a balanced result.

This image may help:

Last edited by phrontister (2017-03-10 15:20:43)

thickhead · 2017-03-10 15:34:02

That is excellent.but my query was for your posting in #14 removing 4 from A and weighing it (3:3) vs.C.
but in any way Salem_Ohio's start of 8,8,1 is to be admired as it is less taxing and shows the strength of binary division to the core(8 vs 8 ;4 vs 4; 2 vs 2 when rotten apples break down) even though it requires 3 weighings.

phrontister · 2017-03-10 16:57:15

You're right..I'd overlooked that.

I've added two red entries to my post #14. I've checked it a few times and I think it will now work.

I haven't looked at salem_ohio's {8,8,1} yet, but I will soon.

Last edited by phrontister (2017-03-10 21:04:02)

phrontister · 2017-03-11 09:46:57

thickhead wrote:

Salem_Ohio's start of 8,8,1 is to be admired as it is less taxing and shows the strength of binary division to the core(8 vs 8 ;4 vs 4; 2 vs 2 when rotten apples break down) even though it requires 3 weighings.

Yes, salem_ohio's {8,8,1} method is easily the most elegant one here, with its simpler, more logical approach:

Rotten apple numbers from the following weighings:
Split 16: W1 (8:8) = 0 or 2
Split 8: W2 (4:4) = 0 or 1
Split 4: W3 (2:2) is the decider: if there's 1 rotten apple left, it can't be split, and therefore a balanced weigh = all good apples, and unbalanced = rotten.

The final (2:2) weigh is either of these two: 2 good vs 2 good...for a balanced result; or 2 good vs (1 good + 1 bad)...for an unbalanced result.

Done in 3 weighings.

My 2-weigh solution of the {7,7,3} is very laborious, being just trial and error. It would be a pity if it was the winner as it would only win on minimum weighs, not technique. However, I've looked at it pretty closely and can't fault it yet.

And it looks like my {7,7,3} solution isn't the only 2-weigh one, either, because that strategy also seems to work for {5,5,7}. That would further sour the {7,7,3) result, as that means there are multiple solutions. I haven't tried my T&E strategy on other groups yet.

Last edited by phrontister (2017-03-11 11:45:40)

phrontister · 2017-03-13 22:59:01

Hi salem_ohio;

All I know is that it can be done with 3.

As thickhead showed in post #12, your {8,8,1} group can be done with 3 (see also my previous post), by what I suspect is the intended method: binary division, as thickhead said in post #17.

Anyway, here's my 'trial and error' solution for {5,5,7}, done in 2 weighings in much the same way as for {7,7,3}:

Groups {A,B,C} = {5,5,7}.

Weigh A:B (5:5):
1. If not balanced, the bag has the rotten apples.
2. If balanced, transfer 2 from A to B and weigh B:C (7:7).
(a) If also balanced, the bag has all good apples.
(b) If not balanced, the bag has the rotten apples.

The 2(b) result is possible without any further weighings. That is because, after returning the 2 transferred apples to A, all other weighing combinations would yield an unbalanced result...shown as follows:

We have {A,B,C} = {5,5,7}.
That gives 3 options of rotten apple combinations: {0,0,5}, {1,1,3} and {2,2,1}.

Transferring 2 apples from A to B yields the following rotten apple options:
For {0,0,5}, it's {0,0,5}.
For {1,1,3}, it's {1,1,3} and {0,2,3}.
For {2,2,1}, it's {2,2,1}, {1,3,1} and {0,4,1}.

Weighing A:C is as follows:
For {0,0,5}, it's {0:5}.
For {1,1,3}, it's {1:3} and {2:3).
For {2,2,1}, it's {2:1}, {3:1} and {4:1}.

None of these weighings give a balanced result.

By this (laborious) method, the minimum number of weighings required for the greengrocer to determine which bag he has is 2.

This image may help:

Last edited by phrontister (2017-03-14 10:42:41)

Math Is Fun Forum

#1 2017-03-07 01:15:34

Rotten apples

#2 2017-03-07 20:05:38

Re: Rotten apples

#3 2017-03-07 21:57:01

Re: Rotten apples

#4 2017-03-08 05:02:03

Re: Rotten apples

#5 2017-03-08 06:18:32

Re: Rotten apples

#6 2017-03-08 07:08:18

Re: Rotten apples

#7 2017-03-08 17:59:00

Re: Rotten apples

#8 2017-03-08 21:00:47

Re: Rotten apples

#9 2017-03-08 22:40:49

Re: Rotten apples

#10 2017-03-08 23:32:02

Re: Rotten apples

#11 2017-03-08 23:41:30

Re: Rotten apples

#12 2017-03-09 04:24:14

Re: Rotten apples

#13 2017-03-09 11:02:03

Re: Rotten apples

#14 2017-03-09 21:00:17

Re: Rotten apples

#15 2017-03-10 03:47:34

Re: Rotten apples

#16 2017-03-10 10:19:21

Re: Rotten apples

#17 2017-03-10 15:34:02

Re: Rotten apples

#18 2017-03-10 16:57:15

Re: Rotten apples

#19 2017-03-11 09:46:57

Re: Rotten apples

#20 2017-03-13 22:59:01

Re: Rotten apples

Board footer