114 replies to this topic

[TerraPrime]

I mentioned the gold bar question at lunch as sort of comparison, and of course everyone at the table all got excited. Now I have to give them the answer. Except that I had forgotten it.

So, if I recall correctly, you have 100 bars of gold. One of them is lighter than the rest. You have one scale, and you can use it 3 times. Find out which gold bar is the light one.

Anyone got the solution memorized? Or know of a link? My GoogleFu is failing me on this one.

Edited by 好土同志, 12 April 2010 - 02:01 PM.

[Arataniello]

好土同志, on 12 April 2010 - 01:39 PM, said:

I mentioned the gold bar question at lunch as sort of comparison, and of course everyone at the table all got excited. Now I have to give them the answer. Except that I had forgotten it.

So, if I recall correctly, you have 100 bars of gold. One of them is lighter than the rest. You have one scale, and you can use it 3 times. Find out which gold bar is the light one.

Anyone got the solution memorized? Or know of a link? My GoogleFu is failing me on this one.

Hmm, never heard this one before, but I would assume that you put all the bars on there, and take them off one by one, carefully monitoring how much the scale dips each time (assuming this is an accurate digital scale). When you take off a bar that reduces the overall weight by a different amount, that is the lighter bar.

Check this by putting the suspected lighter bar to one side.

Take all the bars off the scale. Weigh a NON-suspect bar (2nd use of scale). Weight the suspect bar (3rd use of scales), to confirm your hypothesis.

[Iskaral Pust]

好土同志, on 12 April 2010 - 01:39 PM, said:

I mentioned the gold bar question at lunch as sort of comparison, and of course everyone at the table all got excited. Now I have to give them the answer. Except that I had forgotten it.

So, if I recall correctly, you have 100 bars of gold. One of them is lighter than the rest. You have one scale, and you can use it 3 times. Find out which gold bar is the light one.

Anyone got the solution memorized? Or know of a link? My GoogleFu is failing me on this one.

I have not heard of it before, but three weighings seems too few unless I'm missing a trick.

I would have guessed that the solution is to treat it as a trinary problem rather than binay, thereby reducing the number of weighings:
- binary would be to put half of the 100 bars on either side of the scales, identify the lighter half and use recursion on that half. This is the obvious approach.
- trinary would be to put a third of the 100 bars on either side of the scales and leave the last third off. Either the scales are uneven (identify which is lighter) or else perfectly even (the unweighed third contains the light bar).

In that trinary model
1st weighing: 33 vs 33 (34 aside), worst case outcome: the light bar is in the 34
2nd weighing: 11 vs 11 (11 or 12 aside), worst case outcome: the light bar is in the 12
3rd weighing: 4 vs 4 (3 or 4 aside), worst case outcome (and most likely): the light bar is in the 4
4th weighing: 1 vs 1 (2 aside) ~50% chance of finishing here, else
5th weighing: 1 vs 1 definitely finish here

#trials = n^(1/m). Setting m as 3 rather than 2 makes a geometric improvement in the #trials. For n=100, m=3 => #trials=4.64 (instead of 10 for m=2).

Is there another trick to further reduce the weighings?

[Iskaral Pust]

Aratan, on 12 April 2010 - 02:13 PM, said:

Hmm, never heard this one before, but I would assume that you put all the bars on there, and take them off one by one, carefully monitoring how much the scale dips each time (assuming this is an accurate digital scale). When you take off a bar that reduces the overall weight by a different amount, that is the lighter bar.

Check this by putting the suspected lighter bar to one side.

Take all the bars off the scale. Weigh a NON-suspect bar (2nd use of scale). Weight the suspect bar (3rd use of scales), to confirm your hypothesis.

I think that qualifies as many more than three usages of the scale. I also assumed that the scale is an old-fashioned fulcrum-based model (that measures relative weight not absolute weight). There would be a different solution for a scale that measures the actual weight.

[gronkie]

This site explains the problem pretty thoroughly. It seems you would need to use the scale five times to find the odd bar of gold if you had 100 bars.

[Iskaral Pust]

gronkie, on 12 April 2010 - 02:17 PM, said:

