DiMono
Level: Smitemaster

Rank Points: 1181
Registered: 09-13-2003
IP: Logged

Everyone kicks a guard in the nuts and runs?

____________________________
Deploy the... I think it's a yellow button... it's usually flashing... it makes the engines go... WHOOSH!

DiMono
Level: Smitemaster

Rank Points: 1181
Registered: 09-13-2003
IP: Logged

Is there an equal distribution of hats? Ten of each?

____________________________
Deploy the... I think it's a yellow button... it's usually flashing... it makes the engines go... WHOOSH!

DiMono
Level: Smitemaster

Rank Points: 1181
Registered: 09-13-2003
IP: Logged

Never mind, I think I have it. If the person in front of you has a red hat, you answer loudly. If the person in front of you has a white hat, you answer softly. The next person takes their cue from the volume of the person who just spoke. The first person takes a 50% guess at his own colour, using the correct volume for the person ahead of him, and so on.

If the tongues get cut out, they do the exact same thing with whatever grunting noise they can manage while signalling to the guard their choice.

____________________________
Deploy the... I think it's a yellow button... it's usually flashing... it makes the engines go... WHOOSH!

Schik
Level: Legendary Smitemaster

Rank Points: 5453
Registered: 02-04-2003
IP: Logged

While this is similar to one that Oneiromancer and I discussed a while ago, it has a pretty different solution, so I don't feel bad about solving it.

How about this:

The prisoners decide that the first person will say RED if he sees an even number of red hats, and WHITE if he sees an odd number of red hats.

The next person will then be able to figure out which color his is, since he sees all but his own - if #1 said red, and #2 sees even reds, then #2 is wearing white. If #1 said red but #2 sees odd reds, then #2 is wearing red. If #1 said white and #2 sees even reds, #2 is red, and if #1 said white and #2 sees odd reds, #2 is white.

The remaining can figure out theirs by the same method, subtracting the hat colors called before them from the equation.

This would save 19 people definitely, 20 if the first happened to be correct.

____________________________
The greatness of a nation and its moral progress can be judged by the way it treats its animals.
--Mahatma Gandhi

Oneiromancer
Level: Legendary Smitemaster

Rank Points: 2936
Registered: 03-29-2003
IP: Logged

Yeah, I did realize that it wasn't the same one after a bit, but got caught up in other stuff so I didn't have time to think of an answer. Oh, well.

Game on,

____________________________
"He who is certain he knows the ending of things when he is only beginning them is either extremely wise or extremely foolish; no matter which is true, he is certainly an unhappy man, for he has put a knife in the heart of wonder." -- Tad Williams

Mattcrampy
Level: Smitemaster

Rank Points: 2388
Registered: 05-29-2003
IP: Logged

Schik has it, by my reckoning.

Let's wait for Avon, though.

Matt

____________________________
What do you call an elephant at the North Pole?

Avon
Level: Delver
Rank Points: 47
Registered: 12-06-2003
IP: Logged

Yes, Schik is correct.

As the guards know this plan, they can ensure the first man is incorrect so they get to have at least one execution.

____________________________
"Les hommes ne sont jamais plus ingénieux que dans l'invention des jeux." -- Gottfried Wilhelm Leibniz

Schik
Level: Legendary Smitemaster

Rank Points: 5453
Registered: 02-04-2003
IP: Logged

An urn contains a number of colored balls, with equal numbers of each color. Adding 20 balls of a new color to the urn would not change the probability of drawing (without replacement) two balls of the same color.

How many balls are in the urn? (Before the extra balls are added.)


____________________________
The greatness of a nation and its moral progress can be judged by the way it treats its animals.
--Mahatma Gandhi

bibelot
Level: Smiter
Rank Points: 322
Registered: 07-11-2003
IP: Logged

There are 190, 10 each of 19 colors. The chance of picking two of the same color is 1/21.

Schik
Level: Legendary Smitemaster

Rank Points: 5453
Registered: 02-04-2003
IP: Logged

190 is correct - you're up!

____________________________
The greatness of a nation and its moral progress can be judged by the way it treats its animals.
--Mahatma Gandhi

bibelot
Level: Smiter
Rank Points: 322
Registered: 07-11-2003
IP: Logged

There are seven men taken prisoner, destined for execution. The executioner, being of a kind sort with a penchant for hats, proposes the following:

On the day of the execution, the seven men will be put in a circle and a hat will be placed on each man's head, either red or white, with equal probability. They will each then be given a piece of paper and a pencil. On the paper, they are to write what they believe is the color of their hat, either "red", "white", or they may leave it blank. The men will be set free if nobody guesses the wrong color on their paper and at least one person guesses correctly; they are all executed otherwise. (It is assumed that there will be no cheating, or else they will also be executed.) The men plan their strategy the night before. What is their best strategy, and what is the chance that they will survive?

agaricus5
Level: Smitemaster
Rank Points: 1838
Registered: 02-04-2003
IP: Logged

I'll probably get this wrong again - logic like this tends to be hard on my poor little brain.

But...

If they cannot cheat, I assume they must not communicate with each other in any way, shape or form (i.e. no body movements, sounds, signals or showing each other their pieces of paper). To survive, I suppose six must leave their papers blank and only one guess, giving them a 50% chance of surviving.

However, I suppose it's a silly answer that has no "common sense" in it, so it's probably incorrect.

____________________________
Resident Medic/Mycologist

The_Red_Hawk
Level: Smitemaster
Rank Points: 783
Registered: 09-02-2003
IP: Logged

Could you define "cheating" a little more please?

____________________________
Slashing, whirling, diving, twirling,
Snapping, turning, rising, swirling,
Screeching, flipping, gliding, sliding,
The red hawk's dance of death.

.....the king of the skies.....

bibelot
Level: Smiter
Rank Points: 322
Registered: 07-11-2003
IP: Logged

The prisoners can do better than 50-50.

"Cheating" is anything like signaling the other people or looking at one's own hat; basically, what a person writes (or does not write) must depend only on the colors of the hats of the other people.

StuartK
Level: Smitemaster

Rank Points: 564
Registered: 06-10-2003
IP: Logged

Bribing the guards is not prohibited? But then, the only thing the prisoners have to offer is a few hats, so I guess that's out of the question Your original question said 'no cheating' so I'll assume that was an incomplete qualification of 'cheating'
Also, what is the probability of successfully digging a tunnel or finding another escape route? The prisoners could keep their eyes open for something, but only take the opportunity if it's a 'sure thing' thus increasing their chances above 50%.


Other than that, as far as I can see, it will only ever be 50%.

I'm assuming (yes, a bad habit) you're thinking that the 'guesser' can do something better than 50-50 by looking at the number of hats of different colours, then basing his guess on this (e.g. if more than 3 hats are white, guess red, if more than 3 hats are red, guess white) Since each hat is picked independently, and has it's own equal, independent probability of being either red or white*, it will, no matter what the colour of the hats infront of the guesser, ever be possible to get the answer right 50% of the time.

The only information available is the colour of those 6 hats, but the colour of everyones hat, except that of the single guesser, is irrelevant. If more than one person makes a guess as to their hat colour, the chance of everyone surviving lowers. But it will never be higher than 50-50.

If, like Agaricus, I've not missed something subtle, I say he's got it.



* I'm assuming that each time one of the condemned has a hat picked, another hat is added to the 'pot'(and the 'pot', suitably agitated so the next person doesn't just get the new hat that has been placed at the top) so the probability of picking the same colour remains the same each time, as stated by the question.

Schik
Level: Legendary Smitemaster

Rank Points: 5453
Registered: 02-04-2003
IP: Logged

No, I'm finding ways to have better than 50% chances - I'm not done yet though, so I won't post how just yet.

Try the problem with fewer people - say 3 - and see if you can come up with anything.

____________________________
The greatness of a nation and its moral progress can be judged by the way it treats its animals.
--Mahatma Gandhi

DiMono
Level: Smitemaster

Rank Points: 1181
Registered: 09-13-2003
IP: Logged

The men pick an order in which to go. If the first person sees a high number of one colour or the other, he writes down the lower numbered colour, and everyone else writes nothing. If the first person sees an equal number of each colour, he sets his pencil down on his paper and leans back, and it's the next person's turn to do the same thing.


Edit: I've got a better solution. They pick someone whose sole purpose is to stare at someone wearing a red hat. That person writes "red", and everyone else writes nothing. If he looks down, it means he sees no red hats, and someone writes "white". This is 100% chance for survival.

[Edited by DiMono on 01-02-2004 at 05:27 AM GMT]

____________________________
Deploy the... I think it's a yellow button... it's usually flashing... it makes the engines go... WHOOSH!

Schik
Level: Legendary Smitemaster

Rank Points: 5453
Registered: 02-04-2003
IP: Logged

