The golf ball riddle

rgiller

One of the tougher ones:

So at a driving range there are six golf ball dispensing machines. Five of them give out golf balls of exactly the same size and weight (10 grammes) but the other gives out balls of the same size but double the weight (20 grammes). ie All balls are the same size but the balls from one machine are twice as heavy as the ones from the other machines. You have no idea which machine gives out the heavy ball but you have to find out. To help you you have a weighing scales but the catch is that you're only allowed to use it once. This means you can't just take one ball from each machine and weigh it individually. Also, you can't put in one ball from each machine and take them out one at a time and weigh the remainder. You can't judge their weight by holding them in your hand or put any marks on the balls at all. You can only put balls on the weighing scales altogether and find out from that one weight. How do you do it?

PS This is the most number of times I've ever written the word balls in one go

dudara

Take 6 from Machine A, 5 from Machine B and so on. Work out what that should weigh if they were all 10g = 210g.

Now weigh them and subtract 210g from it. The difference will be a multiple of 10. If it's 20, then bin E (where you took two balls from) contains the heavier balls.

ianmc38

Yeah i';ve seen this riddle in many guises, usually as gold bars.

w66w66

a similar classic:
You have twelve coins, eleven identical and one different. You do not know whether the "odd" coin is lighter or heavier than the others. Someone gives you a balance scale and three chances to use it. The question is: How can you make just three weighings on the balance scale and find out not only which coin is the "odd" coin, but also whether it's heavier or lighter?

besty

My brain hurts!

Bill McH

w66w66 - a quick question for clarification.

By "balance scale" do you mean an arrangement where it is possible to compare the weight of, say, 3 coins on one side versus 3 coins on the other side - rather than a conventional weighing scales where you might measure the weight of something by comparing it to known weights (e.g. a kitchen weighing scales).

w66w66

It would be, 3 coins on one side versus 3 coins on the other side. eg http://www.cdc.gov/diabetes/pubs/images/balance.gif

TIP: I found solving this easier variation of the puzzle helpful for solving the tougher one.
You have 9 gold coins. All 9 coins look exactly the same but one coin is a fake and is either lighter or heavier than the other 8 coins. You have a balance scale but can only load it twice. How do you find the fake gold coin?

Bill McH

w66w66 wrote:

It would be, 3 coins on one side versus 3 coins on the other side. eg http://www.cdc.gov/diabetes/pubs/images/balance.gif

OK, thanks.

w66w66 wrote:

TIP: I found solving this easier variation of the puzzle helpful for solving the tougher one.
You have 9 gold coins. All 9 coins look exactly the same but one coin is a fake and is either lighter or heavier than the other 8 coins. You have a balance scale but can only load it twice. How do you find the fake gold coin?

And thanks again. I'll try that. 'Cos I'm stumped with the other one. I was working on the basis that it was a scale such as the one illustrated in the link. I am currently dividing the twelve coins into 3 groups of four (lets call them A,B and C). If I measure A versus B and they balance, then it must be one of the coins in group C. I can then measure 3 of the coins of group A against 3 of the coins in group C. If they balance, the odd coin must be fourthcoin in group C, and I can measure it against any of the group A or B coins to see if it's heavier or lighter than it should be. If, when I measure the three coins from group A against the three coins from group C and they don't balance, I know that the coin I'm looking for is one of those three from group C. I can also tell whether the odd coin is heavier or lighter, depending on whether the three C coins are heavier or lighter than the three A coins. If I then take two of these three C coins and measure them against each other I can find out which (if either) of them is heavier or lighter. If they are the same weight, the elusive coin is the third coin.

But what I can't do is figure out a way to find the odd coin if, when I measure group A versus group B, they don't balance. Grrrr.:D

Maybe it'll be easier if the new 9 coin puzzle can be solved.

Bill McH

I'm just going to rephrase some of that, hopefully to make it clearer.

I am currently dividing the twelve coins into 3 groups of four (lets call them A,B and C). If I measure coins A1+A2+A3+A4 on one side versus coins B1+B2+B3+B4 on the other side and they balance, then it must be one of the coins in group C.