This site explains the problem pretty thoroughly. It seems you would need to use the scale five times to find the odd bar of gold if you had 100 bars.

That matches my approach (assuming the scales is a "two pan" model for relative weight, using their phrase).

[TerraPrime]

Well, my recollection is that it's the 100 bars, fulcrum type balance.

I did find a similar puzzle for 10 coins, 3 weighs, and got the answer for that.

But I'm fairly certain that someone else posted the 100-bar question here before, because I read the question and I thought "that seems impossible." Anyone else remember reading that thread?

[Arataniello]

Iskaral Pust, on 12 April 2010 - 02:17 PM, said:

I think that qualifies as many more than three usages of the scale. I also assumed that the scale is an old-fashioned fulcrum-based model (that measures relative weight not absolute weight). There would be a different solution for a scale that measures the actual weight.

I solved the problem given the parameters in the original post. Since the type of scale wasn't specified, I get to decide what form of scales were used. Since gold is valuable, I assume it is weighed more accurately.

And it looks from the website that was linked that the '3 weighings' simply is not enough for 100 objects.

[Iskaral Pust]

好土同志, on 12 April 2010 - 02:20 PM, said:

Well, my recollection is that it's the 100 bars, fulcrum type balance.

I did find a similar puzzle for 10 coins, 3 weighs, and got the answer for that.

But I'm fairly certain that someone else posted the 100-bar question here before, because I read the question and I thought "that seems impossible." Anyone else remember reading that thread?

100 in 3 weighings seems improbable. That implies a geometric reduction of order 5 (order 5 would give 2.5 weighings, order 4 would give 3.16 weighings, so to be certain you would need order 5).

It would be a good trick to take the reduction to order 5 rather than 3 (my suggestion). Perhaps there is one that I'm not seeing, presumably using some other substitution trick to take advantage of the simple information structure, but it doesn't jump out at me and I don't have time to pick at it.

[TerraPrime]

Ah, so it is 5, after all, and not 3.

Great job Isk.

Now I shall go receive my lashings from my coworkers (Ivory Tower people are very merciless) for giving them a wrong puzzle.

[Iskaral Pust]

好土同志, on 12 April 2010 - 02:29 PM, said:

Ah, so it is 5, after all, and not 3.

Great job Isk.

Now I shall go receive my lashings from my coworkers (Ivory Tower people are very merciless) for giving them a wrong puzzle.

You could follow up with a pink stretch that rolls up a hill. Their reaction can be used as a experiment to validate the maxim "Fool me once..."

[Shryke]

Aratan, on 12 April 2010 - 02:23 PM, said:

I solved the problem given the parameters in the original post. Since the type of scale wasn't specified, I get to decide what form of scales were used. Since gold is valuable, I assume it is weighed more accurately.

No, this is a rather famous type of logic puzzle.

You get a bunch of stuff to weight and a simple scale that will only tell you if they are the same weight, or if one weights more then another.

[Xray the Enforcer]

Here's the link to the old thread (although this is a different riddle to what TP describes in the OP):
http://asoiaf.wester...th-this-riddle/

I believe the answer is in post #22 (or thereabouts).

Edited by Xray the Enforcer, 12 April 2010 - 02:59 PM.

[Shryke]

Xray the Enforcer, on 12 April 2010 - 02:56 PM, said:

Here's the link to the old thread (although this is a different riddle to what TP describes in the OP):
http://asoiaf.wester...th-this-riddle/

I believe the answer is in post #22 (or thereabouts).

I don't think anyone actually answered that riddle. At least, from what I say quickly reading the thread.

There is a fairly easy answer to it though.

[Datepalm]

Can I threadjack for a riddle thats been bugging me? I know the answer (its not that difficult) but then theres a second part that i've never quite managed to parse, which appearantly dosen't have a straight up logical solution.

Anyway, the initial riddle:

On a remote island lives a society who absolutely believe that should any person find out the color of their own eyes, they must commit suicide that very night. Naturally, they have no mirrors, are very careful with puddles and such, and their maudlin love poetry references other body parts. All of them have either blue or brown eyes.

One day, an explorer arrives on the island, and becuase hes apparently something of an asshat, gathers the entire population together in the village square and announces: "At least one person here has blue eyes."

