Math Puzzles (Read the Rules!)

[chiggins]

Does that mean I'm supposed to post the next brainteaser?

I believe it does, unless you wanna pass it on to Parks for not taking your $100 bet.

[veganray]

One of my faves. Helped me win a math contest at Virginia Commonwealth University when I was 12. Enjoy!

An insane despot (let's call him Frank Delicious) kidnaps 100 virgins & tells them he is about to line them up and that he will place either a red or blue hat on each of their heads. Once lined up, they must not communicate amongst themselves. Nor may they attempt to look behind them or remove their own hat.

Frank tells the virgins that they will be able to see all the hats in front of them. They will not be able to see the color of their own hat or any of the hats behind them, although they will be able to hear the answers from all those behind them.

Frank will then start with virgin in the back of the line and ask, "What color is your hat?" The virgin will only be allowed to answer, "Red," or "Blue," nothing more. If the answer is incorrect then the virgin will be silently killed. If the answer is correct then she may live but must remain absolutely silent.

Frank will then move on to the next virgin in line and repeat the question.

Frank makes it clear that if anyone breaks the rules then all the virgins will die, then allows the unfortunate ladies to consult before lining them up. Frank listens in while the virgins consult each other to make sure they don't devise a plan to cheat. To communicate anything more than their guess of red or blue by coughing or shuffling would be breaking the rules.

What is the maximum number of virgins they can be guaranteed to save? What strategy should they employ?

[ChUcK]

Was that your brainteaser?

[veganray]

If you are asking if I wrote it, the answer is no. I correctly solved it (among 99 other problems) iwhen I was in 7th grade to win the individual facet (there was a team competition, too, but I had no team) of a statewide timed math contest for high schoolers. (The headmaster of my school convinced the "powers that were" to let me in despite my youth.)

BTW - The obvious answer is, of course, incorrect.

[Parks]

I'm not sure what the exact rules are.

If the 100 virgins in the line can line up in pairs facing each other, then you can save at least 50 virgins if the first virgin in the pair guesses the hat color of the virgin that she is facing. The second virgin will then know their own hat color, and the first has a 50/50 shot at living.

I'm trying to think of a better solution, and one that doesn't involve facing each other in case that isn't allowed.

[edit]You can do the same thing by having odd numbered virgins guessing the hat color in front of them, and even numbered virgins saying their own hat color that they just heard to save at least 50.[/edit]

[edit]Just looked it up, this answer is wrong. Its sad that I couldn't easily see the answer, since it just uses a parity bit :D[/edit]

[veganray]

they will not be able to see the color of their own hat or any of the hats behind them

No facing allowed. Even if it were, clever virgins could save more of their own with a more optimum strategy that doesn't involve "cheating".

[edit]There are many algorithms that would yield 50% survival (such as random guessing), but none are optimum.[/edit]

[Trey133]

are there 50 red hats and 50 blue hats?

[veganray]

Maybe, but not necessarily. There can be any number of red & blue hats (as long as the sum is 100) & Frank ain't tellin' the virgins the distribution!

[J-Bolt]

They can see ALL hats in front of them, correct?

[veganray]

Yes. The last in line can see 99 hats, the second-to-last 98 hats, etc., until the first virgin in the line can see 0 hats.

Remember that Frank will start at the back of the line (where the virgin can see 99 hats) when demanding each virgin's choice.

[J-Bolt]

Here's my guess...

The virgins agree that the last(#100) will say the color of the first(#1). This way #1 knows her color and #100 has a 50% chance of living. Then #99 says the color of #2, so #2 knows her color and #99 has 50% of living. Continue with this method.

Guarantees 50 of them live, but most likely 75 will survive Franks violence.

[veganray]

They can do much better than that. Good thing virgins have become extremely clever in their years of narrowly escaping the evil defilement of manmeat.

[pdorries]

this shit is crazy

[pdorries]

the first virgin to respond guesses the color of the girl in front of her, she is the only one that will have a 50/50 chance of survival. the next girl replies with the color the girl behind her said, getting it right, but here is the kicker... if the girl in front of her has the same color as herself, she responds to the question "what color is your hat" immediately, if the girl in front of her has a different color hat, she waits 10 seconds and then says her answer, then the girl in front of her knows she has the opposite color, then the next girl says the correct color that is on her head but uses the same strategy of a timed response.

It seems to fall under your guideline of rules and guarantees that 99 will live.

[rusch_bag]

I was thinking your exact response myself, but I did not know if it was allowed.