Re: Guest Post: Tau By Two

1

I'm terrible at puzzles like the dwarf one, but it seems underspecified. First, can they coordinate beforehand, so we're looking for a combined strategy for all seven of them, or is each dwarf independent? And second, do you mean guarantee a right answer, or maximize the chance of a right answer? Because I really don't believe there's a solution that guarantees a right answer.


Posted by: LizardBreath | Link to this comment | 03-14-14 8:17 AM
horizontal rule
2

"You know how it's like 3.14....? It's like hella numbers?"

cow-orker


Posted by: Mister Smearcase | Link to this comment | 03-14-14 8:19 AM
horizontal rule
3

1: Sorry. Sure they can confer beforehand I was going to make that explicit but Midwestern reticence.

Also guarantee they can get it, Not a probabilistic thing.


Posted by: JP Stormcrow | Link to this comment | 03-14-14 8:21 AM
horizontal rule
4

In any seven hats, one is guaranteed to be black so they should all guess black.


Posted by: Moby Hick | Link to this comment | 03-14-14 8:22 AM
horizontal rule
5

The dwarves puzzle confuses me. If this is true, "All combinations possible; everyone can get the same color hat for instance. " then seeing the other hats doesn't give a dwarf any information about their own hat. So they need to have one of the other dwarves tell them.

If their were only seven hats, one of each color, than they easy solution is to agree that they will all guess "blue" (for example) and exactly one of them will be correct.


Posted by: NickS | Link to this comment | 03-14-14 8:22 AM
horizontal rule
6

Also: I am pretty sure I never heard of Pi day before I was 25, and now it seems to be a national holiday. Stuuuuuuuuuuuupid.


Posted by: heebie-geebie | Link to this comment | 03-14-14 8:22 AM
horizontal rule
7

6 is right, adjusting the age for me being older.


Posted by: Moby Hick | Link to this comment | 03-14-14 8:23 AM
horizontal rule
8

Also from OP: "How to guarantee that one dwarf correctly names the color of his hat?"


Posted by: JP Stormcrow | Link to this comment | 03-14-14 8:23 AM
horizontal rule
9

How to guarantee that one dwarf correctly names the color of his hat?

Dwalin: "Hey, Balin, what colour is my hat?"
Balin: "Blue."
Dwalin: "You sure?"
Balin. "Yup."
Dwalin: "OK, I'm ready to make a guess."


Posted by: ajay | Link to this comment | 03-14-14 8:24 AM
horizontal rule
10

If their were only seven hats, one of each color, than they easy solution is to agree that they will all guess "blue" (for example) and exactly one of them will be correct.

If they could hear each other's answers, then it's easy, too.


Posted by: heebie-geebie | Link to this comment | 03-14-14 8:24 AM
horizontal rule
11

Are there even seven colors...at all?


Posted by: heebie-geebie | Link to this comment | 03-14-14 8:24 AM
horizontal rule
12

Can they name their color "Fred" or "Harry"?


Posted by: heebie-geebie | Link to this comment | 03-14-14 8:25 AM
horizontal rule
13

5: I did struggle with how to write it up--it works better where you can verbally query the person. But all 7 hats could be red or whatever, but can still guarantee one gets it right. (In fact your observation could be construed as a clue.)


Posted by: JP Stormcrow | Link to this comment | 03-14-14 8:25 AM
horizontal rule
14

Does each dwarf get unlimited guesses? That might work.


Posted by: Thorn | Link to this comment | 03-14-14 8:25 AM
horizontal rule
15

11: There may not be! I guess it could have been worded "At most 7 colors."


Posted by: JP Stormcrow | Link to this comment | 03-14-14 8:26 AM
horizontal rule
16

One guess.


Posted by: JP Stormcrow | Link to this comment | 03-14-14 8:26 AM
horizontal rule
17

Are there even seven colors...at all?

Black, white, gray, off-white, brown, ROYGBIV. That's the exhaustive, complete list.


Posted by: Moby Hick | Link to this comment | 03-14-14 8:26 AM
horizontal rule
18

15: I was being way sillier than you're taking me to be.


Posted by: heebie-geebie | Link to this comment | 03-14-14 8:27 AM
horizontal rule
19

Of all colors, not all hat colors.


Posted by: Moby Hick | Link to this comment | 03-14-14 8:27 AM
horizontal rule
20

(In fact your observation could be construed as a clue.)

Wait, I assumed there was no communication allowed whatsoever, after the hats were distributed. That they were essentially each placed in isolation booths, but could see each other's hats.


Posted by: heebie-geebie | Link to this comment | 03-14-14 8:28 AM
horizontal rule
21

These sorts of inductive reasoning problems fall right into a hole in my brain. In theory, I like puzzles, but these precise ones I can't get any purchase on. If I didn't know that I'm really unreliable, I would be offering serious money to bet that there isn't a guaranteed solution.


Posted by: LizardBreath | Link to this comment | 03-14-14 8:29 AM
horizontal rule
22

(In fact your observation could be construed as a clue.)

Yeah, then I'm with 9.


Posted by: NickS | Link to this comment | 03-14-14 8:29 AM
horizontal rule
23

And I assume they're not allowed to guess things like "Samsies of whatever Dwarf One said."


Posted by: heebie-geebie | Link to this comment | 03-14-14 8:29 AM
horizontal rule
24

17: You forgot Dusty Rose.


Posted by: Mr. S | Link to this comment | 03-14-14 8:31 AM
horizontal rule
25

Oh, if they can react to each other's guesses, then I wouldn't bet it's unsolveable. I probably won't ever figure it out, but I'd believe in a solution.


Posted by: LizardBreath | Link to this comment | 03-14-14 8:31 AM
horizontal rule
26

Prearranged sequence of answers.
Dwarf 1: if he sees six red hats, he will answer that his hat is red too. Otherwise he will remain silent. (Mutatis mutandis; the point is that he only speaks if he sees six hats the same colour).
Dwarf 2: if Dwarf 1 has already spoken, Dwarf 2 will say "red" (or whatever) (and will thus be correct). Otherwise...


Posted by: ajay | Link to this comment | 03-14-14 8:32 AM
horizontal rule
27

If they're allowed to hear each other's guesses, then Dwarf 1 just says whatever color he sees the most of.


Posted by: heebie-geebie | Link to this comment | 03-14-14 8:32 AM
horizontal rule
28

What if they all agree that each one of them will guess a different color? Or does that count as knowing the others' answers?


Posted by: widget | Link to this comment | 03-14-14 8:32 AM
horizontal rule
29

So is the situation Balin guesses, then Dwalin, who heard Balin, guesses, then Bifur, who heard the prior two guesses...? That sounds solveable, but also not like the way the puzzle was stated.


Posted by: LizardBreath | Link to this comment | 03-14-14 8:33 AM
horizontal rule
30

No, then everyone else just repeats Dwarf 1's answer. Someone will be right.


Posted by: heebie-geebie | Link to this comment | 03-14-14 8:34 AM
horizontal rule
31

It can't be that they can hear each other's answers, though, because that's too silly.


Posted by: heebie-geebie | Link to this comment | 03-14-14 8:34 AM
horizontal rule
32

And the puzzle does say explicitly that they don't have access to each other's answers. At which point I'm back to insoluble.


Posted by: LizardBreath | Link to this comment | 03-14-14 8:35 AM
horizontal rule
33

I suppose I did receive a separate answer with the email, but I'd rather get clarification on the situation.


Posted by: heebie-geebie | Link to this comment | 03-14-14 8:35 AM
horizontal rule
34

From the OP

They do not have access to each other's answers.

Posted by: NickS | Link to this comment | 03-14-14 8:36 AM
horizontal rule
35

So I'm going forth with the Isolation Booth assumption.


Posted by: heebie-geebie | Link to this comment | 03-14-14 8:36 AM
horizontal rule
36

The "hearing each other's guesses" thing is a big part of other dwarves-in-hats puzzles. Also reasoning from each other's silences. So I was assuming that was allowed.
But if you prearrange strategies that include lying, it's just a case of "Balin guesses whatever colour Dwalin's hat is, and then Dwalin says the same thing".


Posted by: ajay | Link to this comment | 03-14-14 8:38 AM
horizontal rule
37

I'm confused about the rules. They are allowed to confer while they can see the others' hats, just not allowed to specifically tell any dwarf what color hat he is wearing? Or is the strategy fixed before they are hatted?

Also, why are they dwarves? Racist.


Posted by: L. | Link to this comment | 03-14-14 8:38 AM
horizontal rule
38

Ah - it must be one of these things where the order in which they answer gives clues to each other.

So if anyone sees six of the same color, he answers right away. Then everyone else knows what to do, based on their own view.

After a minute, anyone who sees five of the same color answers. Everyone else knows what to do.

After two minutes, etc.


Posted by: heebie-geebie | Link to this comment | 03-14-14 8:38 AM
horizontal rule
39

God, the tau thing is so stupid. And if you can figure out why it's stupid, you'll know the answer to the hat thing!


Posted by: Sifu Tweety | Link to this comment | 03-14-14 8:39 AM
horizontal rule
40

20,25: No sorry. No subsequent info--this observation of Nick's was the potential "clue': then seeing the other hats doesn't give a dwarf any information about their own hat.


Posted by: JP Stormcrow | Link to this comment | 03-14-14 8:40 AM
horizontal rule
41

So they can pre-discuss a strategy, but before hats are distributed they are confined to isolation booths and further strapped down by the sadistic puzzlemaster so they cannot see their own hats?


Posted by: snarkout | Link to this comment | 03-14-14 8:41 AM
horizontal rule
42

Sorry have to run to doc appt. let me repeat-can arrange ahead of time as much as they want. No subsequent communication. Do not hear other answers, or timing of them or whatever.


Posted by: JP Stormcrow | Link to this comment | 03-14-14 8:42 AM
horizontal rule
43

We need some tie scenarios - ie suppose there are two colors represented by three hats.

Then one person guesses after 3 minutes, and the second person needs to somehow indicate the tie, so that whoever sees a 3-2-1 pattern can deduce their own.


Posted by: heebie-geebie | Link to this comment | 03-14-14 8:42 AM
horizontal rule
44

41 is right.


Posted by: JP Stormcrow | Link to this comment | 03-14-14 8:42 AM
horizontal rule
45

I know a version of this puzzle that involves maximizing correct guesses and is bassed on Hamming codes, but it doesn't guarantee correctness.