What happens now?

[Luisa Aoiftrazzini]

Datepalm, on 12 April 2010 - 03:15 PM, said:

Can I threadjack for a riddle thats been bugging me? I know the answer (its not that difficult) but then theres a second part that i've never quite managed to parse, which appearantly dosen't have a straight up logical solution.

Anyway, the initial riddle:

On a remote island lives a society who absolutely believe that should any person find out the color of their own eyes, they must commit suicide that very night. Naturally, they have no mirrors, are very careful with puddles and such, and their maudlin love poetry references other body parts. All of them have either blue or brown eyes.

One day, an explorer arrives on the island, and becuase hes apparently something of an asshat, gathers the entire population together in the village square and announces: "At least one person here has blue eyes."

What happens now?

What part are you looking for an explanation?

Spoiler

the fact that they will kill themselves, or the logic about when it will happen?

explanation:

Spoiler

these all assume that each person knows the eye colour of every other person, just not his or her own.
take the simple case that there's only one person on the island. As soon as the explorer gives that line, the islander must commit suicide that night.
In the case where there are two people on the island, they each see the other has blue eyes, based on the premise of the puzzle. If either had brown eyes, the other would know he has blue eyes, and would kill himself the first night. Since this doesn't happen, both villagers know that they both see blue eyes, so they both have blue eyes. They will therefore both kill themselves on the second night.
This continues this same way no matter how many islanders there are. So if there are 100 islanders, nobody will kill themselves until the 100th night, when they will all commit suicide the same evening.

Edited by Peggy Leef, 12 April 2010 - 03:53 PM.

[Iskaral Pust]

Datepalm, on 12 April 2010 - 03:15 PM, said:

Can I threadjack for a riddle thats been bugging me? I know the answer (its not that difficult) but then theres a second part that i've never quite managed to parse, which appearantly dosen't have a straight up logical solution.

Anyway, the initial riddle:

On a remote island lives a society who absolutely believe that should any person find out the color of their own eyes, they must commit suicide that very night. Naturally, they have no mirrors, are very careful with puddles and such, and their maudlin love poetry references other body parts. All of them have either blue or brown eyes.

One day, an explorer arrives on the island, and becuase hes apparently something of an asshat, gathers the entire population together in the village square and announces: "At least one person here has blue eyes."

What happens now?

Anyone who cannot see another person with blue eyes would immediately kill themselves, all others would not.
So long as there is more than one blue-eyed person in the group, nothing happens. If there is only one, he/she kills themself.

[Datepalm]

Iskaral Pust, on 12 April 2010 - 03:42 PM, said:

Anyone who cannot see another person with blue eyes would immediately kill themselves, all others would not.
So long as there is more than one blue-eyed person in the group, nothing happens. If there is only one, he/she kills themself.

nope.

Quote

Spoiler

that they will kill themselves, or the logic about when it will happen?

it just seemed bad riddling etiquette to put up a riddle immediately together with its solution. The perplexing bit is

Spoiler

why has the process waited for the arrival of the explorer, as he has told them nothing they don't already know.

The confusing explanation the riddler gave involved Kant, which is where he lost me.

[Happy Ent]

But he did tell them something! He doesn’t just tell them “There are blue-eyed people”, he actually (implicitly) tells them “There are blue-eyed people, this information is known to everybody from exactly this moment, Geheimnistag, the 52th of Conan 3453, in the evening.”

[Luisa Aoiftrazzini]

Datepalm, on 12 April 2010 - 03:49 PM, said:

nope.



it just seemed bad riddling etiquette to put up a riddle immediately together with its solution. The perplexing bit is

Spoiler

why has the process waited for the arrival of the explorer, as he has told them nothing they don't already know.

The confusing explanation the riddler gave involved Kant, which is where he lost me.

Spoiler

that's true, but the islanders -don't- know their own eye colours (I.e. They don't know they all have blue eyes), and have to use the logic I wrote out above to figure it out. They all figure out their own eye colour on the same day, and kill themselves that night.

Edited by Peggy Leef, 12 April 2010 - 04:00 PM.