Math Is Fun Forum
  Discussion about math, puzzles, games and fun.   Useful symbols: ÷ × ½ √ ∞ ≠ ≤ ≥ ≈ ⇒ ± ∈ Δ θ ∴ ∑ ∫ • π ƒ -¹ ² ³ °

You are not logged in.

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

salem_ohio
Member
Registered: 2016-03-11
Posts: 37

Rotten apples

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?

Offline

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

phrontister
Real Member
From: The Land of Tomorrow
Registered: 2009-07-12
Posts: 4,592

Re: Rotten apples

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


"The good news about computers is that they do what you tell them to do. The bad news is that they do what you tell them to do." - Ted Nelson

Offline

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

salem_ohio
Member
Registered: 2016-03-11
Posts: 37

Re: Rotten apples

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 sad

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?

Offline

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

thickhead
Member
Registered: 2016-04-16
Posts: 1,077

Re: Rotten apples

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)


{1}Vasudhaiva Kutumakam.{The whole Universe is a family.}
(2)Yatra naaryasthu poojyanthe Ramanthe tatra Devataha
{Gods rejoice at those places where ladies are respected.}

Offline

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

salem_ohio
Member
Registered: 2016-03-11
Posts: 37

Re: Rotten apples

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 smile I am already 36+ tongue tongue

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

Offline

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

thickhead
Member
Registered: 2016-04-16
Posts: 1,077

Re: Rotten apples

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.


{1}Vasudhaiva Kutumakam.{The whole Universe is a family.}
(2)Yatra naaryasthu poojyanthe Ramanthe tatra Devataha
{Gods rejoice at those places where ladies are respected.}

Offline

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

thickhead
Member
Registered: 2016-04-16
Posts: 1,077

Re: Rotten apples


{1}Vasudhaiva Kutumakam.{The whole Universe is a family.}
(2)Yatra naaryasthu poojyanthe Ramanthe tatra Devataha
{Gods rejoice at those places where ladies are respected.}

Offline

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

phrontister
Real Member
From: The Land of Tomorrow
Registered: 2009-07-12
Posts: 4,592

Re: Rotten apples

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

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! smile


"The good news about computers is that they do what you tell them to do. The bad news is that they do what you tell them to do." - Ted Nelson

Offline

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

salem_ohio
Member
Registered: 2016-03-11
Posts: 37

Re: Rotten apples

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

Thank you!!

Offline

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

salem_ohio
Member
Registered: 2016-03-11
Posts: 37

Re: Rotten apples

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?

Offline

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

phrontister
Real Member
From: The Land of Tomorrow
Registered: 2009-07-12
Posts: 4,592

Re: Rotten apples

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

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

n8YrYdb.jpg


"The good news about computers is that they do what you tell them to do. The bad news is that they do what you tell them to do." - Ted Nelson

Offline

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

thickhead
Member
Registered: 2016-04-16
Posts: 1,077

Re: Rotten apples

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)


{1}Vasudhaiva Kutumakam.{The whole Universe is a family.}
(2)Yatra naaryasthu poojyanthe Ramanthe tatra Devataha
{Gods rejoice at those places where ladies are respected.}

Offline

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

phrontister
Real Member
From: The Land of Tomorrow
Registered: 2009-07-12
Posts: 4,592

Re: Rotten apples

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! smile 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. sad

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


"The good news about computers is that they do what you tell them to do. The bad news is that they do what you tell them to do." - Ted Nelson

Offline

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

phrontister
Real Member
From: The Land of Tomorrow
Registered: 2009-07-12
Posts: 4,592

Re: Rotten apples

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)


"The good news about computers is that they do what you tell them to do. The bad news is that they do what you tell them to do." - Ted Nelson

Offline

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

thickhead
Member
Registered: 2016-04-16
Posts: 1,077

Re: Rotten apples

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


{1}Vasudhaiva Kutumakam.{The whole Universe is a family.}
(2)Yatra naaryasthu poojyanthe Ramanthe tatra Devataha
{Gods rejoice at those places where ladies are respected.}

Offline

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

phrontister
Real Member
From: The Land of Tomorrow
Registered: 2009-07-12
Posts: 4,592

Re: Rotten apples

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:

7EeybEO.jpg

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


"The good news about computers is that they do what you tell them to do. The bad news is that they do what you tell them to do." - Ted Nelson

Offline

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

thickhead
Member
Registered: 2016-04-16
Posts: 1,077

Re: Rotten apples

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.


{1}Vasudhaiva Kutumakam.{The whole Universe is a family.}
(2)Yatra naaryasthu poojyanthe Ramanthe tatra Devataha
{Gods rejoice at those places where ladies are respected.}

Offline

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

phrontister
Real Member
From: The Land of Tomorrow
Registered: 2009-07-12
Posts: 4,592

Re: Rotten apples

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

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)


"The good news about computers is that they do what you tell them to do. The bad news is that they do what you tell them to do." - Ted Nelson

Offline

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

phrontister
Real Member
From: The Land of Tomorrow
Registered: 2009-07-12
Posts: 4,592

Re: Rotten apples

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)


"The good news about computers is that they do what you tell them to do. The bad news is that they do what you tell them to do." - Ted Nelson

Offline

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

phrontister
Real Member
From: The Land of Tomorrow
Registered: 2009-07-12
Posts: 4,592

Re: Rotten apples

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:

xG6LO8o.jpg

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


"The good news about computers is that they do what you tell them to do. The bad news is that they do what you tell them to do." - Ted Nelson

Offline

Board footer

Powered by FluxBB