Posted by: snarkout | Link to this comment | 03-14-14 8:42 AM
horizontal rule
46

but before hats are distributed they are confined to isolation booths and further strapped down by the sadistic puzzlemaster so they cannot see their own hats?

Maybe we can just put the hat on top of the isolation booth?


Posted by: heebie-geebie | Link to this comment | 03-14-14 8:42 AM
horizontal rule
47

Timing does not come into it at all.


Posted by: JP Stormcrow | Link to this comment | 03-14-14 8:42 AM
horizontal rule
48

Oh well, disregard 38 and 43, then.


Posted by: heebie-geebie | Link to this comment | 03-14-14 8:43 AM
horizontal rule
49

Also, why are they dwarves? Racist.

Because there are seven of them and they're wearing coloured hats.

38: but that might count as having access to each other's answers, though. Even if they can't hear the answers, they know that one of them has answered.


Posted by: ajay | Link to this comment | 03-14-14 8:44 AM
horizontal rule
50

Of course! The dwarves speak a language with a dramatically impoverished set of color words, so the only color word they have at their disposal accurately describes any of the possible hat colors to the limit of their linguistic capacity!


Posted by: Sifu Tweety | Link to this comment | 03-14-14 8:46 AM
horizontal rule
51

37: Strategy fixed before hatted.

49.1: I gave an opportunity in another thread to an alternative and got none

49.2: Total isolation. It is quite different than the other dwarf/hat puzzles so I can see that being confusing.


Posted by: JP Stormcrow | Link to this comment | 03-14-14 8:46 AM
horizontal rule
52

OT: Halford's VM fundraiser is currently more than $500 behind the fifth place fundraiser, with about 15 minutes to go, I believe. I was thinking about making a last minute donation to try to push us back up the rankings, but probably can't do over $500 right now. But if several others were thinking about kicking in a bit more, maybe still possible?


Posted by: Airedale | Link to this comment | 03-14-14 8:47 AM
horizontal rule
53

I do believe that the tau is less stupid than Sifu thinks it is. But not strongly.


Posted by: JP Stormcrow | Link to this comment | 03-14-14 8:47 AM
horizontal rule
54

Okay, start here -- I'm not going to get it done, but maybe someone else can finish this. Every dwarf guesses an unrepresented color. If there are no repeats, everyone guesses right. If the dwarf sees repeats, he selects among unrepresented colors according to some prearranged rule.


Posted by: LizardBreath | Link to this comment | 03-14-14 8:49 AM
horizontal rule
55

Anyone have the link to the fundraiser handy? I'll kick in some more.


Posted by: heebie-geebie | Link to this comment | 03-14-14 8:50 AM
horizontal rule
56

There is no time limit specified, neither an institutional budget.

They arrange ahead of time to have hot wings and beer delivered by personable non-exploited hotties every day forward unto eternity at two in the afternoon. Salads on Wednesday, nicely-executed chicken ceasars, Gimli who is partial to Cobb is killed for this reason so there are only six players. Maybe a taco van comes once in a while for variety, tacos al lengua must be an option, also those amazing pickled red onions. They never get around to guessing.


Posted by: lw | Link to this comment | 03-14-14 8:54 AM
horizontal rule
57

So they can pre-discuss a strategy, but before hats are distributed they are confined to isolation booths and further strapped down by the sadistic puzzlemaster so they cannot see their own hats?

But that doesn't match the OP which says that they, "get to see everyone else's hat."

I'm sort of curious about the answer, but I feel like the entire puzzle hinges on precisely what sort of communication is allowed. Given the confirmation that "seeing the other hats doesn't give a dwarf any information about their own hat." there has to be some information communicated between the dwarves.


Posted by: NickS | Link to this comment | 03-14-14 8:55 AM
horizontal rule
58

I don't think it is possible.
a) There is no prearranged number of hats: so knowing that everyone else's hat is red gives me no Shannon information about the colour of my own hat. My hat has a 1/7 chance of being red, regardless of the colour of all other hats.

b) It's total isolation: there is no way for me to receive Shannon information about my own hat from any other dwarf.

c) Therefore there's no strategy that gives a chance of success better than 1/7 for each individual dwarf, or 1-(6/7)^7 for the team.


Posted by: ajay | Link to this comment | 03-14-14 8:56 AM
horizontal rule
59

With total isolation and unlimited variation in hat colour, surely it's no different from having just one dwarf and forcing him to guess the colour of his own hat.


Posted by: ajay | Link to this comment | 03-14-14 8:57 AM
horizontal rule
60

Fundraiser Link.


Posted by: LizardBreath | Link to this comment | 03-14-14 8:57 AM
horizontal rule
61

Violating the sanctity, Stormcrow wrote in the email "Not quite heavyweight for enough to stand as a whole puzzler".


Posted by: heebie-geebie | Link to this comment | 03-14-14 8:57 AM
horizontal rule
62

Halford's VM fundraiser is currently more than $500 behind the fifth place fundraiser, with about 15 minutes to go

Yeah, I think it makes sense to concede (and compliment the superfans, as Halford called them, for donating so much). OTOH, I think Halford should at least make an attempt to lobby for passes to the afterparty based on the fact that he was the only person in the top 10 (when I checked) who actually had a broad base of small donors. Everyone else essentially had a couple of $500+ pledges.


Posted by: NickS | Link to this comment | 03-14-14 8:58 AM
horizontal rule
63

I am pretty sure a lot of the others were just financing it all themselves, or maybe with an immediate family member/friend or two.

But, yes, cheers to the superfans/stalkers for their big donations - we even ended up falling out of the top 10 (or I guess we're number 10 if you don't count KB).


Posted by: Airedale | Link to this comment | 03-14-14 9:02 AM
horizontal rule
64

58 seems right to me.


Posted by: nattarGcM ttaM | Link to this comment | 03-14-14 9:05 AM
horizontal rule
65

There's a centaur in the isolation chamber with 1 or more dwarves, and the dwarf asks the centaur what color his hat is.


Posted by: Natilo Paennim | Link to this comment | 03-14-14 9:06 AM
horizontal rule
66

Yeah, we're way out of the top 5 and probably need to concede (but I believe boosted the total amount donated by others by at least $5000, and were also the main group actually doing this for charity and not just for tix). I think I might still be able to use the secret power of connections to get Trapnel and Trapnelette into the after party but we will see!


Posted by: Robert Halford | Link to this comment | 03-14-14 9:07 AM
horizontal rule
67

"Why do I always have to wear the pink hat?"
-Reservoir Dwarves


Posted by: Barry Freed | Link to this comment | 03-14-14 9:08 AM
horizontal rule
68

The centaur eats one dwarf if 7 hats match. After a minute he eats another dwarf if the 6 remaining hats still match. And so on, for seven minutes. Done, and done with dwarves.


Posted by: heebie-geebie | Link to this comment | 03-14-14 9:09 AM
horizontal rule
69

The damn dwarves need to cheat or they all die. As posed I don't think there is a certain solution, just probability maximizing strategies.


Posted by: togolosh | Link to this comment | 03-14-14 9:09 AM
horizontal rule
70

Pertinent questions unanswered in the original problem:
1. Does each dwarf have on and only one head?
2. Is there any other entity present that the dwarves can query?
3. Do the dwarves all have full color vision?
4. Are the dwarves naturally visible themselves?
5. Can the dwarves manipulate any other object?
6. Does this puzzle take place in a universe with physical laws similar or identical to those in our own?


Posted by: Natilo Paennim | Link to this comment | 03-14-14 9:09 AM
horizontal rule
71

I'm thinking about peeking at the answer, which Stormcrow also emailed to me.


Posted by: heebie-geebie | Link to this comment | 03-14-14 9:10 AM
horizontal rule
72

Can the dwarves take selfies with their smartphones and upload them to Tumblr or Instagram or Facebook and solicit comments?


Posted by: Natilo Paennim | Link to this comment | 03-14-14 9:11 AM
horizontal rule
73

One of the dwarves is an OPP, but it's Meekins.


Posted by: heebie-geebie | Link to this comment | 03-14-14 9:13 AM
horizontal rule
74

The dwarfs previously agree among themselves a scale of worthiness, such that a red-hatted dwarf is worth seven black-hatted dwarfs, a blue-hatted dwarf is worth four and so on. Through a series of trolley problems, dwarfs will be able to deduce the colour of their own hats by observing the dwarfs whom their fellow dwarfs will kill them in order to rescue. e.g. if Dwalin observes that Thorin is ready to divert a runaway trolley car to kill Fili (blue hat, 4 points) and Bombur (white hat, 2 points) rather than let it continue on its course and kill him, Dwalin, then Dwalin will correctly deduce that his hat must be red (7 points).


Posted by: ajay | Link to this comment | 03-14-14 9:14 AM
horizontal rule
75

As posed I don't think there is a certain solution, just probability maximizing strategies.


As I say, as posed I don't think there is even a solution that will lift your answer above blind chance.


Posted by: ajay | Link to this comment | 03-14-14 9:15 AM
horizontal rule
76

Also the seven colors are all shades of blue, ranging from navy to sky to robin's egg, and the dwarves must correctly identify the shade of blue without a master list.


Posted by: heebie-geebie | Link to this comment | 03-14-14 9:17 AM
horizontal rule
77

