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.
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.
Does the solution involve passing the coins through your gastro-intestinal system?
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.
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?
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.
Wow, cool! I think I solved that in 5 seconds. Though I will wail you to check.
Goddamn it. I can do it in four weighings, but not in 3.
You figure out whether it's heavier or lighter during the course of the second weighing.
I love this puzzle.
11: Hm. Not necessarily in my solution I don't think. Shoot. I left the notebook where I wrote it down at home.
11: I agree with the second sentence of 14.
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.
Are you allowed to make any kind of mark on the coins after each weighing?
(I should note that mine is the worst, in terms of simplicity, of any solution I've seen.)
Cause I'm worried about losing track of which coins I've weighed already and having to start over.
You ought to be able to keep track of them anyway. Put them in a stack, and remember which one went where.
Sure. You can do anything you want to keep track of the coins.
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.
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.
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.
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.
and w/d, I'm working on an email telling you my solution, but it's requiring some reconstruction.
But you can figure out the weight in 75% of the possible solutions.
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.
oh wait, it is easily tweakable. Thank god. I was about to jump out a window.
You know, I'm realizing w/d's solution may actually be my solution, just expressed differently.
wait, I think they're different. Maybe I should figure out what's going on before serial commenting any further on this thread.
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?
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.
34: I just, after much labor, reasoned my way to one of the 5/6 solutions. Crap.
Yeah, I've had a couple of those too.
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.
That would be elegant. My 5/6 solution involves a brutal decision tree.
My decision tree is very elegant!
For a decision tree.
I don't see how it could be more elegant.
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.
This one is so old hat.
Forgive my being supercilious, it's just I've got great hair.
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..
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.
Welcome to two hours ago, Ben.
Two hours ago I wa in bed, dreaming about your sandy locks, Drymala.
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?
No! No talking. Email people if you must.
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 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!
I'm tellin' you guys, it's possible and elegant.
Tia's right, it's mad elegant. I Googled it in frustration, so shoot me.
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.
You could still try to do it the decision tree way TCK.
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.
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.
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.
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.)
But don't everybody go reading all the puzzle solutions at that site; I'm going to use it for future puzzles.
Yeah, I found a pretty cool solution elsewhere.
Don't take your cue from these weak-willed people! I spent three days solving this puzzle and so should you.
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?
Yeah, you don't need to know that. You find that out. And there are several solutions, not just one.
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.
NickS, I also had the additonal supply of weighted coins solution, and that's moving you in the right direction.
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.
Did everyone either check the answer or give up? For shame.
I'm not working on it with any focus, but I'm still vaguely worrying the stupid thing as I work.
I believe (I haven't been working on it the whole time!) I have a decision-tree solution.
I've thought that -- I'm up to three distinguishable 5/6 solutions.
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.
The elegant solution doesn't work? Now I'm really confused.
I can see a three step solution, but it's the a fairly straightforward one, so maybe I'm missing something.
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.
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?
if scientists 1, 2, and 4 can open lock 1
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.
79 -- I thought Cala meant because maybe you wouldn't be allowed to label the pills prior to weighing them.
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.
Ah. Yeah well that works too.
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.
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. :)
Weiner is damn good at these, isn't he?
Aw shucks. This one was my old math competition skills coming to the fore.
Uh, fellas and ladies? It's no longer Tuesday morning. Move along.
I didn't realize this was going to be a timed test.
Din't say "Tuesday Morning Solution."
Prof Peter Fellgett taught us this as an example of mapping, in Information Theory, in 1967.