I can then measure A1+A2+A3 against C1+C2+C3. If they balance, the odd coin must be coin C4. I can then measure C4 against any of the group A or B coins to see if it's heavier or lighter than it should be.

If I measure A1+A2+A3 against C1+C2+C3 and they don't balance, I know that the coin I'm looking for is C1, C2 or C3. I can also tell whether the odd coin I'm looking for is heavier or lighter, depending on whether A1+A2+A3 is lighter or heavier than C1+C2+C3. Now that I know whether I'm looking for a heavier or a lighter coin, I can then measure C1 against C2 to find out which (if either) of them is heavier or lighter and decide which of C1 or C2 is the elusive coin. If C1 and C2 are the same weight, the elusive coin is C3.

That seems to be the easy part. Still pretty clueless about the situation where, If I measure coins A1+A2+A3+A4 on one side versus coins B1+B2+B3+B4 on the other side, they don't balance.

w66w66

Sorry Bill Mch, forget that one about the nine coins, it's incorrect. Here's the proper easier version:
You have 8 marbles that weigh 1 ounce each, & 1 marble that weighs 1.5 ounces. You are unable to determine which is the heavier marble by looking at them. You have a balance weighing scale, but the scale is only good for 2 total weighings. How can you determine which marble is the heaviest one using the scale, & in only 2 weighings?

Hint: Your on the right track with the 12 coins puzzle.

Bill McH

w66w66 wrote:

You have 8 marbles that weigh 1 ounce each, & 1 marble that weighs 1.5 ounces. You are unable to determine which is the heavier marble by looking at them. You have a balance weighing scale, but the scale is only good for 2 total weighings. How can you determine which marble is the heaviest one using the scale, & in only 2 weighings?

Hint: Your on the right track with the 12 coins puzzle.

Hmmmm.

Well, if I'm on the right track, I suppose you could again divide the marbles up into 3 groups (A, B and C). So you'd have marbles A1, A2, A3 in group A, marbles B1, B2 and B3 in group B and marbles C1 and C2 in group C.

So you measure A1+A2+A3 against B1+B2+B3. If they balance, the heavier marble must be C1 or C2. If you weigh them against each other you'll find out which one is heavier.

But if A1+A2+A3 does not balance with B1+B2+B3, then the heavy marble is one of those six, and you can tell whether its an A or a B marble by seeing which of groups A or B is heavier on the scale.

Let's say group B is heavier. So now you measure B1 against B2. If they balance, the heavy marble is B3. If they don't, then it is whichever of B1 or B2 is heavier.

Seems like there's going to be some jump from that to the 12 coin puzzle:D

Bill McH

Ooops, silly me, I read it wrong. I thought it was a total of 8 marbles, but now I see that it's 8 @ 1 ounce and 1 @ 1.5 ounces.


Back to the drawing board.

Bill McH

Hopefully, I've read the question right this time.:o
9 marbles, 8 of them @ 1 ounce, 1 of them @ 1.5 ounce.

As before, I'm going to divide the marbles up into 3 groups (A, B and C). So there are marbles A1, A2, A3 in group A, marbles B1, B2 and B3 in group B and marbles C1, C2 and C3 in group C.

So now I'm going to measure A1+A2+A3 against B1+B2+B3. If they balance, the heavier marble must be C1, C2 or C3. If I then weigh C1 against C2 and they balance, then the heavy marble is C3. If C1 and C2 do not balance, the heavier of them is the 1.5 ounce marble.

If A1+A2+A3 does not balance with B1+B2+B3, then the heavy marble is one of those six, and I can tell whether its an A or a B marble by seeing which of groups A or B is heavier on the scale.

Let's say group B is heavier. So I'm now going to measure B1 against B2. If they balance, the heavy marble is B3. If they don't, then it is whichever of B1or B2 is heavier.

So not all that different, in any case. (Though I can do without the "READ THE QUESTION" memories flooding back:D ).

Drakar

I've seen the solution to the 12 coins question and it's far from trivial.

Bill McH

Drakar wrote:

I've seen the solution to the 12 coins question and it's far from trivial.

Too right! I'm afraid I crumbled early this morning and I went looking for a solution.:o I'm glad I did, because I might have been working on this for years and never come up with the solution.