Heebie, can you look at the answer and tell us if it exists and works? (And isn't some maddening purely verbal quibble?) I'm really not believing it's possible, for Ajay's reasons, but I also don't trust myself.


Posted by: LizardBreath | Link to this comment | 03-14-14 9:20 AM
horizontal rule
78

One dwarf is friends with Jiminy Cricket who is able to hide in a pocket while the dwarves are being isolated and then reveal the hat color.


Posted by: NickS | Link to this comment | 03-14-14 9:20 AM
horizontal rule
79

Hrm. No subsequent information is tricky and seems impossible, but I'm willing to trust there's something I'm overlooking.


Posted by: dalriata | Link to this comment | 03-14-14 9:22 AM
horizontal rule
80

76: so clearly these are female dwarfs.


Posted by: ajay | Link to this comment | 03-14-14 9:25 AM
horizontal rule
81

The number seven is presumably culturally derived and hence arbitrary (some of these puzzles need e.g. specifically five or whatever dwarves/prisoners/islanders/"people I've othered and also put hats on"). Can we make this work with two or three dwarves instead? I'm not seeing anything.


Posted by: dalriata | Link to this comment | 03-14-14 9:25 AM
horizontal rule
82

If each of the dwarves can see the other six dwarves and their hats, each should be able to perform some action to indicate how many different colors they can see. (For instance, if I see six different colors, I stand on my right foot. If I see five different colors, I stick out my tongue. Etc.) Given the information about how many colors each of his fellow dwarves can see, at least one dwarf should be able to correctly deduce the color of his own hat.

If they're not allowed to do this, then 58 holds, and there is no solution. It's as if I just put six random hats on the floor in front of you and then asked what color your own hat is.


Posted by: MAE | Link to this comment | 03-14-14 9:26 AM
horizontal rule
83

Yep, there is a true, non-maddening answer.


Posted by: heebie-geebie | Link to this comment | 03-14-14 9:26 AM
horizontal rule
84

Are the dwarfs academics? Do any of them have tenure?


Posted by: ajay | Link to this comment | 03-14-14 9:27 AM
horizontal rule
85

I haven't completely worked out the math for myself, but it's very believable.


Posted by: heebie-geebie | Link to this comment | 03-14-14 9:29 AM
horizontal rule
86

Is taupe even a real colour?


Posted by: OPINIONATED AUDITOR | Link to this comment | 03-14-14 9:29 AM
horizontal rule
87

Can we ask them in order? Is it something like we only ask dwarf N if dwarves 1,...,N-1 have failed?


Posted by: dalriata | Link to this comment | 03-14-14 9:29 AM
horizontal rule
88

Oh, yes, it does work. Stormcrow even included a "why it works" email, which I had failed to read.


Posted by: heebie-geebie | Link to this comment | 03-14-14 9:32 AM
horizontal rule
89

Now the only question is how insulted we should feel about 61.


Posted by: heebie-geebie | Link to this comment | 03-14-14 9:33 AM
horizontal rule
90

So can you give us a hint about what information is communicated between the dwarves?


Posted by: NickS | Link to this comment | 03-14-14 9:33 AM
horizontal rule
91

Thank god I can get some work done, now. Have fun, suckers.


Posted by: heebie-geebie | Link to this comment | 03-14-14 9:33 AM
horizontal rule
92

90: Absolutely none.


Posted by: heebie-geebie | Link to this comment | 03-14-14 9:33 AM
horizontal rule
93

Can dwarves see squant?


Posted by: Barry Freed | Link to this comment | 03-14-14 9:34 AM
horizontal rule
94

That's "Absolutely no information" not "Absolutely no hint".


Posted by: heebie-geebie | Link to this comment | 03-14-14 9:34 AM
horizontal rule
95

Can't be, that'd be information about the other answers.

It's got to be a cumbersome set of case by case rules, somehow: each dwarf has its own set of responses to what he sees, that somehow prevents overlap. Like, say they all get red hats. Dwarf 1 knows "If I see six reds, I guess red", Dwarf 2 knows "If I see six reds, I guess orange," Dwarf 3 knows "If I see six reds, I guess yellow"... That works great for 'all the same color', but I don't know how to make it work for situations where the different dwarfs see different things without manually trying to work out a solution for literally all of the 7 to the 7th cases.


Posted by: LizardBreath | Link to this comment | 03-14-14 9:35 AM
horizontal rule
96

I don't know what exactly I meant by "prevents overlap" in that last comment.


Posted by: LizardBreath | Link to this comment | 03-14-14 9:38 AM
horizontal rule
97

I think the answer is an iteration of this solution for two dwarves: Dwarf 1 says dwarf 2's hat's color. If they're the same color, good. If they're the same, success. If they're not the same, dwarf 2 succeeds by saying the opposite of dwarf 1's color.


Posted by: dalriata | Link to this comment | 03-14-14 9:40 AM
horizontal rule
98

Can every dwarf make up to 7 guesses?


Posted by: Minivet | Link to this comment | 03-14-14 9:40 AM
horizontal rule
99

Don't know whether it breaks the rules, but could each dwarf group the other six into groups of matching color? (By showing them into corners of the room or something?) Then each could see who he fits with. It requires some kind of communication, but not telling what color the guesser's hat is. You need each dwarf to be the organizer once, though, for the case where everyone draws a different color. Doesn't work if they're in isolation booths, though.


Posted by: ydnew | Link to this comment | 03-14-14 9:40 AM
horizontal rule
100

Redundant sentence was redundant.


Posted by: dalriata | Link to this comment | 03-14-14 9:41 AM
horizontal rule
101

97, 98: nope, nope. Zero signalling of any kind.


Posted by: heebie-geebie | Link to this comment | 03-14-14 9:41 AM
horizontal rule
102

I meant 97 and 99.


Posted by: heebie-geebie | Link to this comment | 03-14-14 9:41 AM
horizontal rule
103

97: so what would that be for 3 dwarfs?


Posted by: ajay | Link to this comment | 03-14-14 9:44 AM
horizontal rule
104

I give up. I'm stuck at, "It's as if I just put six random hats on the floor in front of you and then asked what color your own hat is."


Posted by: NickS | Link to this comment | 03-14-14 9:44 AM
horizontal rule
105

97, 99. Those both rely on communication, so I think they're verboten.


Posted by: LizardBreath | Link to this comment | 03-14-14 9:44 AM
horizontal rule
106

That's not signaling. They're allowed to see each other's hats beforehand (but with no communication), right? Or am I misunderstanding that? And I thought we hit a success state if any dwarf is correct. 97 would apply even in isolation--dwarf 2 should act as if dwarf 1 failed.

I'm having trouble getting that to work with 3 dwarves due to the possibility of a shared color, though.


Posted by: dalriata | Link to this comment | 03-14-14 9:44 AM
horizontal rule
107

But it's communication about success or failure.


Posted by: LizardBreath | Link to this comment | 03-14-14 9:45 AM
horizontal rule
108

101: 97 doesn't involve signalling between dwarfs. Dwarf 1 says whatever colour D2 is. D2 says whatever colour D1 isn't - not whatever colour D1 didn't say.

So if it's (black, black) D1 says "Black" and is correct.
If it's (black, red) D1 says "red" and is wrong, and D2 says "red" and is correct.

But I can't see how to set up a three-dwarf solution.


Posted by: ajay | Link to this comment | 03-14-14 9:46 AM
horizontal rule
109

No, it's not. Each subsequent dwarf should assume the previous dwarves failed: if one succeeded, then we already win so who cares what they say?


Posted by: dalriata | Link to this comment | 03-14-14 9:46 AM
horizontal rule
110

108.1: Thanks for that clarification.


Posted by: dalriata | Link to this comment | 03-14-14 9:47 AM
horizontal rule
111

Does the game stop when somedwarf guesses correctly, or are they only told the result when they've all had a go?


Posted by: chris y | Link to this comment | 03-14-14 9:53 AM
horizontal rule
112

Oh, I get the 97 -- they key element isn't communication, it's being able to predict what the other people will do based on having a system worked out in advance.

Now the trick is just to generalize to 7 dwarves . . .


Posted by: NickS | Link to this comment | 03-14-14 9:56 AM
horizontal rule
113

111: The game stopping gives them information. But that doesn't matter: dwarf 4 should just assume that dwarves 1, 2, and 3 all lost. If one of 1,2, or 3 didn't lose, dwarf 4's answers doesn't matter. That way we can behave as if the game stops even if they're not told the result until they've all had a go.


Posted by: dalriata | Link to this comment | 03-14-14 9:56 AM
horizontal rule
114

If the seven possible colors of hats are known in advance, isn't it pretty easy? Each dwarf just guesses the color that hasn't been guessed yet, ensuring that at least the last dwarf gets it right.


Posted by: Robert Halford | Link to this comment | 03-14-14 9:57 AM
horizontal rule
115

114: Yeah. Unfortunately, duplicates are allowed.


Posted by: dalriata | Link to this comment | 03-14-14 9:58 AM
horizontal rule
116

No, because they can repeat. All the hats could be the same color.


Posted by: LizardBreath | Link to this comment | 03-14-14 9:59 AM
horizontal rule
117

Wait, so, if the 7 colors are known in advance, why don't they each assign themselves a color before hand and guess that?


Posted by: Natilo Paennim | Link to this comment | 03-14-14 9:59 AM
horizontal rule
118

I maybe have a solution -- a tell is that there are seven dwarves, not six or eight or nine. Let me work out the math.


Posted by: snarkout | Link to this comment | 03-14-14 9:59 AM
horizontal rule
119

Oh right, I didn't read 97 closely enough.

The correct solution, when limited to 2 dwarves, does in fact yield the answer in 97.


Posted by: heebie-geebie | Link to this comment | 03-14-14 9:59 AM
horizontal rule
120

Oh, right, 'cause they have to guess their own color. But Halford's doesn't work either, does it?


Posted by: Natilo Paennim | Link to this comment | 03-14-14 9:59 AM
horizontal rule
121

It has to be prime? I have no idea at all how that could play into it.


Posted by: LizardBreath | Link to this comment | 03-14-14 9:59 AM
horizontal rule
122

Oh whoops that was pretty dumb even for me.


Posted by: Robert Halford | Link to this comment | 03-14-14 9:59 AM
horizontal rule
123

I'm sure the answer hinges on multi-headedness among dwarves though.


Posted by: Natilo Paennim | Link to this comment | 03-14-14 10:00 AM
horizontal rule
124

So let's try three dwarves with R,G,B, hat colors. There are 27 possibilities:

1) R,R,R
2) G,R,R
3) B,R,R
4) R,R,G
5) G,R,G
6) B,R,G
7) R,R,B
8) G,R,B
9) B,R,B

10) R,G,R
11) G,G,R
12) B,G,R
13) R,G,G
14) G,G,G
15) B,G,G
16) R,G,B
17) G,G,B
18) B,G,B

19) R,B,R
20) G,B,R
21) B,B,R
22) R,B,G
23) G,B,G
24) B,B,G
25) R,B,B
26) G,B,B
27) B,B,B

. . .


Posted by: NickS | Link to this comment | 03-14-14 10:00 AM
horizontal rule
125

118: Oh, so you think that they're dwarves was chosen because there are 7, not 7 because they're dwarves? Clever.


Posted by: dalriata | Link to this comment | 03-14-14 10:01 AM
horizontal rule
126

And they know which seven colours are involved? So that if, in the pre-game parade they see the others wearing violet, indigo, bue, green, yellow and orange, they know that theirs is either violet, indigo, blue, green, yellow, orange or red, but not white?


Posted by: chris y | Link to this comment | 03-14-14 10:01 AM
horizontal rule
127

