This is, if not my favorite riddle/puzzle what have you, very close. I actually remember very clearly when I first heard it (visiting D.C. for July 4th, while drinking) and when I solved it (sitting down with a pad the next night) after driving back.
Just noticed this is a different version of the riddle than the one I use. In mine you also need to know if the false coin is heavier or lighter than the rest.
But knowing first makes it easier -- if you don't know to begin with, it's tougher. (E.g., say you've narrowed it down to two. If you know the bad coin is the heavy one, you've got it. If you don't, you're nowhere.)
LB, I think w/d meant that you were required to figure out whether it was heavier or lighter, not that you got that info from the start. It's an easy puzzle if you know.
I mean that by the time you've figured out which coin it is, you also know whether it's heavier or lighter. I don't mean to imply anything about figuring that out whether it's heavier or lighter first.
Cala, I'd be curious to see that solution, because now I've seen three, mine, w/d's and the elegant solution, and I don't think that's true of any of them.
1) Combine steps three and four into one step (you have more information than you think.)
2) Don't divide the coins into two groups of six for the first weighing.
Tia, I don't see a way not. You won't know which coin is heavier or lighter, but you will know which it is, and what group it's in, by the end of the second step.
Cala, I can e-mail you the answer I just sent Tia, which doesn't do that. Here's my e-mail, in puzzle form: My pseudonym is an obvious pun on my last name, and my e-mail is lastname@abbreviation for New York Univeristy.edu.
damn, I just realized my solution doesn't actually meet w/d's condition. Does that mean I didn't really solve it? AAARRGH. Maybe I can tweak mine so it does.
can you determine in three weighings which is the counterfeit coin
Being a lawyer, I'm going to stretch the words. Is the test to find a way in which it is possible that you will solve the problem in three weighings (which I can do) or to ensure that in all possible circumstances you can solve the problem in three weighings?
If anyone who's already solved the puzzle wants to try for ithe elegant solution, I'll explain what sort of elegant it is by saying that it does not involve a decision tree.
My decision tree is ugly, and I'm having trouble concentrating well enough at work to reproduce it for you and w/d. I wish I had remembered my notebook.
I thought I remembered the solution, but the one I tried has 1 in 4 cases where it only works if you know in advance whether the coin is lighter or heavier. I'll try to fix that.
Logic puzzles like this make me feel like an idiot. I think of myself as a reasonably efficient and accurate reasoner, but I'm terrible at these things.
I remember this exercise from when I was a T.A. for a logic class, and I remember the two key things you need to figure out in order to find any solution, but I'm not really aware of solutions vastly differing in elegance. How can you possibly avoid a decision tree?
Actually, now that I see that you don't know whether the off coin is heavier or lighter, all the solutions I'm thinking of would require four weighings. Hmm..
In order not to be misleading, I guess I should say that by no decision tree, I mean that no weighing arrangement depends on the outcome of any previous one. I mean obviously different outcomes of the weighings would lead you to different conclusions about what was the bad coin, that goes without saying.
I googled it, and I don't think it's mad elegant, because you still have to go through twelve possibilities in your head in order to fill out the matrix.
I will admit that for the first hour or so of this thread I had misread the post and thought there were three coins and three weighings and was very perplexed as to why people couldn't figure it out. Seemed pretty damn obvious.
Well, I was wrong. That solution is absurdly elegant. I should remember that us mere dabblers in logic are in no way competent to compete with mathematicians.
The elegant solution was pretty cool, but the decision-tree one has the advantage of actually being workable when the twelve coins are eleven poison pills and one placebo and the evil king gives you a scale.
That took me far longer than I should have but I have a solution involving a decision tree (which I e-mailed to tia).
So now for my puzzle which comes with a story (and a guarantee that any of you who solve this puzzle will solve it faster than I did).
The puzzle is simple: there's a lab with 5 scientists working together on a cutting edge research project. For security reasons the lab wants to restrict access to the project only when a group is working on it together.
They put the project materials behind a door that has multiple locks on it (to open the door all the locks have to be unlocked) they give each of the scientists keys to some but not all of the locks such that any 4 of the 5 can open the door, but no 3 of the 5 can.
How many locks does the door have, and how many keys must there be to each lock.
I saw this problem on a test when I was on the high school math team. I couldn't solve it in the time limit, after the test I asked my teammates about it and none of them were able to solve it either. We poked at it a little bit, couldn't figure it out on the car ride home, and stopped working on it.
7 years later I wake up in the middle of the night knowing the solution to the problem. I don't know why that problem came back to me, or how I solved it in my sleep, but all of a sudden it was obvious. It was one of the great moments of my life.
My preliminary inspection of my, Cala's, NickS's, w/d's and Weiner's solution, if I perceive correctly, reveals that all five of our solutions are distinct in significant ways (not just swapping heavies for lights), though they all have some elements in common, and mine is more different from the other four than they are from each other. I may not be quick, but at least I march to my own drum.
Cala simply meant that she finds the übercool elegant powers method, which she finally googled, harder to implement practically given the tiny portion of Cala's brain dedicated to finding the distribution that wouldn't allow for mirroring or introduce other problems in the initial set-up.
As in, if Cala actually had to do this and had coins and a balance scale, she'd use a decision tree because she's sure she'd fuck up the elegant solution.
We now return you to your regularly scheduled programming.
84 -- this statement is correct and your solution is correct (and it took you only 1/100,000 as long to solve the problem as it took me if I'm calculating correctly. :)
This is, if not my favorite riddle/puzzle what have you, very close. I actually remember very clearly when I first heard it (visiting D.C. for July 4th, while drinking) and when I solved it (sitting down with a pad the next night) after driving back.
Posted by washerdreyer | Link to this comment | 04-18-06 8:47 AM
Just noticed this is a different version of the riddle than the one I use. In mine you also need to know if the false coin is heavier or lighter than the rest.
Posted by washerdreyer | Link to this comment | 04-18-06 8:51 AM
It's the same w/d. There's no way to solve this without figuring out in the process whether it's heavier or lighter, I don't think.
Posted by Tia | Link to this comment | 04-18-06 9:03 AM
Does the solution involve passing the coins through your gastro-intestinal system?
Posted by Jackmormon | Link to this comment | 04-18-06 9:08 AM
But knowing first makes it easier -- if you don't know to begin with, it's tougher. (E.g., say you've narrowed it down to two. If you know the bad coin is the heavy one, you've got it. If you don't, you're nowhere.)
Posted by LizardBreath | Link to this comment | 04-18-06 9:09 AM
LB, I think w/d meant that you were required to figure out whether it was heavier or lighter, not that you got that info from the start. It's an easy puzzle if you know.
Posted by Tia | Link to this comment | 04-18-06 9:11 AM
3: Tia, you mean figuring out whether the coin you are looking for is heavier or lighter, before you have identified a target coin/coins?
Posted by silvana | Link to this comment | 04-18-06 9:15 AM
I mean that by the time you've figured out which coin it is, you also know whether it's heavier or lighter. I don't mean to imply anything about figuring that out whether it's heavier or lighter first.
Posted by Tia | Link to this comment | 04-18-06 9:18 AM
Wow, cool! I think I solved that in 5 seconds. Though I will wail you to check.
Posted by The Modesto Kid | Link to this comment | 04-18-06 9:20 AM
Goddamn it. I can do it in four weighings, but not in 3.
Posted by Joe Drymala | Link to this comment | 04-18-06 9:20 AM
You figure out whether it's heavier or lighter during the course of the second weighing.
I love this puzzle.
Posted by Cala | Link to this comment | 04-18-06 9:21 AM
Oh shoot, no I'm wrong.
Posted by The Modesto Kid | Link to this comment | 04-18-06 9:21 AM
It's taking me 4 weighings.
Posted by The Modesto Kid | Link to this comment | 04-18-06 9:21 AM
11: Hm. Not necessarily in my solution I don't think. Shoot. I left the notebook where I wrote it down at home.
Posted by Tia | Link to this comment | 04-18-06 9:22 AM
11: I agree with the second sentence of 14.
Posted by washerdreyer | Link to this comment | 04-18-06 9:25 AM
Cala, I'd be curious to see that solution, because now I've seen three, mine, w/d's and the elegant solution, and I don't think that's true of any of them.
Posted by Tia | Link to this comment | 04-18-06 9:26 AM
Are you allowed to make any kind of mark on the coins after each weighing?
Posted by The Intrigued Kid | Link to this comment | 04-18-06 9:27 AM
(I should note that mine is the worst, in terms of simplicity, of any solution I've seen.)
Posted by Tia | Link to this comment | 04-18-06 9:28 AM
Cause I'm worried about losing track of which coins I've weighed already and having to start over.
Posted by The Intrigued Kid | Link to this comment | 04-18-06 9:28 AM
You ought to be able to keep track of them anyway. Put them in a stack, and remember which one went where.
Posted by Matt Weiner | Link to this comment | 04-18-06 9:29 AM
Sure. You can do anything you want to keep track of the coins.
Posted by Tia | Link to this comment | 04-18-06 9:29 AM
If it's taking you four, you need either to:
1) Combine steps three and four into one step (you have more information than you think.)
2) Don't divide the coins into two groups of six for the first weighing.
Tia, I don't see a way not. You won't know which coin is heavier or lighter, but you will know which it is, and what group it's in, by the end of the second step.
Posted by Cala | Link to this comment | 04-18-06 9:29 AM
You have to assume you can tell them apart (that is, that you can keep straight which you've weighed).
I've seen this puzzle a dozen times over the years. I never figure it out, and never remember the solution.
Posted by LizardBreath | Link to this comment | 04-18-06 9:29 AM
That's why I'm curious to hear your solution, Cala, cuz I know that's not true of the other three. Email me if you want.
Posted by Tia | Link to this comment | 04-18-06 9:35 AM
Cala, I can e-mail you the answer I just sent Tia, which doesn't do that. Here's my e-mail, in puzzle form: My pseudonym is an obvious pun on my last name, and my e-mail is lastname@abbreviation for New York Univeristy.edu.
Posted by washerdreyer | Link to this comment | 04-18-06 9:39 AM
Oops, I'm wrong.
Posted by Cala | Link to this comment | 04-18-06 9:39 AM
and w/d, I'm working on an email telling you my solution, but it's requiring some reconstruction.
Posted by Tia | Link to this comment | 04-18-06 9:41 AM
But you can figure out the weight in 75% of the possible solutions.
Posted by Cala | Link to this comment | 04-18-06 9:43 AM
damn, I just realized my solution doesn't actually meet w/d's condition. Does that mean I didn't really solve it? AAARRGH. Maybe I can tweak mine so it does.
Posted by Tia | Link to this comment | 04-18-06 9:44 AM
oh wait, it is easily tweakable. Thank god. I was about to jump out a window.
Posted by Tia | Link to this comment | 04-18-06 9:46 AM
You know, I'm realizing w/d's solution may actually be my solution, just expressed differently.
Posted by Tia | Link to this comment | 04-18-06 9:48 AM
wait, I think they're different. Maybe I should figure out what's going on before serial commenting any further on this thread.
Posted by Tia | Link to this comment | 04-18-06 9:50 AM
can you determine in three weighings which is the counterfeit coin
Being a lawyer, I'm going to stretch the words. Is the test to find a way in which it is possible that you will solve the problem in three weighings (which I can do) or to ensure that in all possible circumstances you can solve the problem in three weighings?
Posted by Idealist | Link to this comment | 04-18-06 9:54 AM
No, I came up with two possible ways to have a 5/6 chance of figuring out which coin it is, but those are not solutions.
Posted by Tia | Link to this comment | 04-18-06 9:56 AM
E-mailed you, Tia.
Posted by Cala | Link to this comment | 04-18-06 10:00 AM
34: I just, after much labor, reasoned my way to one of the 5/6 solutions. Crap.
Posted by LizardBreath | Link to this comment | 04-18-06 10:05 AM
Yeah, I've had a couple of those too.
Posted by Joe Drymala | Link to this comment | 04-18-06 10:07 AM
If anyone who's already solved the puzzle wants to try for ithe elegant solution, I'll explain what sort of elegant it is by saying that it does not involve a decision tree.
Posted by Tia | Link to this comment | 04-18-06 10:11 AM
That would be elegant. My 5/6 solution involves a brutal decision tree.
Posted by LizardBreath | Link to this comment | 04-18-06 10:16 AM
My decision tree is very elegant!
For a decision tree.
I don't see how it could be more elegant.
Posted by Cala | Link to this comment | 04-18-06 10:17 AM
My decision tree is ugly, and I'm having trouble concentrating well enough at work to reproduce it for you and w/d. I wish I had remembered my notebook.
Posted by Tia | Link to this comment | 04-18-06 10:19 AM
I thought I remembered the solution, but the one I tried has 1 in 4 cases where it only works if you know in advance whether the coin is lighter or heavier. I'll try to fix that.
Posted by NickS | Link to this comment | 04-18-06 10:34 AM
This one is so old hat.
Forgive my being supercilious, it's just I've got great hair.
Posted by ben wolfson | Link to this comment | 04-18-06 10:42 AM
Logic puzzles like this make me feel like an idiot. I think of myself as a reasonably efficient and accurate reasoner, but I'm terrible at these things.
Posted by LizardBreath | Link to this comment | 04-18-06 10:44 AM
I remember this exercise from when I was a T.A. for a logic class, and I remember the two key things you need to figure out in order to find any solution, but I'm not really aware of solutions vastly differing in elegance. How can you possibly avoid a decision tree?
Posted by Protagoras | Link to this comment | 04-18-06 10:55 AM
Actually, now that I see that you don't know whether the off coin is heavier or lighter, all the solutions I'm thinking of would require four weighings. Hmm..
Posted by ben wolfson | Link to this comment | 04-18-06 11:00 AM
I'm not going to tell you how to avoid a decision tree. Sheesh. But you can--I've seen the solution and it is darned impressive.
Posted by Tia | Link to this comment | 04-18-06 11:01 AM
Welcome to two hours ago, Ben.
Posted by Joe Drymala | Link to this comment | 04-18-06 11:03 AM
Welcome to two hours ago, Ben.
Two hours ago I wa in bed, dreaming about your sandy locks, Drymala.
Posted by ben wolfson | Link to this comment | 04-18-06 11:07 AM
Given my level of stuckness, would it be okay to talk about what I think is the necessary first weighing, and the elementary consequences of that?
Posted by LizardBreath | Link to this comment | 04-18-06 11:08 AM
No! No talking. Email people if you must.
Posted by Joe Drymala | Link to this comment | 04-18-06 11:09 AM
I guess so.
Posted by Tia | Link to this comment | 04-18-06 11:09 AM
Oh, okay, JD says no. Never mind.
Posted by Tia | Link to this comment | 04-18-06 11:10 AM
In order not to be misleading, I guess I should say that by no decision tree, I mean that no weighing arrangement depends on the outcome of any previous one. I mean obviously different outcomes of the weighings would lead you to different conclusions about what was the bad coin, that goes without saying.
Posted by Tia | Link to this comment | 04-18-06 11:13 AM
I can't see how that's possible. Well, I can, but it doesn't strike me as terribly elegant. It's like a brute-force computer way to get through it.
This is a fun puzzle!
Posted by Cala | Link to this comment | 04-18-06 11:18 AM
I'm tellin' you guys, it's possible and elegant.
Posted by Tia | Link to this comment | 04-18-06 11:20 AM
Tia's right, it's mad elegant. I Googled it in frustration, so shoot me.
Posted by The Cheating Kid | Link to this comment | 04-18-06 11:28 AM
I googled it, and I don't think it's mad elegant, because you still have to go through twelve possibilities in your head in order to fill out the matrix.
Posted by Cala | Link to this comment | 04-18-06 11:29 AM
You could still try to do it the decision tree way TCK.
Posted by Tia | Link to this comment | 04-18-06 11:29 AM
In other news, I just won 500K Euros! In a state lottery of the Netherlands that I was not even aware of having entered! Woo-hoo! Life is sweet.
Posted by The Fortunate Son Kid | Link to this comment | 04-18-06 11:30 AM
Cala, I think you did not Google the same one as Tia and I -- the one with powers of 3? Cause you didn't have to keep track of any matrices there.
Posted by The Numbering Kid | Link to this comment | 04-18-06 11:32 AM
I will admit that for the first hour or so of this thread I had misread the post and thought there were three coins and three weighings and was very perplexed as to why people couldn't figure it out. Seemed pretty damn obvious.
Posted by Becks | Link to this comment | 04-18-06 11:35 AM
No, not powers of three.
Posted by Cala | Link to this comment | 04-18-06 11:35 AM
Check the solution that's on cut-the-knot.org, at this page -- it will blow your mind. (The rest of the site's well worth your while as well.)
Posted by The Numbering Kid | Link to this comment | 04-18-06 11:42 AM
But don't everybody go reading all the puzzle solutions at that site; I'm going to use it for future puzzles.
Posted by Tia | Link to this comment | 04-18-06 11:44 AM
Yeah, I found a pretty cool solution elsewhere.
Posted by Joe Drymala | Link to this comment | 04-18-06 11:48 AM
Don't take your cue from these weak-willed people! I spent three days solving this puzzle and so should you.
Posted by Tia | Link to this comment | 04-18-06 11:51 AM
That solution is hella elegant.
Posted by ben wolfson | Link to this comment | 04-18-06 11:56 AM
So can the people that have seen the solution confirm that you do not need to know whether the false coin is lighter or heavier?
Posted by NickS | Link to this comment | 04-18-06 12:05 PM
Yeah, you don't need to know that. You find that out. And there are several solutions, not just one.
Posted by Tia | Link to this comment | 04-18-06 12:11 PM
The annoying thing is that I thought I knew the solution to this, but now I'm not quite able to remember it.
When I get this figured out I have another math / logic puzzle to inflict on everyone.
I just worked out a foolproof solution, assuming I have a supply of additional properly weighted coins that I can use.
I don't think that counts. I'm still working on this one.
Posted by NickS | Link to this comment | 04-18-06 1:47 PM
NickS, I also had the additonal supply of weighted coins solution, and that's moving you in the right direction.
Posted by Tia | Link to this comment | 04-18-06 1:48 PM
Well, I was wrong. That solution is absurdly elegant. I should remember that us mere dabblers in logic are in no way competent to compete with mathematicians.
Posted by Protagoras | Link to this comment | 04-18-06 2:28 PM
Did everyone either check the answer or give up? For shame.
Posted by washerdreyer | Link to this comment | 04-18-06 3:49 PM
I'm not working on it with any focus, but I'm still vaguely worrying the stupid thing as I work.
Posted by LizardBreath | Link to this comment | 04-18-06 4:07 PM
I believe (I haven't been working on it the whole time!) I have a decision-tree solution.
Posted by Matt Weiner | Link to this comment | 04-18-06 4:15 PM
I've thought that -- I'm up to three distinguishable 5/6 solutions.
Posted by LizardBreath | Link to this comment | 04-18-06 4:18 PM
The elegant solution was pretty cool, but the decision-tree one has the advantage of actually being workable when the twelve coins are eleven poison pills and one placebo and the evil king gives you a scale.
Posted by Cala | Link to this comment | 04-18-06 4:18 PM
The elegant solution doesn't work? Now I'm really confused.
Posted by LizardBreath | Link to this comment | 04-18-06 4:19 PM
In case that should come up.
Posted by Cala | Link to this comment | 04-18-06 4:19 PM
78 to 4?
Posted by Matt Weiner | Link to this comment | 04-18-06 4:32 PM
I can see a three step solution, but it's the a fairly straightforward one, so maybe I'm missing something.
Posted by SomeCallMeTim | Link to this comment | 04-18-06 4:45 PM
That took me far longer than I should have but I have a solution involving a decision tree (which I e-mailed to tia).
So now for my puzzle which comes with a story (and a guarantee that any of you who solve this puzzle will solve it faster than I did).
The puzzle is simple: there's a lab with 5 scientists working together on a cutting edge research project. For security reasons the lab wants to restrict access to the project only when a group is working on it together.
They put the project materials behind a door that has multiple locks on it (to open the door all the locks have to be unlocked) they give each of the scientists keys to some but not all of the locks such that any 4 of the 5 can open the door, but no 3 of the 5 can.
How many locks does the door have, and how many keys must there be to each lock.
I saw this problem on a test when I was on the high school math team. I couldn't solve it in the time limit, after the test I asked my teammates about it and none of them were able to solve it either. We poked at it a little bit, couldn't figure it out on the car ride home, and stopped working on it.
7 years later I wake up in the middle of the night knowing the solution to the problem. I don't know why that problem came back to me, or how I solved it in my sleep, but all of a sudden it was obvious. It was one of the great moments of my life.
So don't google the solution.
Posted by NickS | Link to this comment | 04-18-06 6:40 PM
How many locks does the door have, and how many keys must there be to each lock.
Just to be clear, all keys to any given lock are identical? That is, scientists 1, 2, and 4 can open lock 1, lock 1 has three keys?
Posted by Matt Weiner | Link to this comment | 04-18-06 7:00 PM
if scientists 1, 2, and 4 can open lock 1
Posted by Matt Weiner | Link to this comment | 04-18-06 7:02 PM
My preliminary inspection of my, Cala's, NickS's, w/d's and Weiner's solution, if I perceive correctly, reveals that all five of our solutions are distinct in significant ways (not just swapping heavies for lights), though they all have some elements in common, and mine is more different from the other four than they are from each other. I may not be quick, but at least I march to my own drum.
Posted by Tia | Link to this comment | 04-18-06 8:05 PM
79 -- I thought Cala meant because maybe you wouldn't be allowed to label the pills prior to weighing them.
Posted by The Mind-reading Kid | Link to this comment | 04-18-06 8:20 PM
Cala simply meant that she finds the übercool elegant powers method, which she finally googled, harder to implement practically given the tiny portion of Cala's brain dedicated to finding the distribution that wouldn't allow for mirroring or introduce other problems in the initial set-up.
As in, if Cala actually had to do this and had coins and a balance scale, she'd use a decision tree because she's sure she'd fuck up the elegant solution.
We now return you to your regularly scheduled programming.
Posted by Cala | Link to this comment | 04-18-06 8:39 PM
Ah. Yeah well that works too.
Posted by The Modesto Kid | Link to this comment | 04-18-06 8:49 PM
I thought that my and w/d's solution differed only by numbering, but I could be wrong.
Through *painstaking analysis* I just came up with another different solution, which didn't have the common element.
Posted by Matt Weiner | Link to this comment | 04-18-06 9:10 PM
84 -- this statement is correct and your solution is correct (and it took you only 1/100,000 as long to solve the problem as it took me if I'm calculating correctly. :)
Posted by NickS | Link to this comment | 04-18-06 9:59 PM
Weiner is damn good at these, isn't he?
Posted by teofilo | Link to this comment | 04-18-06 10:05 PM
Aw shucks. This one was my old math competition skills coming to the fore.
Posted by Matt Weiner | Link to this comment | 04-18-06 10:23 PM
Uh, fellas and ladies? It's no longer Tuesday morning. Move along.
Posted by ben wolfson | Link to this comment | 04-18-06 10:57 PM
I didn't realize this was going to be a timed test.
Posted by eb | Link to this comment | 04-18-06 11:09 PM
Din't say "Tuesday Morning Solution."
Posted by Matt Weiner | Link to this comment | 04-19-06 7:05 AM
Prof Peter Fellgett taught us this as an example of mapping, in Information Theory, in 1967.
Posted by dave heasman | Link to this comment | 04-20-06 11:08 AM