It's really very neat. I'll post up my interpretation of it later on, if there are no objections.

As usual, w66w66 comes up with a really good problem.:)

w66w66

Bill McH wrote:

Too right! I'm afraid I crumbled early this morning and I went looking for a solution.:o I'm glad I did, because I might have been working on this for years and never come up with solution

funnily enough, I read an email on a website once from guy who'd been at this for a year and still hadn't cracked it.

QUOTE=Drakar]I've seen the solution to the 12 coins question and it's far from trivial.[/QUOTE]

I've even seen literature from mathematicians about this puzzle, in which they admitted it was quite a struggle.

Bill McH

In fact, I'm confident that I would never have got it out.

What follows is my interpretation of what I saw.

If groups A and B, when measured against each other, do not balance, then it will appear that one side of the scales will be heavier and the other side will be lighter. This will be due to the presence of the rogue coin, which will either be heavier or lighter than the norm. So, let's take the coins from whichever side is heavier and rebrand them as group H. The lighter group can also be rebranded as group L. The third group, group C, could be left as it is. But as this group must contain all neutral weight coins, let's change it to group N.

As above, the trick is to now measure the coins in groups of three. We can lay out the coins as follows: 2 heavy, 2 light, 2 heavy, 2 light:

H1, H2, L1, L2, H3, H4, L3, L4

Place a neutral coin in the middle, to get:

H1, H2, L1, L2, N1, H3, H4, L3, L4

Then, working from the left, divide them into 3 groups of three:

(H1, H2, L1), (L2, N1, H3) and (H4, L3, L4).

Then weigh the left hand and middle groups against each other, i.e., H1+H2+L1 versus H3+L2+N1

If these two groups balance, then the rogue coin must be one of the coins which is not being weighed, i.e., H4, L3 or L4. So weigh L3 against L4. Whichever is lighter must be the rogue coin, and it is lighter than all the rest. If they balance, the rogue coin must be H4, and it is heavier than all the others.

If the left hand side of the balance is heavier, this is either because H1+H2+L1 contains a heavy coin or because H3+L2+N1 contains a light coin. We know that L1 cannot be a heavy coin, so it could be that H1 or H2 is a heavy coin. We know that H3 cannot be a light coin, so it could be that L2 is a light coin. So the possibilities are that H1 or H2 are a heavy coin, or L2 is a light coin. So measure H1 against H2. If they do not balance, the heavier of the two is the bogus coin and it is heavier than the others. If they do balance, then L2 is lighter than all the other coins.

If the right hand side of the balance is heavier, this is either because H3+L2+N1 contains a heavy coin, or because H1+H2+L1 contains a light coin. We know that L2 cannot be a heavy coin, so it could be because H3 is a heavy coin. We know that H1+H2 cannot be light coins, so it could be because L1 is a light coin. So the possibilities are that H3 is heavy or L1 is light. By measuring either of these against a known neutral coin, such as N1, the bogus coin can be found.

Bill McH

Oh by the way, w66w66, I'm assuming that we're allowed put little labels on these coins without compromising their relative weight. Otherwise it could be quite difficult to keep track.

w66w66

it's as easy as that.

now try it with 120 marbles and 5 weighs. I would guess it's pretty straight forward.

w66w66

Bill McH wrote:

Oh by the way, w66w66, I'm assuming that we're allowed put little labels on these coins without compromising their relative weight. Otherwise it could be quite difficult to keep track.

of course

Bill McH

w66w66 wrote:

it's as easy as that.

now try it with 120 marbles and 5 weighs. I would guess it's pretty straight forward.

Can I take it that that is 120 marbles - 119 of which have a common weight?

5 weighs.

Hmmmm.

w66w66

yep.
I could do it but i just don't to.:D

Bill McH

Well, w66w66, you're going to have to strut your stuff here:p Are you sure it's doable?

I suppose you could bundle them into groups of 10 and use the method of the 12 coin puzzle to identify which group of 10 marbles contained the rogue marble. That's three weighings. Those three weighings would also identify whether the marble you're looking for is a light marble or a heavy marble.

