Post Riddles

[DaShen]

Originally posted by: DaShen

Originally posted by: CarpeDeo
And this one is #7 from above, but I'm putting it again here for all to see.
Gargomoyle (sp?) has captured 50 smurfs. He tells them, "Tomorrow is your execution day. But I will give you a chance to live. I will line you up, all facing the same direction. I will randomly put either a black or white hat on your head. Starting from the smurf in the back (the one who can see the other 49 in front), if you guess the correct color of your hat, I will let you go." The smurfs have one night to figure out a plan. What plan do they come up to save the most # of smurfs? (Note: a smurf can see all the other smurfs in front of him. The 50 hats are randomly distributed (can be 25 white - 25 black or 3 white - 47 black).

This is just a guess. Since I was C.S. we talked a lot about these kinds of problems in Automata Theory.

I figure that you can treat the two colors as a binary pattern. In that case 1 would be white, 0 black.

if the first two smurfs are solids, either 1-1 or 0-0, then the 3rd smurf should guess 1 for 1-1 or 0 for 0-0 in front of him. If the first 2 smurfs are 0-1 or 1-0, then the 3rd smurf should remain silent and the 4th smurf should guess 0 for 0-1 or 1 for 1-0. Iterate through the 50 till you finish guessing.

In this way, worst case scenario (the guesser is wrong every time), only a little more than 66% will be able to leave free, since 1 out of 4 will make an absolute guess, and 1 out of the first 3 will have to remain in the next guess. (It is more than 25 free with this solution BTW). If only 1/2 of the guessers get it right, which follows probability, then more like 90% go free.

I am pretty sure this is a good way of doing it, but there could be a better one. You could even write a pice of code with random generated binary to check this solution.

So is this right?

 

[DaShen]

Originally posted by: Glavinsolo
BTW, I am not looking these up and all my answers are guesses. Please tell me if i'm right or not.

Probably, poison in ice. The other the house could've been condemned. The husband's wife probably died in labor.

Calin, asnwered the statue one, Ask the statue what the other statue guards.

 

[CarpeDeo]

Originally posted by: DaShen

Originally posted by: DaShen

Originally posted by: CarpeDeo
And this one is #7 from above, but I'm putting it again here for all to see.
Gargomoyle (sp?) has captured 50 smurfs. He tells them, "Tomorrow is your execution day. But I will give you a chance to live. I will line you up, all facing the same direction. I will randomly put either a black or white hat on your head. Starting from the smurf in the back (the one who can see the other 49 in front), if you guess the correct color of your hat, I will let you go." The smurfs have one night to figure out a plan. What plan do they come up to save the most # of smurfs? (Note: a smurf can see all the other smurfs in front of him. The 50 hats are randomly distributed (can be 25 white - 25 black or 3 white - 47 black).

This is just a guess. Since I was C.S. we talked a lot about these kinds of problems in Automata Theory.

I figure that you can treat the two colors as a binary pattern. In that case 1 would be white, 0 black.

if the first two smurfs are solids, either 1-1 or 0-0, then the 3rd smurf should guess 1 for 1-1 or 0 for 0-0 in front of him. If the first 2 smurfs are 0-1 or 1-0, then the 3rd smurf should remain silent and the 4th smurf should guess 0 for 0-1 or 1 for 1-0. Iterate through the 50 till you finish guessing.

In this way, worst case scenario (the guesser is wrong every time), only a little more than 66% will be able to leave free, since 1 out of 4 will make an absolute guess, and 1 out of the first 3 will have to remain in the next guess. (It is more than 25 free with this solution BTW). If only 1/2 of the guessers get it right, which follows probability, then more like 90% go free.

I am pretty sure this is a good way of doing it, but there could be a better one. You could even write a pice of code with random generated binary to check this solution.

So is this right?

Nope- but it's certainly the best wrong answer I've heard! I was a CS major- yet Automata Theory isn't ringing any bells. What class was it for?

Also, a smurf cannot remain silent. He must answer black or white.

The problem's not quite THAT difficult, though it's not easy.

Little hint for this problem:

Worst case scenario: 49 saved
Best case scenario: 50 saved

That should help a bit!

 

[DaShen]

Originally posted by: CarpeDeo

Originally posted by: DaShen

Originally posted by: DaShen

Originally posted by: CarpeDeo
And this one is #7 from above, but I'm putting it again here for all to see.
Gargomoyle (sp?) has captured 50 smurfs. He tells them, "Tomorrow is your execution day. But I will give you a chance to live. I will line you up, all facing the same direction. I will randomly put either a black or white hat on your head. Starting from the smurf in the back (the one who can see the other 49 in front), if you guess the correct color of your hat, I will let you go." The smurfs have one night to figure out a plan. What plan do they come up to save the most # of smurfs? (Note: a smurf can see all the other smurfs in front of him. The 50 hats are randomly distributed (can be 25 white - 25 black or 3 white - 47 black).

