Re: Tuesday Morning Puzzle

1

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.

horizontal rule
2

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.

horizontal rule
3

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.

horizontal rule
4

Does the solution involve passing the coins through your gastro-intestinal system?

horizontal rule
5

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.)

horizontal rule
6

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.

horizontal rule
7

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?

horizontal rule
8

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.

horizontal rule
9

Wow, cool! I think I solved that in 5 seconds. Though I will wail you to check.

horizontal rule
10

Goddamn it. I can do it in four weighings, but not in 3.

horizontal rule
11

You figure out whether it's heavier or lighter during the course of the second weighing.

I love this puzzle.

horizontal rule
12

Oh shoot, no I'm wrong.

horizontal rule
13

It's taking me 4 weighings.

horizontal rule
14

11: Hm. Not necessarily in my solution I don't think. Shoot. I left the notebook where I wrote it down at home.

horizontal rule
15

11: I agree with the second sentence of 14.

horizontal rule
16

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.

horizontal rule
17

Are you allowed to make any kind of mark on the coins after each weighing?

horizontal rule
18

(I should note that mine is the worst, in terms of simplicity, of any solution I've seen.)

horizontal rule
19

Cause I'm worried about losing track of which coins I've weighed already and having to start over.

horizontal rule
20

You ought to be able to keep track of them anyway. Put them in a stack, and remember which one went where.

horizontal rule
21

Sure. You can do anything you want to keep track of the coins.

horizontal rule
22

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.

horizontal rule
23

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.

horizontal rule
24

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.

horizontal rule
25

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.

horizontal rule
26

Oops, I'm wrong.

horizontal rule
27

and w/d, I'm working on an email telling you my solution, but it's requiring some reconstruction.

horizontal rule
28

But you can figure out the weight in 75% of the possible solutions.

horizontal rule
29

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.

horizontal rule
30

oh wait, it is easily tweakable. Thank god. I was about to jump out a window.

horizontal rule
31

You know, I'm realizing w/d's solution may actually be my solution, just expressed differently.

horizontal rule
32

wait, I think they're different. Maybe I should figure out what's going on before serial commenting any further on this thread.

horizontal rule
33

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?

horizontal rule
34

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.

horizontal rule
35

E-mailed you, Tia.

horizontal rule
36

34: I just, after much labor, reasoned my way to one of the 5/6 solutions. Crap.

horizontal rule
37

Yeah, I've had a couple of those too.

horizontal rule
38

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.

horizontal rule
39

That would be elegant. My 5/6 solution involves a brutal decision tree.

horizontal rule
40

My decision tree is very elegant!

For a decision tree.

I don't see how it could be more elegant.

horizontal rule
41

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.

horizontal rule
42

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.

horizontal rule
43

This one is so old hat.

Forgive my being supercilious, it's just I've got great hair.

horizontal rule
44

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.

horizontal rule
45

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?

horizontal rule
46

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..

horizontal rule
47

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.

horizontal rule
48

Welcome to two hours ago, Ben.

horizontal rule
49

Welcome to two hours ago, Ben.

Two hours ago I wa in bed, dreaming about your sandy locks, Drymala.

horizontal rule
50

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?

horizontal rule
51

No! No talking. Email people if you must.

horizontal rule
52

I guess so.

horizontal rule
53

Oh, okay, JD says no. Never mind.

horizontal rule
54

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.

horizontal rule
55

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!

horizontal rule
56

I'm tellin' you guys, it's possible and elegant.

horizontal rule
57

Tia's right, it's mad elegant. I Googled it in frustration, so shoot me.

horizontal rule
58

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.

horizontal rule
59

You could still try to do it the decision tree way TCK.

horizontal rule
60

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.

horizontal rule
61

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.

horizontal rule
62

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.

horizontal rule
63

No, not powers of three.

horizontal rule
64

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.)

horizontal rule
65

But don't everybody go reading all the puzzle solutions at that site; I'm going to use it for future puzzles.

horizontal rule
66

Yeah, I found a pretty cool solution elsewhere.

horizontal rule
67

Don't take your cue from these weak-willed people! I spent three days solving this puzzle and so should you.

horizontal rule
68

That solution is hella elegant.

horizontal rule
69

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?

horizontal rule
70

Yeah, you don't need to know that. You find that out. And there are several solutions, not just one.

horizontal rule
71

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.

horizontal rule
72

NickS, I also had the additonal supply of weighted coins solution, and that's moving you in the right direction.

horizontal rule
73

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.

horizontal rule
74

Did everyone either check the answer or give up? For shame.

horizontal rule
75

I'm not working on it with any focus, but I'm still vaguely worrying the stupid thing as I work.

horizontal rule
76

I believe (I haven't been working on it the whole time!) I have a decision-tree solution.

horizontal rule
77

I've thought that -- I'm up to three distinguishable 5/6 solutions.

horizontal rule
78

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.

horizontal rule
79

The elegant solution doesn't work? Now I'm really confused.

horizontal rule
80

In case that should come up.

horizontal rule
81

78 to 4?

horizontal rule
82

I can see a three step solution, but it's the a fairly straightforward one, so maybe I'm missing something.

horizontal rule
83

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.

horizontal rule
84

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?

horizontal rule
85

if scientists 1, 2, and 4 can open lock 1

horizontal rule
86

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.

horizontal rule
87

79 -- I thought Cala meant because maybe you wouldn't be allowed to label the pills prior to weighing them.

horizontal rule
88

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.

horizontal rule
89

Ah. Yeah well that works too.

horizontal rule
90

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.

horizontal rule
91

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. :)

horizontal rule
92

Weiner is damn good at these, isn't he?

horizontal rule
93

Aw shucks. This one was my old math competition skills coming to the fore.

horizontal rule
94

Uh, fellas and ladies? It's no longer Tuesday morning. Move along.

horizontal rule
95

I didn't realize this was going to be a timed test.

horizontal rule
96

Din't say "Tuesday Morning Solution."

horizontal rule
97

Prof Peter Fellgett taught us this as an example of mapping, in Information Theory, in 1967.

horizontal rule