I can't yet see how I could use just two further weighings to identify the rogue marble from those 10. Thinking back to your earlier 9-marble puzzle, where you know whether the marble is heavy or light, I think I'd need three to identify it from 10.

Now if it was just 108 marbles from five weighings, well that'd be easy peasy:D

Any guidance would be appreciated:)

w66w66

Bill McH wrote:

Well, w66w66, you're going to have to strut your stuff here:p Are you sure it's doable?

according this webpage yes, see table, http://home.att.net/~numericana/answer/weighing.htm#counterfeit.

Bill McH wrote:

I suppose you could bundle them into groups of 10 and use the method of the 12 coin puzzle to identify which group of 10 marbles contained the rogue marble. That's three weighings. Those three weighings would also identify whether the marble you're looking for is a light marble or a heavy marble.

I was thinking something along those lines. What i had in mind was making 10 groups of 12 and then trying idenfity which group it was with false marbles in two weighings. then'd i'd have 12 marbles and three weighs left. but I dont' think that's the method, It doesn't seem possible.

Bill McH wrote:

Any guidance would be appreciated:)

So far i've one way in which it would possible to identify a false marble:
Three bags of 40 A,B,C. Weigh A by B and if they're equal you know it's C.

Then make three groups with C, A with 14, B with 14, and C with 12.
Then weigh A by B, and if they're equal you know it's C.
So now you have three weighings to get C, which is the same as the original 12 coin problem. Apart from that I'm stumped.

Bill McH

w66w66, I'm hoping to have a good read of that webpage over the next few days, as it looks interesting. I can't at the moment settle down to read it. But thanks for posting it up.

We may yet get it out:)

w66w66