This is just a guess. Since I was C.S. we talked a lot about these kinds of problems in Automata Theory.

I figure that you can treat the two colors as a binary pattern. In that case 1 would be white, 0 black.

if the first two smurfs are solids, either 1-1 or 0-0, then the 3rd smurf should guess 1 for 1-1 or 0 for 0-0 in front of him. If the first 2 smurfs are 0-1 or 1-0, then the 3rd smurf should remain silent and the 4th smurf should guess 0 for 0-1 or 1 for 1-0. Iterate through the 50 till you finish guessing.

In this way, worst case scenario (the guesser is wrong every time), only a little more than 66% will be able to leave free, since 1 out of 4 will make an absolute guess, and 1 out of the first 3 will have to remain in the next guess. (It is more than 25 free with this solution BTW). If only 1/2 of the guessers get it right, which follows probability, then more like 90% go free.

I am pretty sure this is a good way of doing it, but there could be a better one. You could even write a pice of code with random generated binary to check this solution.

So is this right?

Nope- but it's certainly the best wrong answer I've heard! I was a CS major- yet Automata Theory isn't ringing any bells. What class was it for?

Also, a smurf cannot remain silent. He must answer black or white.

The problem's not quite THAT difficult, though it's not easy.

Little hint for this problem:

Worst case scenario: 49 saved
Best case scenario: 50 saved

That should help a bit!

Automata Theory? It is predicate cal, logics, and math theory, basically the makeup of A.I. programming. You know, P and NP complete kind of stuff.

Also your hint, where the 50th person guesses the person right in front of him, and you iterate down the group, was what one person guessed before, but you said it was wrong, so I assumed there was something you left out.

 

[DaShen]

Originally posted by: DaShen

Originally posted by: CarpeDeo
And this one is #7 from above, but I'm putting it again here for all to see.
Gargomoyle (sp?) has captured 50 smurfs. He tells them, "Tomorrow is your execution day. But I will give you a chance to live. I will line you up, all facing the same direction. I will randomly put either a black or white hat on your head. Starting from the smurf in the back (the one who can see the other 49 in front), if you guess the correct color of your hat, I will let you go." The smurfs have one night to figure out a plan. What plan do they come up to save the most # of smurfs? (Note: a smurf can see all the other smurfs in front of him. The 50 hats are randomly distributed (can be 25 white - 25 black or 3 white - 47 black).

This is just a guess. Since I was C.S. we talked a lot about these kinds of problems in Automata Theory.

I figure that you can treat the two colors as a binary pattern. In that case 1 would be white, 0 black.

if the first two smurfs are solids, either 1-1 or 0-0, then the 3rd smurf should guess 1 for 1-1 or 0 for 0-0 in front of him. If the first 2 smurfs are 0-1 or 1-0, then the 3rd smurf should remain silent and the 4th smurf should guess 0 for 0-1 or 1 for 1-0. Iterate through the 50 till you finish guessing.

In this way, worst case scenario (the guesser is wrong every time), only a little more than 66% will be able to leave free, since 1 out of 4 will make an absolute guess, and 1 out of the first 3 will have to remain in the next guess. (It is more than 25 free with this solution BTW). If only 1/2 of the guessers get it right, which follows probability, then more like 90% go free.

I am pretty sure this is a good way of doing it, but there could be a better one. You could even write a pice of code with random generated binary to check this solution.

There is one other solution that at best can save all 50 of the Smurfs but it assumes two things. 1) The smurf in front will always know who is right behind them. Another way of saying this is that when one person is taken off the line the line will compact so that there is no space. 2) There is a time delay between saying your color and remaining silent before the one in front can say anything.
*You can eliminate the first one by having a global clock that all of the smurfs can see, and having each smurf at the assigned seat, have a designated time. In other words, if you start at the beginning of the hour then the nth, or 50th, person has one minute to respond.

Here is the other solution I thought of, this is probably the one that CarpeDeo was thinking of, but its worst case is not 49. In most cases it is, but it can be much worse.

Think of 2 things that must be satisfied.
1. You wish to save yourself
2. You wish to save the people in front of you, but you cannot say anything but your own color if you wish to satisfy postulate 1.

So if the last person in line guesses the n-1 color, in this case the 49th person, the nth person will have a 50% chance of surviving.

