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:
]]>
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.
]]>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.
]]>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:
]]>
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.
]]>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.
]]>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).
]]>
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?
]]>Thank you!!
]]>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!
]]>