117: Let's call the prisoners A-G and the colors 1-7. If it's set up so A guesses 1, B guesses 2, etc., you lose if the hat distribution is (2,3,4,5,6,1).


Posted by: snarkout | Link to this comment | 03-14-14 10:01 AM
horizontal rule
128

FIND OUT WHY PUZZLEMASTERS HATE LOCAL MOM'S ONE WEIRD TRICK!


Posted by: Natilo Paennim | Link to this comment | 03-14-14 10:03 AM
horizontal rule
129

IF Dwarf 1 sees two matching colors, he will guess that color (that solves for 1, 14, 27). If dwarf 1 sees non-matching colors he will guess the third color (that solves for 6, 8, 12, 16,20, 22).

If Dwarf 2 sees two matching colors he will guess what? Not a matching color, so we'll say one up from the matching color (2Rs yield B, 2Bs yields G, . . . .) That solves . . . .

Okay, I'll try to work this out, but I can imagine a solution of that type working.


Posted by: NickS | Link to this comment | 03-14-14 10:05 AM
horizontal rule
130

It's easier using that toy example. Let Red = 1, Green = 2, Blue = 3. There are three dwarves, Aifur, Bofur, and Calfur. Here's the strategy:

Aifur is assigned the number "1". Bofur is assigned the number "2". Calfur is assigned the number "3" (or "0" -- we're using modulo arithmatic, so they're equivalent). When the hats are given, each dwarf looks at the other hats and makes a guess so that the sum of observed hats + guess is equal to her assigned number (modulo 3). Give me another few minutes and I'll work out the results for the 27 distributions of hats in the three-color case.


Posted by: snarkout | Link to this comment | 03-14-14 10:06 AM
horizontal rule
131

The goal, obviously is to come up with a set of rules that guarantee coverage of all the possibilities.


Posted by: NickS | Link to this comment | 03-14-14 10:06 AM
horizontal rule
132

Give me another few minutes and I'll work out the results for the 27 distributions of hats in the three-color case.

Oh good, I'll wait, because that will be easier than my approach.


Posted by: NickS | Link to this comment | 03-14-14 10:07 AM
horizontal rule
133

Snarkie is smartie.


Posted by: heebie-geebie | Link to this comment | 03-14-14 10:09 AM
horizontal rule
134

No, I confess that I just racked my brain for hat problems I've encountered before. The Hamming function one is good too!


Posted by: snarkout | Link to this comment | 03-14-14 10:11 AM
horizontal rule
135

||
Remember when people had all those weird tricks to get out of paying long distance rates? Like blurting out a short message as one's "name" in making a collect call? I was thinking the other day that anyone born after, say, 1990 or so, just wouldn't have much of a meaningful hook for that. Maybe even earlier.
||>


Posted by: Natilo Paennim | Link to this comment | 03-14-14 10:11 AM
horizontal rule
136

Ok, to continue the stupidity. They plan the ROYGBIV colors along a spectrum of opposites: R-V, O-I, Y-B, G. If no dwarf is seen to be wearing Green, Dwarf 1 will look at Dwarf 7 and guess the same color as on Dwarf 7. Dwarf 2 will look at Dwarf 7 and guess the opposite color. Dwarf 3 will look at Dwarf 6 and guess Dwarf 6's color. Dwarf 4 looks at Dwarf 6 and guesses the opposite. Dwarf 6 then looks at Dwarf 5 and guesses Dwarf 5's color. Dwarf 7 looks at Dwarf 5 and guesses the opposite. Dwarf 5 then guesses Green.

If one of the dwarves is wearing green, the pairing just shifts somehow to keep the guessing pairs in a way one of you can figure out.


Posted by: Robert Halford | Link to this comment | 03-14-14 10:14 AM
horizontal rule
137

Here's the first nine:

1) 1,1,1 A=2, B=3, C=1, C is correct
2) 2,1,1 A=2, B=2, C=3, A is correct
3) 3,1,1 A=2, B=1, C=2, B is correct
4) 1,1,2 A=1, B=3, C=1, A is correct
5) 2,1,2 A=1, B=1, C=3, B is correct
6) 3,1,2 A=1, B=3, C=2, C is correct
7) 1,1,3 A=3, B=1, C=1, B is correct
8) 2,1,3 A=3, B=3, C=3, C is correct
9) 3,1,3 A=3, B=2, C=2, A is correct

I haven't worked this out for the remaining 18, but that's how it works. (Open query: does this work for a non-prime number of hats? Note that this is in fact a generalization of the two-hat solution given in 97.)


Posted by: snarkout | Link to this comment | 03-14-14 10:16 AM
horizontal rule
138

Is there an easy way to explain why 130 works?


Posted by: LizardBreath | Link to this comment | 03-14-14 10:16 AM
horizontal rule
139

I was trying to do it by trial and error along the lines suggested by NickS but I am thankful to snarkout for letting me get back to what I should be doing.


Posted by: widget | Link to this comment | 03-14-14 10:17 AM
horizontal rule
140

I think it does work for a non-prime number.


Posted by: heebie-geebie | Link to this comment | 03-14-14 10:18 AM
horizontal rule
141

Why are 117 and 28 wrong?


Posted by: politicalfootball | Link to this comment | 03-14-14 10:18 AM
horizontal rule
142

Without writing it out, I'm just observing that we're never trying to divide in this process, and that tends to be where having a composite number might screw you up.


Posted by: heebie-geebie | Link to this comment | 03-14-14 10:19 AM
horizontal rule
143

138 - The algorithm given reduces the problem to a set of guesses, "what is the sum of the hat-numbers, modulo seven", where each dwarf guesses a different number. By the pigeonhole principle, if there are seven choices and you make seven different guesses, you correctly guess with one.


Posted by: snarkout | Link to this comment | 03-14-14 10:21 AM
horizontal rule
144

141: For the reason given in 120 -- at least one dwarf has to guess his own hat. They could be seven different colors, but each dwarf's preassigned color could be different from his hat color.


Posted by: widget | Link to this comment | 03-14-14 10:21 AM
horizontal rule
145

Snarkie is indeed a smartie (back form doc appt.)


Posted by: JP Stormcrow | Link to this comment | 03-14-14 10:26 AM
horizontal rule
146

The Hamming code one goes this way: the king has ten prisoners he is planning to execute. But because the kingdom has a chronic shortage of mathematicians, he announces that if they can solve a logic problem they will be freed. Each is put into an isolation booth -- no communication, even on the order of "did so and so guess" -- which is either red or green; every prisoner can see the color of all the booths but her own. If even one prisoner guesses the color of her own booth, they are to be freed unless any prisoner guesses incorrectly in which case a retraction letter will be published in Science and they will all be shot. What's the optimal strategy? (Note that it doesn't guarantee that they escape.)


Posted by: snarkout | Link to this comment | 03-14-14 10:28 AM
horizontal rule
147

I'll see if I can spell out snarkout's argument a bit.
Let's call the colors 0 through n-1 and the dwarf hat colors h_1,...,h_n. So, modulo n, dwarf k guesses

k-\sum_{i!=k} h_i mod n

Now suppose that for dwarves 1 through n-1, that value is not equal to h_k. So