Because of these two postulates, the factor of time becomes very necessary. Therefore two rules must be given.

If you know your color, and by default since the n-1 color is broadcasted to everyone by the last, or nth person, then you must do one of two things.

If the person in fron of you n-2 is your color, you guess your color, otherwise you remain silent.
Your silence, if on a time delay everyone agrees upon, will broadcast to the person in front of you that they are the opposite color.

In either case the person directly in front of you, as well as all the other smurfs will, knows this smurfs color, and therefore can do the algorithm again to the next person in line.

Whoever is the constant color in the back is the key to the whole thing working. In this case whoever is in the 49th position.

----------------------
The problem is that if the people are given alternate colors for a while, the "time delay" becomes more important. Because with the time delay, any person that is silent after the last person who guessed will switch the color down to you. i.e. - if the 49th person is silent and the 50th color called black, then the 48th person is white, and so on. With the time delay, either by everyone trying to keep synchronized or a global clock, and some good logging, everyone after the 50th person will know what color he is.

Example with 5 smurfs.
white11010
silence1010
1silence010
10silence10
They all "guess" correctly. And the 5th one was lucky.
Now with good logging the 1st one in line will know he is black. Basically all of them know there color.
-----------------------

Without the clock and without the compacting of the chairs, the solution becomes much more complicated. The smurf must count how many broadcasts have been made behind him because he can never be sure as to who is behind him. If he is the n-m person, then he must wait for at least m-1 people to "guess". If m-1 people guess, then the last persons guess is the opposite of what your color is. If m people guess, then the last persons guess is the same as your color. The only problem remains if the people alternate through most of the list to the point where it is humanly, or smurfly impossible , to keep track of the time delay. There is a chance that one person in the middle must take a guess, so that the rest can survive.

white 110110101010...
silence 10110101010...
1silence 0110101010...
10white 110101010...
10silence 10101010...
silence
.
.
.
The front people don't know what color they are. The last one to figure out his color from whoever was behind him must restart the guess (and he might have to sacrifice himself). Then he restarts the cycle from him and all people who know behind him can sit back and relax and guess when the cycle is over. So there is a slim chance that less than 49 people will survive.

I think this is a solution (I figured it out on the Metro back home), that works in most case giving 49-50 smurfs surviving, but without the assumptions it could be less.

 

[z0mb13]

head explodes...

 

[z0mb13]

head explodes...

 

[CarpeDeo]

Wow . . .

Umm- the answer is much simpler. Sometimes, being too smart/ knowing too much makes these riddles even harder.

Interesting answer though . . . I've never heard an answer that tried to use time as an extra variable.

Some constraints:

-Gargomoyle provides no clock and no chairs, he's not quite so sympathetic to your requests.


Some things to keep in mind:

-A smurf can see every smurf standing in front of him. (stated this already)

-When a smurf answers "black" or "white", all the other smurfs can hear him. (you already assumed this)


Some hints:

-saving 49 is the worst case. saving 50 is the best case. The likelihood of saving 49 smurfs is 50%, the likelihood of saving 50 smurfs is 50%.

I have one "big" hint that I can give you. Well- it's actually not THAT big of a hint, but it might get you on the right track. Let me know when you want to know the hint.

 

[Speck102]

I've thought of one way, but worst case scenerio would be that 25 die, so it's probably not the right answer. I was thinking that starting with the last smurf, every other smurf says the color of the smurf in front of him, if his happens to be the same he lives, if not he dies, but the smurf in front of him will know his color for certain. Then just keep repeating this process untill you get to the end.

 

[Speck102]

Okay, here is a question, you say that they start from the last one, but do they have to go in order the whole way, or can they jump from one to another?

 

[CarpeDeo]

Originally posted by: Speck102
Okay, here is a question, you say that they start from the last one, but do they have to go in order the whole way, or can they jump from one to another?

In order. No jumping around.

 

[DaShen]

My answer actually reflect 49 as worst case in 49% of the cases. and 50 in 50% of the cases.

50 guesses 49s color. He is correct on his color only 50% of the time.

49 now knows his color, and will only say his color if the person in front of him has that color. If he doesn't say his color, 48 knows his color is the opposite color. 48 will do the same as 49 did and so on, but the algorithm fails on a few minor cases which I discussed on the previous post. Hope that helps for anyone who wants to read cribs.

I believe this is what you wanted, but the problem is that it can be much worse in a few cases without a time delay (to take care of the case of alternating colors throughout). I guarantee that. Read my previous post and you should see.

The best part of this algorithm is that you only need to deal with knowing the color fo the person right in front of you (which is done recursively).

 

[GasX]