I think a have a solution for 120 coin problem, so I’ll attempt to explain it.
Now it would far too difficult to explain the whole thing step by step, so instead I’ll firstly explain how to find a fake coin with 9 coins plus extra good coins in two moves with a group of 4 that have a possibly lighter coin and with a group of 5 that has a possible heavier coin (could also be the other way around). And also how to find a fake coin with 13 coins plus one extra good coin in three moves. And Finally how to find a fake coin with 27 coins, plus extra good coins, with 13 coins that have a possibly lighter coin and 14 coins which have a possibly heavier coin in three moves. The reason way I’m breaking the problem down like this is because essentially what I’m going to do is break down the 120 coins into these three problems.
So firstly:
You have Nine coins, one Group (A) of 5 coins that might a heavier one in it and another group(B) of 4 that might a lighter one in it, plus extra good coins, find the counterfeit coin in three weighs on a balance scale:
Move 1: Firstly take 2 coins from A and 1 from B and leave them aside in group C, leaving 3 and 3. Then take one coin from A and put it in with group B, and then take two from B and put them in With Group A. Also put Two good coins (K) in with group B. So that should be on one side of the scale, A, B ,K ,K by B, B, A, A, on another . Weigh them and if side one is heavier that means that either A on side one is heavier or B, B on side two is lighter.2: Weigh B by B and if one is lighter you have the counterfeit coin and if they are the same counterfeit coin is A and it’s heavier. If side A, B, K, K was lighter, weigh A by A and if one is heavier it’s the counterfeit coin, and if they are the same the counterfeit coin is B and its lighter. If A, B, K, K by B, B, A, A are equal then counterfeit coin is in group C. So from group C weigh A by A and if one is heavier you have counterfeit coin and if equal B is counterfeit coin and it’s lighter.
Next: You have 13 coins with one counterfeit coin which is lighter or heavier, and extra coin good coin(s), find the counterfeit in three weighs on a balance scale:
1: break the 13 coins up into three groups, A, B, C, with 5 in A, 4 in B, and 4 in C.
Now weigh A by B with the extra good coin in B, so that’s 5 by 5. If equal than F(fake coin) is in C.
2: So now break C in three groups A, B, C, with 2 in A, 1 in B and 1 in C.
Leave C aside and weigh A, A, by B, K. 3: If side A, A is heavier then weigh A by A and if one is heavier you have F. If the A by A is the same F is B and its lighter. If A by A, is lighter it’s the same method again. If A, A, by B, B where equal than F is in C. Weigh C by K to determine whether heavier or lighter.
1: Going back to move one, if A by B where uneven, with let’s say A being heavier, you now 5 coins which are possibly heavier and 4 coins which are possibly lighter coins, with two moves left. So that’s basically the 9 coin problem again, so just use that method to solve the rest of the problem
And Finally: You have 27 coins in two groups with one of 14 group(A) containing A possibly heavier coin and another of 13 group(B) containing A possibly lighter coin, plus extra good coins(K). Determine counterfeit coin in three weighs.
1:Firstly break the coins into three groups, take 5 from group A and 4 from group B and leave them aside in group C, leaving 9 and 9. Now take 5 from A and put them in with B and take 4 from B and put them in with A plus two K’s. So on one side you have AAAAA,BBBBB and on the other BBBB,AAAA,K,K. Weigh them and if the first side is heavier its means either AAAAA has heavier coin or BBBB has lighter coin, this leaves you with 9 coin problem with 2 moves as demonstrated above. Same goes for if side one is lighter, and if they the weigh the same, then again you are left with the 9 coin problem with group C to solve the rest of the problem. Now if these methods are all correct I can then use them to solve the 120 coin problem, so here goes.
You 120 coins, one is counterfeit, it’s either lighter or heavier you don’t know which, find the counterfeit coin in 5 weighs on a balance scale.
1:Firstly put them into three groups of 40 A,B, and C. Weigh A by B and if equal F is in C.
2: Put C into three groups A, B and C. Put 14 in A , 13 In B , and 13 In C. Now weigh A by B with one known good coin in B, so that’s 14 by 14. If equal F is in C. This leaves you with the 13 coin problem as demonstrated above to solve C. If A by B where unequal then this leaves you with the 27 coin problem as demonstrated above to complete the problem.
1:Going back to move one, if A by B where unequal, with let’s say A being heavier, then take 14 from A and 13 from B and put them aside into C. Leaving 26 in A and 27 in B. Now take 13 from A and put them in with B and then take 14 from B and put them into A, also put one K into group B. So that should be B(14)A(13) on one side and A(13)B(13)K on the another.
2: So now weigh B(14)A(13) by A(13)B(13)K(1). If equal then F is in Group C which is leaves you with the 27 coin problem as demonstrated above to complete problem. If B(14)A(13) by A(13)B(13)K(1) are unequal, with lets say side one being heavier, then that means that either A(13) on side one has a heavier coin or B(13) on side two has a lighter coin. This basically leaves with the 27 coin problem, with 26 coins instead of 27. And if B(14)A(13) by A(13)B(13)K(1) are unequal with side one being lighter, this again it’s leaves you with the 27 coin problem to complete the problem.

I think that's it, can't find anywhere to verify it though, but it seems correct.

Bill McH