DiMono wrote:
The men pick an order in which to go. If the first person sees a high number of one colour or the other, he writes down the lower numbered colour, and everyone else writes nothing. If the first person sees an equal number of each colour, he sets his pencil down on his paper and leans back, and it's the next person's turn to do the same thing.

Half of the question was "What is their chance of survival?" You've described a method, but not it's chance.

Edit: I've got a better solution. They pick someone whose sole purpose is to stare at someone wearing a red hat. That person writes "red", and everyone else writes nothing. If he looks down, it means he sees no red hats, and someone writes "white". This is 100% chance for survival.

Okay. It's late and I'm cranky, but come on. How many times does it need to be said? Cheating isn't allowed. This is cheating. Assume for the puzzle that there is NO WAY TO COMMUNICATE WITH OTHER PEOPLE. If you try to communicate, you will be killed. Just like the last hat puzzle - you can't tap their shoulders, you can't speak loudly or softly to communicate. They can't take their hats off. They can't hum a few bars of a different song depending on the hat to the left of them. Stop trying to cheat and start trying to actually solve the puzzle.

____________________________
The greatness of a nation and its moral progress can be judged by the way it treats its animals.
--Mahatma Gandhi

zex20913
Level: Smitemaster

Rank Points: 1723
Registered: 02-04-2003
IP: Logged

I think that way might be considered "cheating".

Maybe we should define "cheating" to be doing anything other than looking at the hats, and writing down a color. No signals, staring or otherwise.

____________________________

Scott
Level: Smitemaster
Rank Points: 578
Registered: 02-12-2003
IP: Logged

Would seeing someone write or fail to write something be cheating?

Schik
Level: Legendary Smitemaster

Rank Points: 5453
Registered: 02-04-2003
IP: Logged

I'm getting a little frustrated coming up with what I'd be satisfied is an optimal answer, so I thought I'd share my thinking for 3 prisoners:

First, let's list all of the possibilities:
RRR RRW RWR RWW
WRR WRW WWR WWW

As you can see, there are usually two of one color and one of the other. So the best (?) solution for 3 people is this: If you see two differently colored hats, don't write anything. If you see two of the same color, write down the opposite color.

This would result in only losing if all hats are the same color - otherwise only one person will write something down, and it will be correct. Thus a 75% chance of success.

I extrapolated and modified this a bit for the 7 prisoner case, but I think I can do better with a different method. I also might be able to do better if I write a program to help me, but I'm trying not to resort to that.


____________________________
The greatness of a nation and its moral progress can be judged by the way it treats its animals.
--Mahatma Gandhi

Oneiromancer
Level: Legendary Smitemaster

Rank Points: 2936
Registered: 03-29-2003
IP: Logged

It can get tough when we have some puzzles that require lateral thinking, and some that require completely logical thinking. Perhaps the puzzle author should give hints in this regard...but that's part of the fun of solving the puzzle too.

Game on,

____________________________
"He who is certain he knows the ending of things when he is only beginning them is either extremely wise or extremely foolish; no matter which is true, he is certainly an unhappy man, for he has put a knife in the heart of wonder." -- Tad Williams

agaricus5
Level: Smitemaster
Rank Points: 1838
Registered: 02-04-2003
IP: Logged

I think I've got it.

The strategy is this:

If you see 4 same coloured hats, write the opposite colour on your sheet, or if you se 5 same coloured hats, write the same colour on your sheet, or else write nothing.

Variant

If you see 4 or 6 same coloured hats, write the opposite colour on your sheet, or else write nothing.

Both give a probability of 84/128 or 21/32 of survival.

I'm rushed for time now to get the answer in, and also because it may be wrong anyway, so if anyone wants the logic I used, I'll post it later.

____________________________
Resident Medic/Mycologist

zex20913
Level: Smitemaster

Rank Points: 1723
Registered: 02-04-2003
IP: Logged

This would not work at all. RRWWWWW where R represents a red hat and W a white. By your logic, everyone who wears a white hat sees 4 whites, and two reds. So they would write red.

Everyone with a red hat sees 5 whites, so they write white, by your logic. So, this is a way that everybody dies.

edit: does the executioner know the strategy that the men will try to employ?

[Edited by zex20913 on 01-02-2004 at 04:42 PM GMT: see above]

____________________________

agaricus5
Level: Smitemaster
Rank Points: 1838
Registered: 02-04-2003
IP: Logged

