Author Topic: Age Old Problem (Read 5003 times)

Hooman · « **on:** October 27, 2005, 07:47:47 PM »

Suppose you have 9 coins. Of these, 8 are of equal weight, and 1 is heavier than the others. Suppose you are trying to determine which coin is the heavy one, with absolute certainty, using a fair balance. What is the minimum number of measures, and how is it done?

HaXtOr · « **Reply #1 on:** October 27, 2005, 09:12:07 PM »

ducktape, hammer and a shotgun... thats how it is done

Hooman · « **Reply #2 on:** October 27, 2005, 09:28:49 PM »

Umm, right. Any serious answers?

... and the duct tape I can understand, but the shotgun? :blink:

Stormy · « **Reply #3 on:** October 27, 2005, 10:26:16 PM »

Hmm, your brain?, a triple beam balance, and your hand :lol:

Betaray · « **Reply #4 on:** October 27, 2005, 10:28:35 PM »

through them in the air, and the one that hurts the most when it hits your face is the heaviest

spirit1flyer · « **Reply #5 on:** October 28, 2005, 09:51:04 AM »

put 4 coins on one side of a scale and 4 on the other. if there is no change you know the coin is the one left and if there is a change you only have to do 2 more tests

Eddy-B · « **Reply #6 on:** October 28, 2005, 12:48:52 PM »

Quote

put 4 coins on one side of a scale and 4 on the other. if there is no change you know the coin is the one left and if there is a change you only have to do 2 more tests

Nice try spirit, but i can do it in just 2 go's B) > you know: 1 measuring, and then another 1, and i'll tell u which one is the heavier coin

i'm not (yet) gonna tell u how, but i promise you, it can be done

YOU figure it out too.
(i'll pm hooman the answer - so at least HE will know i'm not cheating, by just waiting for the answer and then saying: thats what i was thinking also ..)

So, the answer is: TWO

CK9 · « **Reply #7 on:** October 28, 2005, 03:54:22 PM »

let's see...9 coins, 1 heavier... I've seen this one before, but it's been soooo long...

with spirit's answer there, the minimum is 1...but Eddy believes the answer is two...and I think I just realized Eddy's veiw point!

Sirbomber · « **Reply #8 on:** October 28, 2005, 03:59:19 PM »

Just one.
Melt all the coins and keep them separate.
Whichever one is a different metal/color/whatever, there you go.

Mez · « **Reply #9 on:** October 28, 2005, 05:56:13 PM »

I would say 3, using spirit's method, but im intrigued to find out what eddys answer is,

Assuming that you have 4 coins, 1 which is heavier than the rest....

can't get beyond that point ( to make 1 more measure)

CK9 · « **Reply #10 on:** October 29, 2005, 02:17:09 AM »

well, mezza, with spirit's way, you measure 4 against 4 and you have 1 left. If they 8 you measure balance on that first weighing, then you know the nineth is the one

Hooman · « **Reply #11 on:** October 29, 2005, 05:56:14 PM »

Eddy is correct. This can be done with 2 weighings.

This kinda has a nice parallel with Huffman codes actually.

HaXtOr · « **Reply #12 on:** October 30, 2005, 08:58:20 PM »

are the coils all teh same size? is so what material are they made of ? you could go by densityof the metatls if you know what they are made of.

with the duck tape you make a gun cartrage for the shotgun and shoot the coins into your head to see wich one goes the deepest, that is the heavier coin

Hooman · « **Reply #13 on:** October 30, 2005, 10:00:17 PM »

Umm, yes. Well ignoring the excessive violence from the last post....

The idea of weighing 4 coins at a time allows you to determine with certainty that the odd coin out is the heavier one IF the 8 coins all balance out. What if they don't? then it takes more tries to determine which one of the remaining is the heavier one.

If on the other hand, you determined less info about that one particular coin that isn't weighed, but more info about the rest, then you might be able to determine which one is heavier (with certainty in all cases) in fewer tries, but you won't be able to solve it on your first try no matter what.

Sorta like how Huffman codes work. If say you represent possibities by the following bit strings:
0
100
101
110
then with a single bit, you can determine if the first message was sent, provided that bit was a 0. But if it's a 1, you know less about the remaining 3, only that it must be one of them (provided these are the only possible strings received). If you were to rebalance things a little as follows:
00
01
10
11
then you can represent all 4 cases with fewer average bits. However, you can't determine what a message is from only the first bit. You must get at least 2 bits to be certain. (You also have a shorter maximum code length in this case).

Of course the idea of Huffman codes was to keep the *average* length to a minimum, based on the probability of each of the possible messages. This question is about keeping the maximum length down to a minimum. Huffman codes just have a way of making tradeoffs between the maximum length of a code and the average length of code words. Mind you..., for cases were all outcomes are equally probable, these are the same thing....

Eddy-B · « **Reply #14 on:** October 31, 2005, 02:22:38 AM »