(forall k (forall k

That summation doesn't depend upon k, so the right hand side is going to give you n-1 distinct values that h_n is not equal to. It's then trivial for the last dwarf to guess the remaining color. Is that right?


Posted by: dalriata | Link to this comment | 03-14-14 10:29 AM
horizontal rule
148

145 - Again, I'm pretty sure I've encountered this before rather than figuring it out from first principles. But it's a good problem!


Posted by: snarkout | Link to this comment | 03-14-14 10:29 AM
horizontal rule
149

Oh, dammit, stupid unfogged formatting.


Posted by: dalriata | Link to this comment | 03-14-14 10:29 AM
horizontal rule
150

I am impressed.


Posted by: ajay | Link to this comment | 03-14-14 10:30 AM
horizontal rule
151
Let's try that again.

Let's call the colors 0 through n-1 and the dwarf hat colors h_1,...,h_n. So, modulo n, dwarf k guesses
k-\sum_{i!=k} h_i mod n
Now suppose that for dwarves 1 through n-1, that value is not equal to h_k. So

(forall k) h_k != k-\sum_{i!=k} h_i (mod n)
(forall k) h_n != k-\sum_{i!=n} h_i (mod n)
That summation is constant for all k, so the right hand side is going to give you n-1 distinct values that h_n is not equal to. It's then trivial for the last dwarf to guess the remaining color. Is that right?


Posted by: dalriata | Link to this comment | 03-14-14 10:31 AM
horizontal rule
152

Those two quantifiers should be for all k < n. It wasn't unfogged formatting, I just once again forgot to escape my character entities.


Posted by: dalriata | Link to this comment | 03-14-14 10:32 AM
horizontal rule
153

As an amendment to 146, the color of the booths is chosen randomly, by coin flip. Working the problem out for three prisoners is a good place to start.


Posted by: snarkout | Link to this comment | 03-14-14 10:33 AM
horizontal rule
154

138 - The algorithm given reduces the problem to a set of guesses, "what is the sum of the hat-numbers, modulo seven", where each dwarf guesses a different number. By the pigeonhole principle, if there are seven choices and you make seven different guesses, you correctly guess with one.

That's a great summary and makes perfect sense once I understood that basic line of argument. I'm not sure that it would have made sense if you'd posted it before 97 (and, for me, 112).


Posted by: NickS | Link to this comment | 03-14-14 10:33 AM
horizontal rule
155

I think you're right, Heebie - no multiplication means that this works even for four hats.


Posted by: snarkout | Link to this comment | 03-14-14 10:34 AM
horizontal rule
156

what's this talk of preassigned- and booth-color? where is that in the original question?

the only thing in this puzzle with color are the hats.


Posted by: cleek | Link to this comment | 03-14-14 10:37 AM
horizontal rule
157

156: The dwarves work it out in conference the night before, since we're specifically told that they can discuss strategy in advance. I'm using prisoners/booths instead of dwarves/hats so people can discuss my problem without stepping on the OP.


Posted by: snarkout | Link to this comment | 03-14-14 10:38 AM
horizontal rule
158

Works for any number of hats

Ungeneralized form of answer based on 7 (basically a restatement of snarkout's):
Colors get numbers 0 to 6.
Dwarves get a number 0 to 6.
Let's say total value of the hats is N.
n = N modulo 7.
Each dwarf will see some value between N-6 and N.
Dwarf guesses the number for his hat that would make the total modulo 7 equal his number.
Dwarf whose number is n will get his hat right.
Every other dwarf will be wrong.


Posted by: JP Stormcrow | Link to this comment | 03-14-14 10:42 AM
horizontal rule
159

That was a lot of fun. We should do more of these.


Posted by: dalriata | Link to this comment | 03-14-14 10:44 AM
horizontal rule
160

61: Violating the sanctity, Stormcrow wrote in the email "Not quite heavyweight for enough to stand as a whole puzzler".

I probably did not appreciate the extent to which other dwarf/hat problems have a whole different kind of solution. And it does seem insoluble until suddenly it isn't. Also not great write up by me. And it does work best interactively.


Posted by: JP Stormcrow | Link to this comment | 03-14-14 10:46 AM
horizontal rule
161

we're specifically told that they can discuss strategy in advance

where were we told that?


Posted by: cleek | Link to this comment | 03-14-14 10:49 AM
horizontal rule
162

In comment 3, cleek.


Posted by: snarkout | Link to this comment | 03-14-14 10:50 AM
horizontal rule
163

ah.

thanks.


Posted by: cleek | Link to this comment | 03-14-14 10:54 AM
horizontal rule
164

77: (And isn't some maddening purely verbal quibble?)

I am now going to now retroactively asser that my recent big thinko on the breastfeeding post, wrong poet assignation, and any other recent deficiencies were just part of a long con to set up this puzzler so that people would not believe there was a legitimate answer.


Posted by: JP Stormcrow | Link to this comment | 03-14-14 11:01 AM
horizontal rule
165

Let's explain this for us who don't know what modulo means here. I am committed to standing up for the stupid people by demonstrating stupidity.


Posted by: Robert Halford | Link to this comment | 03-14-14 11:07 AM
horizontal rule
166

Yay! Halfordismo & Stupidismo forever!


Posted by: Natilo Paennim | Link to this comment | 03-14-14 11:09 AM
horizontal rule
167

Let's explain this for us who don't know what modulo means here. I am committed to standing up for the stupid people by demonstrating stupidity.

Modulo means "the remainder when divided by". So 12 modulo 5 is 2. It's an important base concept in a lot of abstract algebra and number theory.


Posted by: snarkout | Link to this comment | 03-14-14 11:11 AM
horizontal rule
168

Like a clock, where you only have the numbers 1-12 and after 12 it loops back to 1? "Modulo" is that looping back. When we talk about numbers modulo 7, we only have 0-6 and then loop back to 0. So, for example, "8 modulo 7" is the same as 1.


Posted by: L. | Link to this comment | 03-14-14 11:11 AM
horizontal rule
169

Pwnd but my explanation was stupider, therefore better.


Posted by: L. | Link to this comment | 03-14-14 11:12 AM
horizontal rule
170

I'm no good at this kind of puzzle, but I made a spreadsheet generating random "colors" (numbers) to test it and eventually got it to work, which was fun.

Now someone explain intuitively why it works!


Posted by: Minivet | Link to this comment | 03-14-14 11:23 AM
horizontal rule
171

Oh shoot, I missed the puzzler thread. The key is to come up with a strategy that guarantees everyone will be wrong, and then do something else.


Posted by: Eggplant | Link to this comment | 03-14-14 11:24 AM
horizontal rule
172

Let me try and explain it for Halford at a lawyer-appropriate level -- I just barely get it myself. Math people should check me if I've got it wrong.

1) If you give each color a number from 1 to 7, when you put the hats on the dwarves, you can add up the values of all the hat colors modulo 7, and get a number from 1 to 7 (or 0 to 6, whatever).

2) Even if you knew that number, that wouldn't be enough to tell you what color all the hats were, obviously, because there are only 7 possible numbers, and there are 7 to the 7th power possible hat combinations.

3) But, if you're a dwarf looking at six hats, and trying to guess the seventh color, and you already know the number they sum to, that tells you the seventh color: there's only one guess you can make that gives you the right numerical sum.

4) So, each dwarf, beforehand, is assigned a number. One of them is always going to have the right number (that is, the number that the hat colors sum to), accidentally, because there are seven dwarfs and seven possible numbers, and the other six will have wrong numbers.

5) Each dwarf looks at the six hats he can see, adds up their numerical values, and guesses his own hat color so that the seven hat colors add up to his assigned number. Because of 3 -- if you know the correct sum and six hat colors, that's enough to deduce the seventh -- and 4 -- one of the dwarves has the correct sum, because there's a dwarf for each possible correct sum -- the dwarf with the correct sum gets the right answer (and the other six are guaranteed wrong).

Does that make sense? (And, math people, is it right?)


Posted by: LizardBreath | Link to this comment | 03-14-14 11:26 AM
horizontal rule
173

No one wants to tackle 146? The poor mathematicians are going to be in those isolation booths until they starve to death.


Posted by: snarkout | Link to this comment | 03-14-14 11:26 AM
horizontal rule
174

On 146, I will be boldly wrong (did I mention I'm terrible at these) and say they can't do better than 50-50. They prearrange for 9 to stay silent and one to guess randomly.


Posted by: LizardBreath | Link to this comment | 03-14-14 11:29 AM
horizontal rule
175

Also, I made 10,000 rows each with their own randomly-generated dwarf torture conditions, and while I verified that one and only one dwarf will always be correct, intriguingly, each time I generate a new set of 10,000, it's the same-numbered dwarf being correct in all 10,000. Probably something to do with Excel's random number generator.


Posted by: Minivet | Link to this comment | 03-14-14 11:32 AM
horizontal rule
176

Interesting that random guessing and this strategy produce the same expected live dwarves. If I had to go through this with my loved ones this strategy would be the absolute last thing we'd do because it perfectly anticorrelates me living and anyone else I care about living. OTOH, if you and six other people are the only ones in the world who know some secret password, this strategy is great.

You could probably use Shannon theory to prove that all strategies have the same living dwarf EV.


Posted by: dz | Link to this comment | 03-14-14 11:33 AM
horizontal rule
177

Or maybe that dwarf is just a really good guesser.


Posted by: LizardBreath | Link to this comment | 03-14-14 11:34 AM
horizontal rule
178

I don't think it was specified anywhere that the torturers must tell the dwarfs the 7 possible colors beforehand -- otherwise they won't have a standard color-to-number conversion system.


Posted by: Minivet | Link to this comment | 03-14-14 11:34 AM
horizontal rule
179

176: I think if any dwarf guesses correctly, they all live. If only the dwarfs that guess correctly live, then this isn't any better than chance -- it guarantees one success and six failures.


Posted by: LizardBreath | Link to this comment | 03-14-14 11:35 AM
horizontal rule
180

178: If they don't have access to the possible colors beforehand, this solution can't be done, I don't think.


Posted by: LizardBreath | Link to this comment | 03-14-14 11:36 AM
horizontal rule
181

172 is right.

179 is also right - I was imagining different rules where only the dwarves who guess correctly are spared.


Posted by: dz | Link to this comment | 03-14-14 11:36 AM
horizontal rule
182

177: Right now, it's dwarf 2 being right each of 10,000 times; then as I recalculate, the always-right one becomes 0, 4, 5, 1, 1, 3, 1, 4, 5, etc. I can only assume that the spreadsheet is rolling up new character sheets each time, with one heebie-dwarf.


Posted by: Minivet | Link to this comment | 03-14-14 11:38 AM
horizontal rule
183

I understand this works in theory, but so does neoclassical macroeconomics. Has anyone actually tested this empirically on live dwarves?


Posted by: urple | Link to this comment | 03-14-14 11:45 AM
horizontal rule
184

172 makes sense to me, but it took me running through the scenarios a few times to figure out why. Reach out and touch the stupid!


Posted by: Robert Halford | Link to this comment | 03-14-14 11:47 AM
horizontal rule
185

Reach out and touch the stupid!

I thought you weren't doing the online dating thing anymore?


Posted by: Josh | Link to this comment | 03-14-14 11:50 AM
horizontal rule
186

184: If it makes you feel better, my initial reaction to 143 was "There are a whole lot more than seven choices, bucko -- that doesn't work at all." And I didn't even try to puzzle through dalriata's notation.

Sally's just getting to math that isn't instant for me -- for some reason I have a mental block with logarithms, so that the same problem that's obvious and intuitive with exponents takes a couple of minutes of staring and I have to write down log to the base 10 of 100 =2 in the margin to remember how it works.


Posted by: LizardBreath | Link to this comment | 03-14-14 11:53 AM
horizontal rule
187

I don't understand how this can be thought to guarantee a right answer, as opposed to just maximizing the chance of getting a right answer? What if they mess up the calculations??


Posted by: urple | Link to this comment | 03-14-14 11:55 AM
horizontal rule
188

Or what if the torturer cheats? Anyone who would set up a situation this cruel patently cannot be relied on.


Posted by: LizardBreath | Link to this comment | 03-14-14 11:57 AM
horizontal rule
189

187: It does assume perfection in that regard, yes.


Posted by: JP Stormcrow | Link to this comment | 03-14-14 11:57 AM
horizontal rule
190

146: So much for getting work done. If a prisoner guesses wrong, are they all shot right away? Or does the fact they haven't been shot at time t instead convey the information that, as of time t, no one has guessed wrong?


Posted by: widget | Link to this comment | 03-14-14 11:58 AM
horizontal rule
191

190: They are all immediately shot as soon as any of them guess incorrectly. As I said, this version of the problem doesn't guarantee that they escape.


Posted by: snarkout | Link to this comment | 03-14-14 12:00 PM
horizontal rule
192

190, continued: But the king is playing fair. He really wants mathematicians for his ninja army!


Posted by: snarkout | Link to this comment | 03-14-14 12:00 PM
horizontal rule
193

178: I don't think it was specified anywhere that the torturers must tell the dwarfs the 7 possible colors beforehand -- otherwise they won't have a standard color-to-number conversion system.

In the setup, I should have included that the (infallible) dwarves were aware of the rules and setup. Absolutely necessary for it to work.


Posted by: JP Stormcrow | Link to this comment | 03-14-14 12:01 PM
horizontal rule
194

189: so we were supposed to assume that the dwarves are infalliable calculators. You should have specified that.


Posted by: urple | Link to this comment | 03-14-14 12:02 PM
horizontal rule
195

Have I mentioned how much Urple reminds me of the Tortoise lately?


Posted by: LizardBreath | Link to this comment | 03-14-14 12:04 PM
horizontal rule
196

Also, it would have been helpful to know that the dwarves are familiar with modulo operations.


Posted by: urple | Link to this comment | 03-14-14 12:05 PM
horizontal rule
197

If even one prisoner guesses the color of her own booth, they are to be freed unless any prisoner guesses incorrectly in which case a retraction letter will be published in Science and they will all be shot.

I'll give 146 a try. Could you explain the stress on "even one"? It sounds to me like there are two cases: 1) everyone is correct (and so they're all freed), or someone made a mistake (and they are embarrassed in a high impact publication and executed).


