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.
"You know how it's like 3.14....? It's like hella numbers?"
cow-orker
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.
In any seven hats, one is guaranteed to be black so they should all guess black.
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.
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.
6 is right, adjusting the age for me being older.
Also from OP: "How to guarantee that one dwarf correctly names the color of his hat?"
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."
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.
Are there even seven colors...at all?
Can they name their color "Fred" or "Harry"?
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.)
Does each dwarf get unlimited guesses? That might work.
11: There may not be! I guess it could have been worded "At most 7 colors."
Are there even seven colors...at all?
Black, white, gray, off-white, brown, ROYGBIV. That's the exhaustive, complete list.
15: I was being way sillier than you're taking me to be.
(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.
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.
(In fact your observation could be construed as a clue.)
Yeah, then I'm with 9.
And I assume they're not allowed to guess things like "Samsies of whatever Dwarf One said."
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.
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...
If they're allowed to hear each other's guesses, then Dwarf 1 just says whatever color he sees the most of.
What if they all agree that each one of them will guess a different color? Or does that count as knowing the others' answers?
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.
No, then everyone else just repeats Dwarf 1's answer. Someone will be right.
It can't be that they can hear each other's answers, though, because that's too silly.
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.
I suppose I did receive a separate answer with the email, but I'd rather get clarification on the situation.
From the OP
They do not have access to each other's answers.
So I'm going forth with the Isolation Booth assumption.
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".
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.
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.
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!
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.
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?
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.
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.
I know a version of this puzzle that involves maximizing correct guesses and is bassed on Hamming codes, but it doesn't guarantee correctness.
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?
Timing does not come into it at all.
Oh well, disregard 38 and 43, then.
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.
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!
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.
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?
I do believe that the tau is less stupid than Sifu thinks it is. But not strongly.
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.
Anyone have the link to the fundraiser handy? I'll kick in some more.
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.
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.
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.
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.
Violating the sanctity, Stormcrow wrote in the email "Not quite heavyweight for enough to stand as a whole puzzler".
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.
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).
There's a centaur in the isolation chamber with 1 or more dwarves, and the dwarf asks the centaur what color his hat is.
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!
"Why do I always have to wear the pink hat?"
-Reservoir Dwarves
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.
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.
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?
I'm thinking about peeking at the answer, which Stormcrow also emailed to me.
Can the dwarves take selfies with their smartphones and upload them to Tumblr or Instagram or Facebook and solicit comments?
One of the dwarves is an OPP, but it's Meekins.
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).
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.
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.
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.
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.
Hrm. No subsequent information is tricky and seems impossible, but I'm willing to trust there's something I'm overlooking.
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.
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.
Yep, there is a true, non-maddening answer.
Are the dwarfs academics? Do any of them have tenure?
I haven't completely worked out the math for myself, but it's very believable.
Is taupe even a real colour?
Can we ask them in order? Is it something like we only ask dwarf N if dwarves 1,...,N-1 have failed?
Oh, yes, it does work. Stormcrow even included a "why it works" email, which I had failed to read.
Now the only question is how insulted we should feel about 61.
So can you give us a hint about what information is communicated between the dwarves?
Thank god I can get some work done, now. Have fun, suckers.
That's "Absolutely no information" not "Absolutely no hint".
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.
I don't know what exactly I meant by "prevents overlap" in that last comment.
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.
Can every dwarf make up to 7 guesses?
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.
97, 98: nope, nope. Zero signalling of any kind.
97: so what would that be for 3 dwarfs?
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."
97, 99. Those both rely on communication, so I think they're verboten.
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.
But it's communication about success or failure.
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.
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?
108.1: Thanks for that clarification.
Does the game stop when somedwarf guesses correctly, or are they only told the result when they've all had a go?
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 . . .
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.
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.
114: Yeah. Unfortunately, duplicates are allowed.
No, because they can repeat. All the hats could be the same color.
Wait, so, if the 7 colors are known in advance, why don't they each assign themselves a color before hand and guess that?
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.
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.
Oh, right, 'cause they have to guess their own color. But Halford's doesn't work either, does it?
It has to be prime? I have no idea at all how that could play into it.
Oh whoops that was pretty dumb even for me.
I'm sure the answer hinges on multi-headedness among dwarves though.
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
. . .
118: Oh, so you think that they're dwarves was chosen because there are 7, not 7 because they're dwarves? Clever.
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?
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).
FIND OUT WHY PUZZLEMASTERS HATE LOCAL MOM'S ONE WEIRD TRICK!
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.
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.
The goal, obviously is to come up with a set of rules that guarantee coverage of all the possibilities.
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.
No, I confess that I just racked my brain for hat problems I've encountered before. The Hamming function one is good too!
||
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.
||>
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.
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.)
Is there an easy way to explain why 130 works?
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.
I think it does work for a non-prime number.
Why are 117 and 28 wrong?
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.
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.
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.
Snarkie is indeed a smartie (back form doc appt.)
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.)
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?
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!
Oh, dammit, stupid unfogged formatting.
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?
Those two quantifiers should be for all k < n. It wasn't unfogged formatting, I just once again forgot to escape my character entities.
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.
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).
I think you're right, Heebie - no multiplication means that this works even for four hats.
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.
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.
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.
That was a lot of fun. We should do more of these.
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.
we're specifically told that they can discuss strategy in advance
where were we told that?
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.
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.
Yay! Halfordismo & Stupidismo forever!
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.
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.
Pwnd but my explanation was stupider, therefore better.
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!
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.
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?)
No one wants to tackle 146? The poor mathematicians are going to be in those isolation booths until they starve to death.
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.
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.
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.
Or maybe that dwarf is just a really good guesser.
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.
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.
178: If they don't have access to the possible colors beforehand, this solution can't be done, I don't think.
172 is right.
179 is also right - I was imagining different rules where only the dwarves who guess correctly are spared.
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.
I understand this works in theory, but so does neoclassical macroeconomics. Has anyone actually tested this empirically on live dwarves?
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!
Reach out and touch the stupid!
I thought you weren't doing the online dating thing anymore?
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.
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??
Or what if the torturer cheats? Anyone who would set up a situation this cruel patently cannot be relied on.
187: It does assume perfection in that regard, yes.
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?
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.
190, continued: But the king is playing fair. He really wants mathematicians for his ninja army!
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.
189: so we were supposed to assume that the dwarves are infalliable calculators. You should have specified that.
Have I mentioned how much Urple reminds me of the Tortoise lately?
Also, it would have been helpful to know that the dwarves are familiar with modulo operations.
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).
196: Dwarves are familiar with all sorts of math, but particularly differential equations; they're useful in avoiding a feline chain reaction.
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.
Ah, thanks! Allows abstentions seems eminently reasonable for someone who'd construct such an elaborate execution apparatus.
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.
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.
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).
You know what's not too helpful here? The Wikipedia page for "hamming code."
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.
205 is the optimal strategy for 3 people.
s/to be/be/.
Also, I'm assuming that the king picks the number randomly and not maliciously.
207: See 192. The king is playing fair and assigning the colors randomly.
Oh, missed that. The king must be a Final Fantasy Tactics fan.
Nice. I think I am not qualified for this one.
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.
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.
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).
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.
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.
I was told there would be slightly less math.
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...)
On the plus side, if a rat tries to gnaw you, it'll die.
This thread manages to make poring over the appendices to traffic reports seem inviting.
I've found several cheating answers on the internet but I am too dumb even to figure it out using the cheats!
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.
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.
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.
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 ...
Great work! OK, when we start the boutique you and CC can handle the business development.
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.
225.1: Strong work. Apparently no math required.
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.
225: Nicely done.
I like that this thread uses Tolkien's plural for dwarves.
The "Stormcrow" should be a hint there.
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.
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..."
231.2: Purposefully, in a lame attempt to reduce insensitivity and increase nerdliness.
The guy I thought was maybe exhibiting a bit of psychosis is here tonight. He very deliberately did not sit by me.
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.
232/235: But I think everyone went along. Apparently nerdery beats pedantry? Who'd have thought?
I don't see how you could have uncountably many dwarves.
Take the power set of countably many dwarves
. . . and posit a dwarf corresponding to each resulting set.
I'm sure you could cover the set with finitely many dwarves, though.
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.
Is your bartender wearing a track or leisure suit? If so please do be careful.
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
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.
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.)
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.
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?
251: Guess he shouldn't have guessed red.
252: I assume they are in some sense the "parity" bits ...?
256: Don't answer that. I'm feeling like I'm at the "tip of the tongue" stage the solution.
Although apparently my new problem-solving technique is to play online boggle until I'm too exhausted to think.
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.
Iberian Beauty She-Trapnel
This seems like a euphonious and economical pseudonym for her. I'm on board!
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.)
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.
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.
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.
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.
For a couple months I used my Swiss ID because the month/day switch made me 21 a bit earlier.
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.)
NickS's version of both points is better than mine. Hooray!
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.
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.
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.
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.
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.
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).
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.
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.
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.
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.
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.