The first smurf says the color of the smurf in front of him. The next smurf says the color said by the first smurf. If the smurf in front of him's hat is that color too, he says it in that annoying sing song smurf voice. If not, he says it in a different voice. The next smurf says his color and the pattern continues. Every smurf has 100% chance except the first one who has a 50% chance

 

[DaShen]

Originally posted by: Mwilding
The first smurf says the color of the smurf in front of him. The next smurf says the color said by the first smurf. If the smurf in front of him's hat is that color too, he says it in that annoying sing song smurf voice. If not, he says it in a different voice. The next smurf says his color and the pattern continues. Every smurf has 100% chance except the first one who has a 50% chance

I didn't take into account changing your voice tone. That would get rid of all time delays because guesses would be instantanious. Good job, Mwilding. Way to think outside the box. :thumbsup:

A vocal change allows for another variable other than the guess to pass on to the next smurf.

 

[GasX]

Originally posted by: CarpeDeo8) A husband and wife are stopped at a gas station to fill up their car. The husband gets out to pay the cashier and use the toilet. When he gets back, he finds his wife dead and another person in the car. The doors were locked since he left for the gas station and not a single window is broken. How did the third person get in the car?

JToxic got this one. "His wife had a baby and died during childbirth"

This is a ludicrous answer to the riddle.

Labor takes several hours not the time it takes to gas a car and take a piss. If a man is taking his wife to the hospital because she is in labor, he MAY stop for gas if he absolutely has to, but there is no way in hell is going to take a slash and leave her alone if she is well dialated.

 

[DaShen]

Originally posted by: Mwilding

Originally posted by: CarpeDeo8) A husband and wife are stopped at a gas station to fill up their car. The husband gets out to pay the cashier and use the toilet. When he gets back, he finds his wife dead and another person in the car. The doors were locked since he left for the gas station and not a single window is broken. How did the third person get in the car?

JToxic got this one. "His wife had a baby and died during childbirth"

This is a ludicrous answer to the riddle.

Labor takes several hours not the time it takes to gas a car and take a piss. If a man is taking his wife to the hospital because she is in labor, he MAY stop for gas if he absolutely has to, but there is no way in hell is going to take a slash and leave her alone if she is well dialated.

That isn't always true. She could have been due later on and had complications and a forced birth.

 

[GasX]

Originally posted by: DaShen
That isn't always true. She could have been due later on and had complications and a forced birth.

MAYBE and I emphasize MAYBE if the guy was taking a dump and had some really bad constipation, but noone spits out a kid and dies from complications in the time it takes to drain a bladder.

 

[CarpeDeo]

Originally posted by: Mwilding

Originally posted by: DaShen
That isn't always true. She could have been due later on and had complications and a forced birth.

MAYBE and I emphasize MAYBE if the guy was taking a dump and had some really bad constipation, but noone spits out a kid and dies from complications in the time it takes to drain a bladder.

Dude was going #2 . . . and had to go reaaallly bad. How's that?

 

[CarpeDeo]

Originally posted by: DaShen

Originally posted by: Mwilding
The first smurf says the color of the smurf in front of him. The next smurf says the color said by the first smurf. If the smurf in front of him's hat is that color too, he says it in that annoying sing song smurf voice. If not, he says it in a different voice. The next smurf says his color and the pattern continues. Every smurf has 100% chance except the first one who has a 50% chance

I didn't take into account changing your voice tone. That would get rid of all time delays because guesses would be instantanious. Good job, Mwilding. Way to think outside the box. :thumbsup:

A vocal change allows for another variable other than the guess to pass on to the next smurf.

Haha- fine.

Let's change the riddle a little then. Gargomoyle goes to each smurf, starting with the one in the back. No smurf can say anything. Rather, the smurf raises his right hand for white, and his left hand for black, where only Gargomoyle can see. Actually- use whatever you want, the smurf points to a black piece or white piece of paper that Gargomoyle is holding. But something only Gargomoyle can see. Gargomoyle will then announce to the smurfs which color the smurf chose, black or white. He may choose to do it instantly after the smurf chooses the color, or he may choose to wait awhile. Any smurf who makes any sound loud enough for another smurf to hear will instantly be killed.

I think that removes most other possible variables. Keep trying!

 

[CarpeDeo]

Originally posted by: DaShen
My answer actually reflect 49 as worst case in 49% of the cases. and 50 in 50% of the cases.

50 guesses 49s color. He is correct on his color only 50% of the time.

49 now knows his color, and will only say his color if the person in front of him has that color. If he doesn't say his color, 48 knows his color is the opposite color. 48 will do the same as 49 did and so on, but the algorithm fails on a few minor cases which I discussed on the previous post. Hope that helps for anyone who wants to read cribs.