Posted by: dalriata | Link to this comment | 03-14-14 12:07 PM
horizontal rule
198

196: Dwarves are familiar with all sorts of math, but particularly differential equations; they're useful in avoiding a feline chain reaction.


Posted by: dalriata | Link to this comment | 03-14-14 12:08 PM
horizontal rule
199

I'll give 146 a try. Could you explain the stress on "even one"? It sounds to me like there are two cases: 1) everyone is correct (and so they're all freed), or someone made a mistake (and they are embarrassed in a high impact publication and executed).

Oh, sure - an important caveat is that not every prisoner needs to make a guess. If prisoner A is unsure of her color or the scheme adopted by the group means she is not supposed to guess, she may abstain. To avoid communication based on the length of time without guesses, assume that each prisoner is asked to write down her guess on a piece of paper that will be collected at a fixed time, with no guess being taken as an abstention. At least one must guess correctly with no incorrect guesses in order for them to be freed.


Posted by: snarkout | Link to this comment | 03-14-14 12:10 PM
horizontal rule
200

Ah, thanks! Allows abstentions seems eminently reasonable for someone who'd construct such an elaborate execution apparatus.


Posted by: dalriata | Link to this comment | 03-14-14 12:13 PM
horizontal rule
201

If none of them guess and they are like, "Ha ha, none of us guessed incorrectly so now you must neither release nor execute us!", the king will have them all torn apart by tigers for being smartasses, but will not write a retraction letter, so their academic reputations will remain intact.


Posted by: snarkout | Link to this comment | 03-14-14 12:13 PM
horizontal rule
202

I know how the Hamming code works, so I bet I could get 146. But instead I'm going to spend the next hour scanning and uploading documents to a website.


Posted by: heebie-geebie | Link to this comment | 03-14-14 12:27 PM
horizontal rule
203

This problem is easier to work out starting with three prisoners. I will tell you right now that our mathematicians can come up with a better answer than LB's perfectly sensible base case (prisoner A choses "red", prisoners B and C shut up; they have a 50-50 chance of being freed).


Posted by: snarkout | Link to this comment | 03-14-14 12:29 PM
horizontal rule
204

You know what's not too helpful here? The Wikipedia page for "hamming code."


Posted by: Robert Halford | Link to this comment | 03-14-14 12:47 PM
horizontal rule
205

I think I have an algorithm that works 3/4 of the time for the three person case:

If you see two red, pick green
If you see two green, pick red
If you see one of each, abstain

My reasoning is that it's slightly less likely to have the number of 1 bits to be congruent to 0 mod 3 than 1 or 2 mod 3. Testing it out and assuming that I didn't confuse myself (very likely), this fails for the all red and all green cases but in the other six cases one person gets it right and the other two abstain.


Posted by: dalriata | Link to this comment | 03-14-14 12:55 PM
horizontal rule
206

205 is the optimal strategy for 3 people.


Posted by: snarkout | Link to this comment | 03-14-14 12:57 PM
horizontal rule
207

s/to be/be/.

Also, I'm assuming that the king picks the number randomly and not maliciously.


Posted by: dalriata | Link to this comment | 03-14-14 12:57 PM
horizontal rule
208

207: See 192. The king is playing fair and assigning the colors randomly.


Posted by: snarkout | Link to this comment | 03-14-14 1:00 PM
horizontal rule
209

Oh, missed that. The king must be a Final Fantasy Tactics fan.


Posted by: dalriata | Link to this comment | 03-14-14 1:01 PM
horizontal rule
210

Nice. I think I am not qualified for this one.


Posted by: widget | Link to this comment | 03-14-14 1:05 PM
horizontal rule
211

My way of thinking about this probably can't be extended to arbitrary bits (or if it can, it's a negligible advantage). I haven't thought about error-correcting codes in years and I'm having trouble comprehending the horrible Wikipedia page to the point where I can turn it into probabilities.


Posted by: dalriata | Link to this comment | 03-14-14 1:11 PM
horizontal rule
212

I haven't read most of the responses yet, but it is clear that there is a solution for 2 dwarfs and 2 colors: dwarf 0 guesses whatever he sees dwarf 1 wearing, and dwarf 1 guesses the opposite of what he sees dwarf 0 wearing. E.g., if the colors are blue and orange, then dwarf 1, seeing dwarf 0 wearing orange, reasons "If my own hat is also orange, dwarf 0 will be correct. Therefore, I will guess blue, since that is the scenario where dwarf 0 will be wrong." This covers all 4 possible cases.

My guess is that this can be extended to n dwarfs and n colors, although it gets tricky. In general, dwarf i must be able to reason that if his own hat is color j, then for all but one of the possible values of j, some other dwarf will be correct (which means there must be no scenario in which two or more dwarfs will be correct), and then use the strategy to guess the remaining color. This implies that every dwarf must use a hashing function that incorporates all of the other n-1 hat values, and every dwarf's hashing function must be unique. That is not sufficient, however - my first try that dwarf i guesses the sum of the other hats plus i (mod n) fails for n=3.


Posted by: Dave W. | Link to this comment | 03-14-14 1:44 PM
horizontal rule
213

212 is impressively on-point.


Posted by: NickS | Link to this comment | 03-14-14 1:49 PM
horizontal rule
214

Ok, I was close - the solution others are pushing is essentially that dwarf i guesses i minus the partial sum mod n (which is equivalent to guessing that the total sum is equal to i mod n).


Posted by: Dave W. | Link to this comment | 03-14-14 1:58 PM
horizontal rule
215
        1
     1  2  1
   1  3  3  1
  1  4  6  4  1
1  5  10 10  5  1

(This analysis of the problem in 146 is primarily from one of my sons.)

Generalizes the scheme in 205 for odd numbers of prisoners, but 1) don't yet see how it works for even numbers and 2) not matching it to a Hamming function.

3 prisoners
If you look at Pascal's triangle shown above, the 3 prisoner case is the 1 3 3 1 row and what you are doing is getting one person to get it right in the mixed scenarios (middle two 3s) the other two abstain. In the edge scenarios (all one color) all 3 guess wrong. So overall 6/8=75% chance of success, but your overall guessing percentage (as it must be) is still just 50% since across all of the all the combinations you have 6 combos x 1 correct guess = 6 and 2 combos x 3 incorrect guess = 6 as well. So what you need to do is "pile up" the wrong guesses in the combinations you are going to lose anyway while being sparse about getting them right.

4 prisoners
Scheme does not generalize, you can reproduce 50% by a scheme which picks up the edges and the middle, but no better than just one random person guessing.

5 prisoners
You can get the 2 10s (3/2) and the edges correct for 22/10 for 68.75% success.
a) If see 4 of same color pick it
b) If see 3 of one color and 1 of another pick the color with 1.
c) If see 2 of each abstain.
For the edges all 5 will guess correctly because of a) for total of 5 x 2 =10 correct guesses.
For 4/1 distributions all 5 will be wrong. 4 of them because of b) and one because of a) for total of 10 x 5 =50 incorrect guesses.
For 3/2 distributions 2 will guess correctly due to b) and 3 will abstain due to c) for a total of 20 x 2=40 correct guesses.
All told 50 correct and incorrect guesses.

7 prisoners
Won't type it all out, but with the scheme you get
2 edges (7/0) wrong - all abstain , so 0 incorrect guesses but still die.
The 14 (6/1) scenarios right, 6 correct, 1 abstain for 6 x 14 =84 correct guesses.
The 42 (5/2) scenarios wrong, all 7 wrong, so 7 x 42 =294 incorrect guesses.
The 70 (4/3) scenarios right, 3 correct, 4 abstain for 3 x 70 =210 correct guesses.
So 294 and 294 50% right on guesses, but 84/44 so 65.625% death avoidance.


Posted by: JP Stormcrow | Link to this comment | 03-14-14 4:55 PM
horizontal rule
216

So, with that scheme, odd # prisoner scenarios only can get above 50% with the success rate slowly declining from 75% (and probably approaching something in the limit, not sure if it would be 50% or a higher 5).

Maybe I'll now go look at the Hamming stuff to see if that can get better, or at least work for the even number scenarios.


Posted by: JP Stormcrow | Link to this comment | 03-14-14 5:04 PM
horizontal rule
217

I was told there would be slightly less math.


Posted by: Moby Hick | Link to this comment | 03-14-14 5:11 PM
horizontal rule
218

Now a few comments on various points in the thread. (Missed a lot because of stupid hematology appointment made stupider by apparent finding that I do have a genetic factor for clotting, which along with Lupus anticoagulant levels would indicate warfarin for life. Also, children and sibs should get tested for the mutation. I still don't 100% believe it since no family history, but then I didn't believe I actually had a clot in the first place...)


Posted by: JP Stormcrow | Link to this comment | 03-14-14 5:11 PM
horizontal rule
219

On the plus side, if a rat tries to gnaw you, it'll die.


Posted by: Moby Hick | Link to this comment | 03-14-14 5:18 PM
horizontal rule
220

This thread manages to make poring over the appendices to traffic reports seem inviting.


Posted by: dairy queen | Link to this comment | 03-14-14 5:23 PM
horizontal rule
221

I've found several cheating answers on the internet but I am too dumb even to figure it out using the cheats!


Posted by: Robert Halford | Link to this comment | 03-14-14 5:24 PM
horizontal rule
222

The solutions all seem to involve some pretty advanced math. Keep in mind that I recently tested out on Khan Academy at about a 7th grade math level.


Posted by: Robert Halford | Link to this comment | 03-14-14 5:29 PM
horizontal rule
223

Khaaaan!


Posted by: Moby Hick | Link to this comment | 03-14-14 5:44 PM
horizontal rule
224

Yeah OK, reading up on Hamming codes which imply you have an ordering* there should be a way to "pile up" the wrong guesses into sacrificial scenarios like parity bits. (Or somehow or other use the order to distinguish more scenarios which you can divide up to your benefit.) Details, however, are devils.