Hooman, not everyone on this forum understands coding, Huffman and your explaination about bits. Maybe it's better to stick with the weighing scale and the coins instead..

Hooman · « **Reply #15 on:** October 31, 2005, 02:58:35 AM »

You're probably right. I just tend to get a little carried away sometimes. Anyways, I just happen to think of this problem in terms of information theory since that's where I last saw it introduced. It kinda relates well to the concepts in that course, but yeah. It's a little overkill.

So yes, weigh coins and see if you can find the right one. It can be done with only two weighings.

Mez · « **Reply #16 on:** October 31, 2005, 04:12:16 PM »

my options from that

1) weigh 4 coins ( 2 on each side) if they balence discard them,

weight teh other 4 coins same as before if they balence then teh one elft over is heavier.

otherwise you take the side which is heaviest and weight the two coins against each other

so it could take 2 weighins, it could take 3.

How do you get the apsolute minimum down to 2 (i can only get it down to 3)!

Hooman · « **Reply #17 on:** October 31, 2005, 10:41:20 PM »

Ok, a request for the answer. I think it's been long enough anyways.

1) Weight 3 coins on each side. If they balance, it wasn't any of them. (discard 6 possibilities) So we have the 3 coins left that haven't been weighed.

2) If the original weighing wasn't balanced, then again we are down to the 3 coins on the heaver side. (discarding the 3 on the lighter side, and the 3 that weren't weighed).

In either of the above two cases, we have 3 coins left to consider.

3) Weight two of the remaining 3 coins, if the balance it was the odd one out, and if it didn't, it's the coin on the heavier side.

So yeah, 2 weighings and you've got it with certainty.

The idea being that each weighing produces 1 of 3 outcomes. Heavier on side A, heavier on side B, or balanced. For each outcome, you reduce the possible space by a factor of 3 (if you've distributed the coins evenly among the cases). So with n weighings, you can determine the heaviest coin out of 3 ^ n coins. (provided the remaining 3^n - 1 coins have equal weight).

Btw, Eddy-B did mail me the answer and he got it right.

(I believe CK might have also spoken with Eddy and was also right, but I can't verify).

CK9 · « **Reply #18 on:** November 01, 2005, 01:18:37 PM »

Yes, I spoke with eddy, I'll forward the PM's to you if you'd like

HaXtOr · « **Reply #19 on:** November 01, 2005, 03:24:07 PM »

Quote

but yeah. It's a little overkill.

I thought my idea was overkill

Hooman · « **Reply #20 on:** November 01, 2005, 08:40:07 PM »

That's alright. It's not like there is a prize for getting the correct answer.

Maybe I should consider some sort of IB credit thing. But hey, at least you had the fun of trying to answer it.

HaXtOr · « **Reply #21 on:** November 01, 2005, 11:40:51 PM »

you never answered my question to weather the coins were the same size or made of the same material

Hooman · « **Reply #22 on:** November 01, 2005, 11:46:17 PM »

You never seemed to post a serious post in my thread. :angry:

Besides, that info is irrelevant to the question at hand as it was posed. It should have been clear that the info obtained was from the weighings, and nothing more.

dm-horus · « **Reply #23 on:** November 04, 2005, 05:36:48 AM »

Both of the following methods require less technology than Hooman suggests for the answer.

Well first you have to assume that the added weight of the heavier one is because it has more MASS since it was never specified (and assumed) that the heavier coin isnt larger than the others. A simple way to visually know which is the heavier one uses relatively little technology and is actually simpler than using a balance.

Heat them simultaneously. For example, put them on a pan and heat them in an oven. Get them red hot. Take them out and watch them cool. The one with more mass cools slower and will thus remain red longer.

Or...

Get a tall glass or bowl or a fishtank (or something similar that can hold water and is transparent) and drop all the coins in simultaneously. Due to hydrodynamic effects experienced by the flat surfaces of the coins, they will want to "cut" into the water at angles as they fall. This is relative to their mass. The lighter coins will not drop as quickly, making them cut, spin and wander thru the water. This slows them down yet more. The heavier coin has more mass and drops thru the water faster. The coin will not cut or flutter thru the water nearly as much as the lighter coins. The heavier one will hit bottom first.

While a difference in mass wont indicate which of 2 objects are heavier if they are dropped from the same height in air, hydrodynamic and surface effects will reveal which of the objects gravity has more of an effect on. Since gravity IS affected by mass (and vice versa) the one with more will be more highly influenced by gravity. The lighter ones will be (by comparison) more affected by the water and hydrodynamic effect. While the differences between the two are small, it is enough for ones eye to catch the difference.

Try it.

Eddy-B · « **Reply #24 on:** November 04, 2005, 08:24:39 AM »

Nice (and very scientific) response!
But the 'riddle' specificly stated you have only 9 coins, and 1 scale. It didn't mention anything about a fish tank or bowl or anything

News:

Author Topic: Age Old Problem (Read 5003 times)