zex20913 wrote:
This would not work at all. RRWWWWW where R represents a red hat and W a white. By your logic, everyone who wears a white hat sees 4 whites, and two reds. So they would write red.

Everyone with a red hat sees 5 whites, so they write white, by your logic. So, this is a way that everybody dies.

Probability of 7 of 1 colour = 2/128
Probability of 6 of 1 colour = 14/128
Probability of 5 of 1 colour = 42/128
Probability of 4 of 1 colour = 70/128

So by logic, if they write the opposite colour when they see 4 same coloured hats, they will live if there are 4 of 1 colour altogether and die if there are 5 of 1 colour. Similarily, if they write the same colour if they see 5 of the same coloured hat, they will live if there are 6 of 1 colour altogether or die if all of the hats are the same colour. Since both strategies are mutually exclusive, you add the probabilities.

Living: 70/128 + 14/128 = 84/128
Dying: 42/128 + 2/128 = 44/128

____________________________
Resident Medic/Mycologist

The_Red_Hawk
Level: Smitemaster
Rank Points: 783
Registered: 09-02-2003
IP: Logged

Why don't you reduce those fractions?

Well done (if you got it right).

____________________________
Slashing, whirling, diving, twirling,
Snapping, turning, rising, swirling,
Screeching, flipping, gliding, sliding,
The red hawk's dance of death.

.....the king of the skies.....

zex20913
Level: Smitemaster

Rank Points: 1723
Registered: 02-04-2003
IP: Logged

The reduced fractions are 21/32 and 11/32. But this hinges on the question I asked about the knowledge of the executioner. If he knows the strategy, he can ensure they all die. If he doesn't know, this will work.

____________________________

agaricus5
Level: Smitemaster
Rank Points: 1838
Registered: 02-04-2003
IP: Logged

The_Red_Hawk wrote:
Why don't you reduce those fractions?

Well done (if you got it right).

I did at first:

Both give a probability of 84/128 or 21/32 of survival.

Look 4 posts up.

I didn't reduce them just to show people exactly where I got my answers from.

____________________________
Resident Medic/Mycologist

The_Red_Hawk
Level: Smitemaster
Rank Points: 783
Registered: 09-02-2003
IP: Logged

agaricus5 wrote:

Look 4 posts up.

I didn't reduce them just to show people exactly where I got my answers from.

Oh. Well, my math teacher always insists that I reduce all my answers.

____________________________
Slashing, whirling, diving, twirling,
Snapping, turning, rising, swirling,
Screeching, flipping, gliding, sliding,
The red hawk's dance of death.

.....the king of the skies.....

Schik
Level: Legendary Smitemaster

Rank Points: 5453
Registered: 02-04-2003
IP: Logged

I can beat 84/128.

The trick behind my solution is to find a set of permutations such that every other permutation (not in the set) differs by exactly one hat from exactly one permutation in the set.

Does that make sense? I'll explain it in detail for the problem of only 3 prisoners:

Our set of permutations ("codes" from here on out) would be (WWW, RRR). Note that these differ by 3 hats - thus, every other permutation differs from *exactly* one code by *exactly* one hat.

To enumerate again - WWR, WRW, RWW, RRW, RWR, WRR - each differs from one of the two codes by exactly 1 hat. So each person looks around - if what they see matches one of the codes (minus their own hat, of course) they pick the color NOT in the code. So again, for 3 people they'd get 6/8 or 75% correct. You are only NOT correct if the actual permutation matches one of the code permutations.

So let's extend this to 7 people. A little programming comes up with this set of codes:

RRRRRRR
WWWWWWW
WWWRRRR
RRRWWWW
WRRRRWW
RWWWWRR
RWRWRWR
WRWRWRW
RRWRWWR
WWRWRRW
WRRWWRR
RWWRRWW
RRWWRRW
WWRRWWR
WRWWRWR
RWRRWRW

So every permutation that's not in the code list differs by one hat from one code. So again, if any person sees something matching a code (minus his own hat), he guesses his hat is NOT the missing one from the matching code.

Since the only wrong guesses will be if the real situation matches one of the codes, the chances of survival are (128-16)/128 = 112/128 = 7/8.

Another way to figure it is that for each code, there are 7 permutations that are one off from it, and thus will be successfully guessed - 7*16/128 = 112/128 = 7/8.

If we want to generalize, then with this method, if there are N people, you have a N/(N+1) chance of guessing correctly.

____________________________
The greatness of a nation and its moral progress can be judged by the way it treats its animals.
--Mahatma Gandhi