*Solution in 215 works if you just know the total number of reds and greens you see but cannot put them in an order; I'm going to go out on a limb and thinking it might be the best you can do in that scenario--which is not, however, a very "satisfying" problem since if a prisoner can actually see them they can order them, the other would happen if they were just told the number of reds and greens.


Posted by: JP Stormcrow | Link to this comment | 03-14-14 5:50 PM
horizontal rule
225

OT: I worked my sexy magic to get Trapnel and SheTrapnel into the reception even though we didn't "win" the right to do so.

All in all, we raised over $3,000 just in direct donations from us, plus I still have a bunch of matching donations to make. Plus I'd guess that we leveraged at least another $5000 from the superfans that they wouldn't have paid otherwise because we raised the money early. Plus we're sending our crew to the reception anyway despite the superfans' effort to block us. So all and all an incredible job done by the collective Unfogged community at helping out a bunch of needy people. Really amazing.


Posted by: Robert Halford | Link to this comment | 03-14-14 6:04 PM
horizontal rule
226

That really is fabulous, Halford. Unfortunately difficult to imagine how I can turn this to advantage in strategizing the capital campaign for the nonprofit I'm on the board of. Awkward conversation with consultant covering imaginary internet playground, nude selfies, etc ...


Posted by: dairy queen | Link to this comment | 03-14-14 6:12 PM
horizontal rule
227

Great work! OK, when we start the boutique you and CC can handle the business development.


Posted by: widget | Link to this comment | 03-14-14 6:20 PM
horizontal rule
228

28: What if they all agree that each one of them will guess a different color? Or does that count as knowing the others' answers?

58: My hat has a 1/7 chance of being red, regardless of the color of all other hats.

When I first heard it I went down these types of paths, but since they tend to reduce what I'll call the "remaining" pool of combinations by 1/7th so you come up short (I think each guessing a different or everyone guessing one of the colors gets you to abut 68% chance.) The modulo solution reduces the "original" pool by 1/7th each time so you end up covering the entire space.


Posted by: JP Stormcrow | Link to this comment | 03-14-14 6:31 PM
horizontal rule
229

225.1: Strong work. Apparently no math required.


Posted by: JP Stormcrow | Link to this comment | 03-14-14 6:31 PM
horizontal rule
230

The problem with the accepted solution is that everyone knows dwarves are bad at math. No way they'd be able to pull that off.


Posted by: Spike | Link to this comment | 03-14-14 6:34 PM
horizontal rule
231

225: Nicely done.

I like that this thread uses Tolkien's plural for dwarves.


Posted by: ydnew | Link to this comment | 03-14-14 6:38 PM
horizontal rule
232

The "Stormcrow" should be a hint there.


Posted by: Moby Hick | Link to this comment | 03-14-14 6:41 PM
horizontal rule
233

97: I think the answer is an iteration of this solution for two dwarves: Dwarf 1 says dwarf 2's hat's color. If they're the same color, good. If they're the same, success. If they're not the same, dwarf 2 succeeds by saying the opposite of dwarf 1's color.

Actually the first form I heard this one in was the n=2 situation you describe, but put in a way that similarly seemed impossible at first glance.

Two prisoners at far ends of a prison, each make guesses about coin flips each day to see if they both will be executed. Rules are this: If either correctly predicts the result of the other prisoner's coin flip they live another day. If they are ever both wrong they die. How long can they go on that way? Answer: Forever. Note: it doesn't work if each is predicting their own coin flip without seeing the result--but if it is the other prisoner's it can work*. (In my experience that last bit triggers almost everyone's "No way!: flag.)

Answer is basically the equivalent of what you describe for the two dwarf problem. Both flip their own coins. One prisoner's guess for the other prioner is what his flip is, the other's guess the opposite of what his flip is.

*There is a purposeful dodge in the way I compare those two situations.


Posted by: JP Stormcrow | Link to this comment | 03-14-14 6:46 PM
horizontal rule
234

I haven't read the thread yet. I know I've heard this puzzle before, because a friend of mine who left physics for finance collected a giant set of dwarf-in-hat-related puzzles a year or two ago to pester or amuse everyone with. But I've forgotten the solution. Mostly I remember that one of his puzzles started with the phrase "A countably infinite set of dwarves..."


Posted by: essear | Link to this comment | 03-14-14 6:46 PM
horizontal rule
235

231.2: Purposefully, in a lame attempt to reduce insensitivity and increase nerdliness.


Posted by: JP Stormcrow | Link to this comment | 03-14-14 6:48 PM
horizontal rule
236

The guy I thought was maybe exhibiting a bit of psychosis is here tonight. He very deliberately did not sit by me.


Posted by: Moby Hick | Link to this comment | 03-14-14 6:49 PM
horizontal rule
237

And apologies again for the rather poor write-up. I was putting it together at my leisure, but when I saw that it was pi day I rushed it to heebie (rather than wait for June 28th) in case people wanted to discuss pi/tau. But apparently not even one little bit.


Posted by: JP Stormcrow | Link to this comment | 03-14-14 6:50 PM
horizontal rule
238

232/235: But I think everyone went along. Apparently nerdery beats pedantry? Who'd have thought?


Posted by: ydnew | Link to this comment | 03-14-14 6:52 PM
horizontal rule
239

I don't see how you could have uncountably many dwarves.


Posted by: heebie-geebie | Link to this comment | 03-14-14 6:56 PM
horizontal rule
240

Take the power set of countably many dwarves


Posted by: beamish | Link to this comment | 03-14-14 7:04 PM
horizontal rule
241

225: Spectacular.


Posted by: LizardBreath | Link to this comment | 03-14-14 7:04 PM
horizontal rule
242

. . . and posit a dwarf corresponding to each resulting set.


Posted by: beamish | Link to this comment | 03-14-14 7:06 PM
horizontal rule
243

I suppose so.


Posted by: heebie-geebie | Link to this comment | 03-14-14 7:06 PM
horizontal rule
244

I'm sure you could cover the set with finitely many dwarves, though.


Posted by: heebie-geebie | Link to this comment | 03-14-14 7:08 PM
horizontal rule
245

Because short.


Posted by: Moby Hick | Link to this comment | 03-14-14 7:13 PM
horizontal rule
246

But stocky


Posted by: teraz kurwa my | Link to this comment | 03-14-14 7:14 PM
horizontal rule
247

Anyway, went to BOGF bar. because no smoking and no young men in vests. Bartender was born in Poland. Kids are using passports as id because peak oil or some shit.


Posted by: Moby Hick | Link to this comment | 03-14-14 7:23 PM
horizontal rule
248

Is your bartender wearing a track or leisure suit? If so please do be careful.


Posted by: Barry Freed | Link to this comment | 03-14-14 7:27 PM
horizontal rule
249

I figured I'd try to solve snarkout's problem computationally; I had spent enough time pounding my head against the wall, and I've been wanting an excuse for a Haskell project. Here's my code; it's pretty messy since I don't really know Haskell and I'm sure I reinvented the wheel a few times.

Anyway, my results agree with what I found for 3 prisoners and with JP's 5. For 4 and for higher values, it starts breaking symmetry. Which is unnerving and probably means there's a bug (or else there are two equivalent answers and the maximization function I was using picked one arbitrarily). But whatever, it was fun to code up.

3 Prisoners
{
(0 Red,2 Green) -> PickRed
(1 Red,1 Green) -> Abstain
(2 Red,0 Green) -> PickGreen
}
Chance of escape: 0.75

4 Prisoners
{
(0 Red,3 Green) -> PickRed
(1 Red,2 Green) -> Abstain
(2 Red,1 Green) -> PickGreen
(3 Red,0 Green) -> PickRed
}
Chance of escape: 0.6875

5 Prisoners
{
(0 Red,4 Green) -> PickGreen
(1 Red,3 Green) -> PickRed
(2 Red,2 Green) -> Abstain
(3 Red,1 Green) -> PickGreen
(4 Red,0 Green) -> PickRed
}
Chance of escape: 0.6875

7 Prisoners
{
(0 Red,6 Green) -> PickRed
(1 Red,5 Green) -> Abstain
(2 Red,4 Green) -> PickGreen
(3 Red,3 Green) -> PickRed
(4 Red,2 Green) -> Abstain
(5 Red,1 Green) -> PickGreen
(6 Red,0 Green) -> PickRed
}
Chance of escape: 0.6640625

10 Prisoners
{
(0 Red,9 Green) -> PickRed
(1 Red,8 Green) -> Abstain
(2 Red,7 Green) -> PickGreen
(3 Red,6 Green) -> PickRed
(4 Red,5 Green) -> Abstain
(5 Red,4 Green) -> PickGreen
(6 Red,3 Green) -> PickRed
(7 Red,2 Green) -> Abstain
(8 Red,1 Green) -> PickGreen
(9 Red,0 Green) -> PickRed
}
Chance of escape: 0.6669922


Posted by: dalriata | Link to this comment | 03-14-14 7:30 PM
horizontal rule
250

Do you have electricity?


Posted by: Moby Hick | Link to this comment | 03-14-14 7:32 PM
horizontal rule
251

Either that or there's a hamster on a wheel in my computer's power supply. But he's probably dead after doing the 10 prisoner case.


Posted by: dalriata | Link to this comment | 03-14-14 7:38 PM
horizontal rule
252

249 - I am impressed and would like to see the code, since I don't know jack about Haskell! Nonetheless, there is an improved system that can be adopted. If it helps, it involves prisoners H, I, and J sitting on their hands and not participating and it lifts the odds to above 75%. I will happily give answers and hints via email to the obvious email address at gmail.com. (This problem apparently is due to a computer scientist named Todd Ebert, now of CSU Long Beach; the solution involves Hamming codes, as previously mentioned. The generalized solution certainly wasn't obvious to me when I learned the problem.)


Posted by: snarkout | Link to this comment | 03-14-14 7:40 PM
horizontal rule
253

The link to the code is in the first line of my last comment.

I forgot that I made a simplifying assumption that probably can't be justified for larger numbers of prisoners, namely that the only thing necessary to determine the answer is the number of bits going each way. Hrm, I'll try it without that and see how it goes, although that might make it somewhat more computationally intractable.


Posted by: dalriata | Link to this comment | 03-14-14 7:43 PM
horizontal rule
254

It's kind of creeping me out to call Iberian Beauty She-Trapnel, though they're both creepy in different ways. Is it just me?