I'm looking forward to reading that post too - just can't get a minute at the moment.:(

Bill McH

I’m working my way through this, slowly but surely. There are a lot of letters being juggled around so I’m finding it hard not to lose track.

A quick question though, w66w66. Am I correct in thinking that your solution to the 9-coin, 13-coin, etc. problems only work as a "subset" of the 120 coin problem. i.e. where you have already established whether the groups you're examining contain an apparently heavy coin or an apparently light coin. It's kind of difficult to express what I mean, so I'll give an example based on your solution to the 9-coin problem.

You've got 9 coins and known good coins (G), and you've divided your 9 coins into groups A and B, as follows:

(A1,A2,A3,A4,A5) and (B1,B2,B3,B4)

Then you've rearranged these coins and use a couple of good coins, as follows:

#1(A1,B1,G1,G2), #2(A2,A3,B2,B3) and #3(A4,A5,B4)

And then you've carried out weighing 1: Weigh #1 against #2.

w66w66 wrote:

Weigh them and if side one is heavier that means that either A on side one is heavier or B, B on side two is lighter.

If you hadn't already established from an earlier stage that group A may contain a heavier coin and that group B may contain a lighter coin, then surely it is possible that either A1 or B1 is heavier or that any one of A2,A3,B2,B3 is lighter.

Hope you get my drift.

Interesting that you are actually making this 9-coin problem easier by making it into an 11-coin problem!:D

w66w66

Bill McH wrote:

A quick question though, w66w66. Am I correct in thinking that your solution to the 9-coin, 13-coin, etc. problems only work as a "subset" of the 120 coin problem. i.e. where you have already established whether the groups you're examining contain an apparently heavy coin or an apparently light coin. It's kind of difficult to express what I mean, so I'll give an example based on your solution to the 9-coin problem.

If you hadn't already established from an earlier stage that group A may contain a heavier coin and that group B may contain a lighter coin, then surely it is possible that either A1 or B1 is heavier or that any one of A2,A3,B2,B3 is lighter

yes they're a subset to the 120 coin problem, and yes i've already established whether the groups i'm examining contain an apparently heavy coin or an apparently light coin.
E.G if I had six coins with one coin been heavier or lighter, and then put them in to two groups A and B, weighed them, and if A was heavier and B was lighter, then i'd be left with a six coin problem with group A having a possible heavier coin and group B having possible lighter coin. I now know that A can't have a lighter coin and B can't have a heavier coin. similarly in the 9 coin problem I have established that A can't have a lighter coin and B can't have a heavier coin.

Bill McH

w66w66 wrote:

Next: You have 13 coins with one counterfeit coin which is lighter or heavier, and extra coin good coin(s), find the counterfeit in three weighs on a balance scale:
1: break the 13 coins up into three groups, A, B, C, with 5 in A, 4 in B, and 4 in C.
Now weigh A by B with the extra good coin in B, so that’s 5 by 5. If equal than F(fake coin) is in C.
2: So now break C in three groups A, B, C, with 2 in A, 1 in B and 1 in C.
Leave C aside and weigh A, A, by B, K. 3: If side A, A is heavier then weigh A by A and if one is heavier you have F. If the A by A is the same F is B and its lighter. If A by A, is lighter it’s the same method again. If A, A, by B, B where equal than F is in C. Weigh C by K to determine whether heavier or lighter.

1: Going back to move one, if A by B where uneven, with let’s say A being heavier, you now 5 coins which are possibly heavier and 4 coins which are possibly lighter coins, with two moves left. So that’s basically the 9 coin problem again, so just use that method to solve the rest of the problem

w66w66, I think you're right with the 9 coin and 27 coin scenarios, and it's tremendous work on your part. It is actually the 13 coin scenario that I have some difficulty with. In the bold bit above, the group C actually contain the only coins which have not at any stage been on the balance in the three weighings so far, so you have no idea whether you're looking for a heavier or a lighter coin.

(If you don't mind, I'm just going to rejig the letters a bit - as much so that I can follow it as that you can:o )

So now break C in three groups P, Q and R, with 2C coins in P, 1C coin and one known good coin (G) in Q and 1C coin in R.
Leave R aside and weigh P against Q (P1,P2 against Q1,G). This is weighing #4. If they are the same then the dodgy coin is coin R1. And then you can use weighing #5 to establish whether it's heavier or lighter than the good coins.

If P and Q are not the same, you could weigh P1 against P2 in weighing #5. If they are the same, then the dodgy coin is Q1. And you can tell from the way weighing #4 went whether it was heavier or lighter than the other coins.

But if P1 and P2 are not the same weight in weighing #5, how do you tell which of P1 and P2 is the dodgy coin? Or whether it's heavier or lighter than the others?

Bill McH

No, of course you can scratch that. What a silly post:o

If P1 and P2 are not the same weight in weighing #5, how do you tell which of P1 and P2 is the dodgy coin? Or whether it's heavier or lighter than the others?

Of course, in that scenario, you'd know from the results of weighing #4 whether the dodgy coin is heavier or lighter, as it would be either heavier or lighter than the combination of Q1 and the good coin.



So, tremendous work, w66w66.

Hats off.:)

w66w66

Bill McH wrote:

So, tremendous work, w66w66.

Hats off.

Thank you, but I have to say I found the 12 coin problem harder, as the principles behind the 120 coin are bascially the same as the coin 12 one but on a larger scale. For example one could easily apply the principles behind the 120 coin problem solution to the 1092 coin problem with 7 weighs, and on and on and on.
figuring out these principles is the truly difficult part.