|
|
friendofgunnar
Honorable
Legendary Hero
able to speed up time
|
posted July 10, 2009 08:59 AM |
|
|
Quote:
Ok let me get the details right - he will let them each pick an end in each hand, but he won't let go of any of the chains before all gnomes have picked their two ends
That's correct. Also, as I said before, the two ends that they pick up have to be from their own side.
|
|
Binabik
Responsible
Legendary Hero
|
|
posted July 10, 2009 09:01 AM |
|
|
I don't know how to do the math on this, but
4 gnomes of the port side, we'll call them P1, P2, P3, P4
4 gnomes on the starboard side, we'll call them S1, S2, S3, S4
Each gnome has a left and right hand, so we have
P1L, P1R, P2L, P2R, etc
Everyone on the port side grabs a chain with each hand. They will all grab a "correct" chain. In other words, it doesn't matter what they grab.
Everyone on the starboard side grabs a chain with their right hand only. Again, it doesn't matter what they grab.
So we have 4 starboard left hands remaining to grab chains.
In order:
S1L has a 75% chance of grabbing a correct chain and 25% chance of a wrong chain
S2L has a 67% chance of grabbing a correct chain and 33% chance of a wrong chain
S3L has a 50% chance of grabbing a correct chain and 50% chance of a wrong chain
S4L sinply takes what's left
So by my reckoning, out of 16 hands there are only 3 that matter. Somehow that doesn't seem right and I'm sure someone will point that out to me.
____________
|
|
alcibiades
Honorable
Undefeatable Hero
of Gold Dragons
|
|
posted July 10, 2009 09:02 AM |
|
|
Quote:
Also, as I said before, the two ends that they pick up have to be from their own side.
Oh ok, and do we know that he doesn't bend any of the chains back - i.e. all chains have separate ends on each side?
____________
What will happen now?
|
|
Rarensu
Known Hero
Formerly known as RTI
|
|
posted July 10, 2009 10:30 AM |
|
Edited by Rarensu at 10:46, 10 Jul 2009.
|
8/35
@ Binabik: your method gives an answer of 1/4. You're very close, but your probabilities are off because the 3 important hands get chosen while some of the 1-to-1 connections aren't in place yet, which tweaks them slightly.
@ Alcibiades: All chains cross from one side to the other.
____________
Sincerely,
A Proponent of Spelling, Grammar, Punctuation, and Courtesy.
|
|
friendofgunnar
Honorable
Legendary Hero
able to speed up time
|
|
posted July 11, 2009 09:22 AM |
|
|
Quote:
Everyone on the starboard side grabs a chain with their right hand only. Again, it doesn't matter what they grab.
So we have 4 starboard left hands remaining to grab chains.
In order:
S1L has a 75% chance of grabbing a correct chain and 25% chance of a wrong chain
The first part of your post was on the right track. However if everybody on the starboard side grabs it with their right hand, depending on the configuration that they grab, S1L might have a 100% percent chance of grabbing a correct chain with his left hand. This opens up a lot of complications. There's an easier way of working through the problem.
Still no correct answers btw.
and yes, The slavemaster is holding all the chains in the middle, no trickery with that part.
|
|
friendofgunnar
Honorable
Legendary Hero
able to speed up time
|
|
posted July 17, 2009 11:03 AM |
|
|
Ok, all the gnomes on the starboard side grab the chains with both hands, it doesn't matter which ones they grab.
Port Gnome #1 grabs a chain with his left hand, it doesn't matter which one. There's seven options for his right hand. One of those options will form a loop, thereby precluding a loop that includes everybody. Six of those options are safe. So 6/7
Port Gnome #2 grabs a chain with his left hand. He might be connected to gnome #1 or he might not be. In both cases when he grabs a chain with his left hand there will be a 1 in 5 chance of making a small loop. 4 of those options will be safe. So 4/5
Port Gnome #3 grabs a chain with his left hand. He might be connected to a gnome #1/gnome #2 linkage, or he might be connected to either one but not the other. In both cases, he has 1 in 3 chance of making a smaller loop. 2 of those options will be safe. So 2/3
Assuming everybody has chosen safe so far, grome #4 will automatically make one big loop. So the probability is 6/7 * 4/5 * 2/3 = 45.7%
|
|
Corribus
Hero of Order
The Abyss Staring Back at You
|
|
posted July 17, 2009 09:24 PM |
|
|
I just saw this problem you posted FOG and when I read your answer, I thought, "No way, that number has to be too high."
So I worked out the probability the long, hard way and to my surprise I also got 45.7(142857143)% How about that!
|
|
ihor
Supreme Hero
Accidental Hero
|
|
posted July 19, 2009 10:58 AM |
|
|
Hi, I have one more problem for you.
Let's say there are 100 wise men in the prison. One day they all have to be executed. The executor creates a column of wise men and gives a hat of red, green or blue color to each man. The column is created in such a way, so each wise man could see a color of hat of all the persons standing in front of him, but he couldn't see the color of his hat and hats of the persons behind him. Then the executor begins to ask each wise man (begins from the end of column) the color of his hat. If the answer is correct then wise man will be free, else he will be executed.
The wise men could agree before execution their actions to maximize the number of survivors.
What is this maximum number, that will survive for sure?
____________
Your advertisement could be
here only for 100$ per day.
|
|
friendofgunnar
Honorable
Legendary Hero
able to speed up time
|
|
posted July 20, 2009 03:56 AM |
|
|
The highest guarenteed number that they can save is 55 wise men.
I'll be back later to describe my math...
|
|
ihor
Supreme Hero
Accidental Hero
|
|
posted July 20, 2009 08:45 AM |
|
Edited by ihor at 08:48, 20 Jul 2009.
|
Quote:
The highest guarenteed number that they can save is 55 wise men.
I'll be back later to describe my math...
I'm very interested in your solution. But to make it more clear:
Each wise man could only say the one word - the color. All other(who are alive  ) could hear it.
____________
Your advertisement could be
here only for 100$ per day.
|
|
Warmonger
Promising
Legendary Hero
fallen artist
|
|
posted July 20, 2009 08:51 AM |
|
|
|
I know this riddle. There was an easy solution if we knew how many hats of each color there are. But if we don't have such knowledge, things become more complicated.
|
|
ihor
Supreme Hero
Accidental Hero
|
|
posted July 20, 2009 09:25 AM |
|
|
You are right. I haven't think about it. Let's say in my riddle all wise men know that there are only 3 possible colors, but it's much more interesting when they not. I will think about it.
____________
Your advertisement could be
here only for 100$ per day.
|
|
friendofgunnar
Honorable
Legendary Hero
able to speed up time
|
|
posted July 21, 2009 12:12 AM |
|
|
The simple solution is that each even numbered person announces the color of the hat in front of him. Each odd numbered person saves his own skin. In this way you will get 50 guarenteed saves, plus an average of 16.7 saves due to the possibility that an announcers hat will be the same color as the hat of the person in front of him.
Here's the math for my solution:
Each wise man can say one of three words. But they can also refuse to answer. In this way, they can transmit more information to the people in the front of the line. They can transmit one bit (in a base 4 system). This has a little bit extra information than saying just one of the three colors. The requirement is that the group of people at the back of the line transmit enough information (in base 4) to save the group at the front of the line (in base 3).
For example for 9 people, 4 people can save 5 people guarenteed (4 ^4 = 256 is greater than 3^5 = 243)
My logarithm math is really rusty so I made a computer program. It basically started out with a few people and then steps up to the number of 100. I used floating point decimals, so there will be a lack of precision that may affect the final answer.
5 + 4 = 9 (55.56 % will be saved)
5 + 5 = 10 (50.00 % will be saved)
11 + 9 = 20 (55.00 % will be saved)
16 + 14 = 30 (53.33 % will be saved)
22 + 18 = 40 (55.00 % will be saved)
27 + 23 = 50 (54.00 % will be saved)
33 + 27 = 60 (55.00 % will be saved)
39 + 31 = 70 (55.71 % will be saved)
44 + 36 = 80 (55.00 % will be saved)
50 + 40 = 90 (55.56 % will be saved)
55 + 45 = 100 (55.00 % will be saved)
You can see it seems to hover around 55%.
Here's the funny part. When a person refuses to answer he gets executed, so you'll lose more of the "randoms" than with the basic strategy. If you compare the two methods you see that the result is about the same.
Basic= 50 guarenteed plus 16.6 randoms = 66.6 people saved
Advanced = 55 guarenteed plus 11.25 randoms = 66.25 people saved
|
|
ihor
Supreme Hero
Accidental Hero
|
|
posted July 21, 2009 10:17 AM |
|
|
Ok, I understand your trick, which allows transmit more information. But proof must consist of 2 parts. In your situation:
1)Proof that 55 wise men will survive for sure.
2)Proof that 56 wise men will not survive for sure.
Try to improve your result of 55.
About the problem when wise men don't know the number of colors:
The natural question: How many colors do exist? Assume there are infinite number of colors. Then I think the answer is simple 50 like FOG described in the beginning. You can't get result of 51 because it could be 100 different colors for each wise man and since there are infinite number of colors then each wise man can't give information for more than one person.
____________
Your advertisement could be
here only for 100$ per day.
|
|
Rarensu
Known Hero
Formerly known as RTI
|
|
posted July 23, 2009 08:57 AM |
|
Edited by Rarensu at 09:53, 23 Jul 2009.
|
Quote:
Assuming everybody has chosen safe so far, grome #4 will automatically make one big loop. So the probability is 6/7 * 4/5 * 2/3 = 45.7%
*forehead-slap*
That's the same math I used, except when I multiplied it out in the end, I accidentally one of the 2s. You'll notice that 8/35 is exactly half of your answer. (22.9%)
About the wise-men. I've seen a very similar problem, but there were only two colors (red and blue). The answer if there are only two colors is to have the first wise man say "red" if the number of red hats in front of him is even or "blue" if the number of red hats is odd. Then next wise man counts the number of red hat in front of him, and if the number is the same class as the previous established class, then he knows his hat is blue. If the class is different, he knows his hat is red. The men in front hear the answers and keep a tab on whether or not the number of known red hats is currently even or odd. 99 of them are guaranteed to live, and the first one has a 50% chance.
The 3-color variant is an extension of the same principle. To form 98 hats, either all three colors are even or one of them is even. The first wise man says red to signify that they are all even or blue if one of them is even. The second wise man then says which color is the even one, if it isn't all three. The other 98 men can then count colors and determine which color is missing a hat.
If you have 4 colors, then the first wise man determines if the colors of the last 97 hats have are 3-and-1 or 1-and-3. The second wise man says the off color. The third wise man might die because if the first two have to account for him then they can't do it on their own.
If you have 5 colors, then the first wise man determines if the colors of the last 97 hats are all odd, 2-and-3, or 4-and-1. If it's 2-and-3, then the next two wise men name the two even colors. If it's 4-and-1, then the second wise man names the odd color.
The pattern continues similarly.
2 colors, 1 man
3 colors, 2 men
4 colors, 3 men
5 colors, 3 men
6 colors, 3 men
7 colors, 4 men
8 colors, 5 men
9 colors, 5 men
10 colors, 6 men
11 colors, 6 men
12 colors, 7 men
____________
Sincerely,
A Proponent of Spelling, Grammar, Punctuation, and Courtesy.
|
|
ihor
Supreme Hero
Accidental Hero
|
|
posted July 23, 2009 07:17 PM |
|
|
You present good solution for 2 colors and 98 survivors when 3 colors.
The same question for 3 colors:
Could it be 99 survivors?
Of course it's obvious that it couldn't be 100 guaranteed.
____________
Your advertisement could be
here only for 100$ per day.
|
|
Ecoris
Promising
Supreme Hero
|
|
posted July 23, 2009 08:56 PM |
|
Edited by Ecoris at 20:57, 23 Jul 2009.
|
100 persons, 3 colors: 99 can be saved.
The first wise man counts the number of red/green/blue hats in front of him. The sum is 99, there are two cases:
1 All odd
The first wise man says nothing indicating to all the others that they are in the "all odd" case. The second wise man deduces the color of his hat and says it. The third wise man can then do the same, and so on.
2 Just one "odd" color
There are two subcases:
a) The second wise man's hat has the "odd" color. The second wise man will then see three "even" colors in front of him, which only happens in case 2a. The first wise man will simply say the color of the second wise man's hat, who will then save himself. The first two wise men will then have said the same color; this only happens in case 2a. Now the remaining 98 wise men know they are in case 2, they know which color is the "odd" one and they know the second wise man wears a hat of that color.
b) The second wise man's hat has one of the "even" colors. The first wise man will not remain silent which tells all the other ones that they are in case 2. The second wise man will see two odd colors; his hat is one of those colors. The first wise man says the other color and the second one then saves himself. Now the remaining 98 wise men know they are in case 2b and as before they know which color is the "odd" one and they know the color of the second wise man's hat.
____________
|
|
Rarensu
Known Hero
Formerly known as RTI
|
|
posted July 25, 2009 10:01 AM |
|
Edited by Rarensu at 10:54, 25 Jul 2009.
|
@ Ecoris: Your solution only works if the First Wise Man is allowed to say nothing. Saying nothing is almost cheating; the game does not make an allowance for this. It could be that Ihor simply forgot to mention the rule pertaining to this option, but my instinct is that this option does not exist.
If a fourth option (silence) does not exist, then it cannot be done with only one wise man. PROOF.
W2 Always sees 2 odds or 0 odds.
If W2 sees 2 odds A & B, there are three possibilities.
1) ABC odd, W2 has C
2) A is odd, W2 has B
3) B is odd, W2 has A
The only way for W2 to know which he has is for W1 to say that color. If W1 says a different color, there are still 2 options and W2 has to guess.
If W2 sees 0 odds, there are three possibilities.
1) A is odd, W2 has A
2) B is odd, W2 has B
3) C is odd, W2 has C
The only way for W2 to know which he has is for W1 to say that color. If W1 says a different color then there are still 2 options and W2 has to guess.
W1 must always say W2's hat and W2 always says his own hat. Therefore, W1 and W2 ALWAYS say the same color. Saying the same color occurs in both distributions (1 odd or all odd). Therefore the other 98 can NEVER know which distribution exists.
@ Ihor: Either Ecoris or I have found the solution, pending whether or not silence is part of the game. Choose.
____________
Sincerely,
A Proponent of Spelling, Grammar, Punctuation, and Courtesy.
|
|
ihor
Supreme Hero
Accidental Hero
|
|
posted July 25, 2009 02:49 PM |
|
|
Quote:
Either Ecoris or I have found the solution, pending whether or not silence is part of the game. Choose.
Before the first reply of FOG I also thought that there are only 3 options and noone couldn't say nothing. In addition to this the first who presented the idea with even/odd numbers was Rarensu. So I think Rarensu presented the right solution.
____________
Your advertisement could be
here only for 100$ per day.
|
|
Rarensu
Known Hero
Formerly known as RTI
|
|
posted July 25, 2009 10:16 PM |
|
Edited by Rarensu at 22:22, 25 Jul 2009.
|
Easy puzzle
There are three boxes, one containing nails, one containing screws, and one containing both nails & screws. But the labels have been switched up; they are all labeled incorrectly!
Can you determine which box is which by pulling a single item out of a single box? No looking inside or shaking or weighing the boxes. You just observe a single item to see if it is a nail or a screw.
Hard puzzle
You're on a game-show. There are three doors. Behind one of them is the grand prize. The other two are empty. You select a door at random. The show host then opens one of the doors that you didn't select and shows you that it is empty (he always chooses an empty door, because he has insider knowledge). Now you have a choice - you can change your selection to the other door that's still closed.
Your friends are all telling you that it doesn't matter, the probability of each door having the grand prize is the same. Are they wrong? Are the probabilities different for the two remaining doors? More importantly - is it a good idea for you to switch?
____________
Sincerely,
A Proponent of Spelling, Grammar, Punctuation, and Courtesy.
|
| |
|
|
This thread is pages long: 