Posted by: Thorn | Link to this comment | 03-14-14 7:43 PM
horizontal rule
255

251: Guess he shouldn't have guessed red.


Posted by: widget | Link to this comment | 03-14-14 7:44 PM
horizontal rule
256

252: I assume they are in some sense the "parity" bits ...?


Posted by: JP Stormcrow | Link to this comment | 03-14-14 7:44 PM
horizontal rule
257

256: Don't answer that. I'm feeling like I'm at the "tip of the tongue" stage the solution.


Posted by: JP Stormcrow | Link to this comment | 03-14-14 7:45 PM
horizontal rule
258

Although apparently my new problem-solving technique is to play online boggle until I'm too exhausted to think.


Posted by: JP Stormcrow | Link to this comment | 03-14-14 7:48 PM
horizontal rule
259

Also, Halford, I'm pretty sure my donation was outside the range of what you were matching, but I just matched it several times over to the kiddo of choice, so please don't feel any need to do so yourself even if I do meet your criteria.


Posted by: Thorn | Link to this comment | 03-14-14 7:48 PM
horizontal rule
260

Iberian Beauty She-Trapnel

This seems like a euphonious and economical pseudonym for her. I'm on board!


Posted by: Sifu Tweety | Link to this comment | 03-14-14 7:50 PM
horizontal rule
261

253: Actually, let's not do that, since in the most general case the toString of a solution would be over a thousand lines long, which is not interesting. There's probably some other shorthand representation (using, I dunno, Hamming codes), but meh. I'll just wait to hear JP explaining how to do it the right way.

(256: surely.)


Posted by: dalriata | Link to this comment | 03-14-14 7:51 PM
horizontal rule
262

Also tried Trapnelette but I figured She Ra is more badass than Smurfette so therefore Trapnelette was offensive. I also wrote a Haskell program demonstrating this logical result.


Posted by: RH | Link to this comment | 03-14-14 8:09 PM
horizontal rule
263

Kids are using passports as id because peak oil or some shit.

I guess I was an early adopter. I remember a couple times way back when bars would want a real ID some official thing, not a passport. An argument over that got me literally tossed from a bar in DC.


Posted by: teraz kurwa my | Link to this comment | 03-14-14 8:10 PM
horizontal rule
264

Hey, electricity.


Posted by: Moby Hick | Link to this comment | 03-14-14 8:12 PM
horizontal rule
265

I briefly used my passport as an ID when my driving license expired and I didn't have any pressing reason to get a new one. Actually I mostly used my expired license until I made the mistake of using it in a South Side bar.


Posted by: dalriata | Link to this comment | 03-14-14 8:13 PM
horizontal rule
266

264: Are/were you still at the bar? That's bizarre that it would be out. This is the mildest weather we've had in a while. I guess it is a little windy, which could have brought down trees.


Posted by: dalriata | Link to this comment | 03-14-14 8:17 PM
horizontal rule
267

For a couple months I used my Swiss ID because the month/day switch made me 21 a bit earlier.


Posted by: teraz kurwa my | Link to this comment | 03-14-14 8:18 PM
horizontal rule
268

OT: I worked my sexy magic to get Trapnel and SheTrapnel into the reception even though we didn't "win" the right to do so.

Woo Hoo! That really is great.

(I did think that "SheTrapnel" was both clever and kind of obnoxious the first time Halford used it. I'd vote for it not becoming a standard appellation.)


Posted by: NickS | Link to this comment | 03-14-14 8:39 PM
horizontal rule
269

NickS's version of both points is better than mine. Hooray!


Posted by: Thorn | Link to this comment | 03-14-14 8:43 PM
horizontal rule
270

"SheTrapnel" is hilarious.


Posted by: Bave | Link to this comment | 03-14-14 10:22 PM
horizontal rule
271

I remember a couple times way back when bars would want a real ID some official thing, not a passport. An argument over that got me literally tossed from a bar in DC.

Me too, here. When I protested, the bouncer said they wouldn't accept them because they were "too easy to forge". Right, that's why they use them for passports.


Posted by: Jesus McQueen | Link to this comment | 03-15-14 12:01 AM
horizontal rule
272

Oh, hey, I just looked at this thread for the first time. We're very excited about the party, all the more so because of not actually earning it (maybe that bit is just me).

I sort of agree about both pseuds sounding a bit creepy. I'll ask her for if she'd prefer something else.

... and now I'll actually read the thread. The dwarf thing has me puzzled.


Posted by: x.trapnel | Link to this comment | 03-15-14 12:15 AM
horizontal rule
273

OK, this woke me up. And I now have a stab at an answer that I think is right, but can't prove exactly why it is, but which builds off the Hamming clue and the n=3 solution.

So my 215 scheme ignored order (so not at all Hamming code-like where order is key). I think the n=3 problem is a bit deceiving in a way because for that one order doesn't matter, and the 215 scheme and hamming scheme give the same result but generalize differently.

Three observations:
1) If you do have an order (and each prisoner knows where they are in the order) for n>3 at a minimum you could just have the first three prisoners use the n=3 scheme and everyone else automatically abstain. In that case you get the 75% for all n, better than the scheme in 215.
2) Hamming codes have lengths 2n-1. So n=3 can be a Hamming (3,1) code and the next is a Hamming (7,4) code. [So I think snark's 252 it involves prisoners H, I, and J sitting on their hands and not participating is not because they are "parity" bits as I guessed in 256 (although there *are* 3 parity bits but it is a red herring I think) it is just that they do not add anything to the (7,4) code.]
3) So re-interpret the N=3 solution as a Hamming code problem by rewriting the rules as:
a) If given the pattern of the other bits you could make a Hamming code pattern that works choose the bit that would keep it from working. (In the N=3 case, the only "valid" codes are 0,0,0 and 1,1,1 so this covers the first two rules in 205)
b) Otherwise abstain.
So you only get wrong votes if the pattern actually is a valid (3,1) Hamming code (malicious torturers take note). In those two cases all 3 vote wrongly balanced by the six scenarios where only one votes and gets it right. If it is not a valid code voters either abstain or vote and get their color right.

So for n>3 per observation 2) the next Hamming code is (7,4)*. I will guess that n=4,5 or 6 cannot do better than the first 3 doing the n=3 strategy and everyone else sitting on their hands. But can't prove it. (Am pretty certain that would be right for n=4 ... but maybe by n-6 you can improve? Don't know.)

*I found the Hamming(7.4) article in Wikipedia to be more illuminating on how they work than the general article.


Posted by: JP Stormcrow | Link to this comment | 03-15-14 1:53 AM
horizontal rule
274

Solution for N=10.
Per snark last 3 always abstain. (So think this is the same for N=7,8,9 or 10 just with different number of abstainers.)

But first 7 do same as for n=3. (Always ignoring the last 3 booths. It's like they don even exist at this school in this problem.):
a) If given the pattern of the other bits you could make a Hamming code pattern that works, choose the bit that would keep it from working.
b) Otherwise abstain.
So this would only be wrong for the 16 valid hamming codes that a (7,3) can have for a nice 87.5% survival rate. in those 16 cases all 7 guess wrong so 112 wrong guesses balanced by the remaining 112 (128 total combinations minus 16) right guesses so have not violated the 50% guess rule. Just isolated the "wrongs" better than the scheme in 215.

So based on the Hamming code hint and snark, I think that I have the right answer. However, what I cannot prove yet is that there are no scenarios where everyone abstains--which is equivalent to saying every pattern can become a valid code by at most one bit flip. I think that property is inherent in how Hemming codes are built, but it's a hand wave by me at this point and the sandman is beating me to death.


Posted by: JP Stormcrow | Link to this comment | 03-15-14 2:13 AM
horizontal rule
275

274 is correct! I can send you a Python script later that demonstrates that the entire space is covered, but I'd have to think about how you'd prove rather than demonstrate it. In general, this system means that for any group of prisoners who number > 2^(k-1) and < 2^(k), they have a (1/2^k) chance of failing, by constructing the Hamming codes and assuming that one of them is in error.


Posted by: snarkout | Link to this comment | 03-15-14 7:30 AM
horizontal rule
276

275: Thanks for posting it. After I woke up to take a piss in the middle of the night I couldn't fall back to sleep for stewing on it. Had to overcome two cognitive barriers:

1) That the prisoners in the parity bit positions aren't treated differently than the data bit ones--the Wiki article on Hamming(7,4) helped with that.
and
2) That ending up with a valid code was the "bad" outcome even though applying the Hamming code to n-3 clearly indicated that was how it worked.

An interesting (to me anyway) thing about puzzles like this which generalize from special case is how to choose how the generalization "scheme" (similar to "what is the next number in this sequence?" problems). So the "same" n=3 solution can generalize in different ways as in the 215 scheme (which I think is the right solution to a slightly different problem where you are only told the totals of reds and greens for the other booths with no ordering info for them or you).


Posted by: JP Stormcrow | Link to this comment | 03-15-14 10:31 AM
horizontal rule
277

275: but I'd have to think about how you'd prove rather than demonstrate it.

Thinking about it this morning, I suspect it should be a corollary of the proof that the Hemming code can correct any single-bit error to a valid code.


Posted by: JP Stormcrow | Link to this comment | 03-15-14 10:36 AM
horizontal rule
278

Pretty sure 276.last is right; that's why my program found the same solution. Well, not sure if you were implying it in your "no ordering info..for you" but the other restriction we were operating on was that all prisoners use the same choice function. We can get to 75% for all n greater than 2 by just using the first three prisoners and having the rest abstain.


Posted by: dalriata | Link to this comment | 03-15-14 10:56 AM
horizontal rule
279

278: Right.

However, just using the first three prisoners implies that the prisoners know whether they are one of the first three or not. So absent any "order" information whatsoever, you will have the same choice function for all.


Posted by: JP Stormcrow | Link to this comment | 03-15-14 11:02 AM
horizontal rule
280

279: The prisoners can arbitrarily decide that they're the first three, e.g. assign Alice, Bob, and Charlene to be the ones that possibly don't abstain. The issue with order only comes in if Alice doesn't know which booths correspond to Bob and Charlene.


Posted by: dalriata | Link to this comment | 03-15-14 11:13 AM
horizontal rule
281

I briefly used my passport as an ID when my driving license expired and I didn't have any pressing reason to get a new one.

I always use my passport as an ID*, because I don't have any other ID.

*In the US - no need for it here.


Posted by: Ginger Yellow | Link to this comment | 03-16-14 8:35 AM
horizontal rule