I believe this is what you wanted, but the problem is that it can be much worse in a few cases without a time delay (to take care of the case of alternating colors throughout). I guarantee that. Read my previous post and you should see.

The best part of this algorithm is that you only need to deal with knowing the color fo the person right in front of you (which is done recursively).

By the way, if you do allow time delays (which I do not in the variation), you can save 49 in the worst case scenarios with a much simpler algorithm.

If the person in front of him has a white hat, he waits no time (or very little time) before he gives his answer. If the person in front of him has a black hat, he waits at least 10 seconds (or 20 or 30, whatever makes it obvious enough) before he gives his answer. Regardless of the color the smurf says, the time delay alone indicates what the color of the next smurf's hat is.

But I took out the possibility for controlled time delays and changing voice patterns in the modified version. You do not need any other variables!

 

[DaShen]

Originally posted by: CarpeDeo

Originally posted by: DaShen
My answer actually reflect 49 as worst case in 49% of the cases. and 50 in 50% of the cases.

50 guesses 49s color. He is correct on his color only 50% of the time.

49 now knows his color, and will only say his color if the person in front of him has that color. If he doesn't say his color, 48 knows his color is the opposite color. 48 will do the same as 49 did and so on, but the algorithm fails on a few minor cases which I discussed on the previous post. Hope that helps for anyone who wants to read cribs.

I believe this is what you wanted, but the problem is that it can be much worse in a few cases without a time delay (to take care of the case of alternating colors throughout). I guarantee that. Read my previous post and you should see.

The best part of this algorithm is that you only need to deal with knowing the color fo the person right in front of you (which is done recursively).

By the way, if you do allow time delays (which I do not in the variation), you can save 49 in the worst case scenarios with a much simpler algorithm.

If the person in front of him has a white hat, he waits no time (or very little time) before he gives his answer. If the person in front of him has a black hat, he waits at least 10 seconds (or 20 or 30, whatever makes it obvious enough) before he gives his answer. Regardless of the color the smurf says, the time delay alone indicates what the color of the next smurf's hat is.

But I took out the possibility for controlled time delays and changing voice patterns in the modified version. You do not need any other variables!

True. I thought of that, too, but it seemed like the same thing as the voice change though.


Also, in the new version, does Gargomoyle announce which chair chose?

 

[shuan24]

good riddle....i had to cheat, too hard for simpletons like me.

 

[CarpeDeo]

Originally posted by: DaShen

Originally posted by: CarpeDeo

Originally posted by: DaShen
My answer actually reflect 49 as worst case in 49% of the cases. and 50 in 50% of the cases.

50 guesses 49s color. He is correct on his color only 50% of the time.

49 now knows his color, and will only say his color if the person in front of him has that color. If he doesn't say his color, 48 knows his color is the opposite color. 48 will do the same as 49 did and so on, but the algorithm fails on a few minor cases which I discussed on the previous post. Hope that helps for anyone who wants to read cribs.

I believe this is what you wanted, but the problem is that it can be much worse in a few cases without a time delay (to take care of the case of alternating colors throughout). I guarantee that. Read my previous post and you should see.

The best part of this algorithm is that you only need to deal with knowing the color fo the person right in front of you (which is done recursively).

By the way, if you do allow time delays (which I do not in the variation), you can save 49 in the worst case scenarios with a much simpler algorithm.

If the person in front of him has a white hat, he waits no time (or very little time) before he gives his answer. If the person in front of him has a black hat, he waits at least 10 seconds (or 20 or 30, whatever makes it obvious enough) before he gives his answer. Regardless of the color the smurf says, the time delay alone indicates what the color of the next smurf's hat is.

But I took out the possibility for controlled time delays and changing voice patterns in the modified version. You do not need any other variables!

True. I thought of that, too, but it seemed like the same thing as the voice change though.


Also, in the new version, does Gargomoyle announce which chair chose?

I'm actually still not quite so clear on what you mean by the chairs. But to simplify, let's assume that they're all standing. No chairs. No smurf can move positions.

 

[DaShen]

Originally posted by: CarpeDeo
I'm actually still not quite so clear on what you mean by the chairs. But to simplify, let's assume that they're all standing. No chairs. No smurf can move positions.

But are they indexed so the 23rd person is 23? No?

 

[Zoblefu]

The smurf in the back says the color of the one in front.

He knows his color. He says his color and exits to the right if the color in front is black... to the left if it is white....(etc)

I'm guessing this isn't it either, but it's fun to keep finding ways to work around the rules