superprismatic Posted February 4, 2011 Report Share Posted February 4, 2011 Consider 25 colored envelopes. There are 10 envelopes of one color, 7 envelopes of a different color, 5 envelopes of yet another color, and 3 envelopes of still another color. Each of the envelopes of the rarest color (i.e., the color for which there are precisely 3 envelopes) contain $100. The other envelopes contain nothing. You don't know which number of envelopes is assigned to which of the four colors. Now, these envelopes are randomly shuffled and shown to you one at a time. As you are presented with an envelope you have two choices. You may stop the game at that point, in which case you get to keep the contents (if any) of that envelope. If you decide not to stop the game at that point, the envelope is thrown away without being opened and you are presented with the next envelope. You can only see one envelope at a time, but you may record the colors of the envelopes presented to you. Find a strategy which will give you the best chance of getting $100 from playing this game. I have done a simulation using the following strategy which gets the $100 with probability about .49: Keep a count of how many of each color you have seen so far, including the one you are currently looking at. If the count of the color you are currently seeing is less than or equal to the counts for each of the other colors, take the envelope you are looking at. Otherwise, continue the game. I have found another strategy which wins with probability a bit bigger than .75, according to my simulator. Can you find a better strategy? Of course you'd get a bonus if you could compute the probability of winning without resorting to computer simulation. Quote Link to comment Share on other sites More sharing options...
0 Guest Posted February 4, 2011 Report Share Posted February 4, 2011 Nice puzzle. Thanks. Keep a count of how many envelopes of each color have been offered already. As there are only 3 envelopes of money color in the stack of 25. Other colored envelops will be offered more frequently. and Money colored envelops will show least frequently. Cut off a color one by one when third envelop appears. The color to show third envelop last is the money color. for example if the counts according to the color are as follows c1 6 c2 8 c3 5 c4 2 If at this stage color c4 envelop is shown, it will be the last one of that color (money color) so grab it. To compute the probability ... this strategy will fail if all three envelops are offered before three envelops of other colors. Though I think I can compute the probabilty .. right now I am not finding the elegant writable way. I will work on it. Quote Link to comment Share on other sites More sharing options...
0 Guest Posted February 5, 2011 Report Share Posted February 5, 2011 D. Deo: We don't know ahead of time that there are 3 money envelopes, could only be one or two, maybe 4 or five or more. We only know that there are the fewest of the money envelopes. If you let too many go by then you run the risk of passing by all of them. Superprismatic: Do we know ahead of time that there are only 25 total envelopes? It is best to get a large sampling of the color distribution, but if we wait until too near the end then all the money envelopes may be passed by already. Quote Link to comment Share on other sites More sharing options...
0 superprismatic Posted February 5, 2011 Author Report Share Posted February 5, 2011 D. Deo: We don't know ahead of time that there are 3 money envelopes, could only be one or two, maybe 4 or five or more. We only know that there are the fewest of the money envelopes. If you let too many go by then you run the risk of passing by all of them. Superprismatic: Do we know ahead of time that there are only 25 total envelopes? It is best to get a large sampling of the color distribution, but if we wait until too near the end then all the money envelopes may be passed by already. Yes, we know ahead of time that there are 25 envelopes (10,7,5,3 for each of 4 colors). We also know that there are 3 money envelopes, all the same color -- a different color than any of the other 22 envelopes. Quote Link to comment Share on other sites More sharing options...
0 Guest Posted February 5, 2011 Report Share Posted February 5, 2011 Also agreed, good puzzle! After walking through a previous, more complex solution in my head I think your best odds are just being patient enough to wait it out until you can rule out other colors and are certain of the money color. I'm not great with probabilities but you would basically need: 3 of 10 in one color 3 of 7 in one color 3 of 5 in one color to all show before your final money envelope shows. Now then, why only 3 instead of 4? Because even though you can't completely rule out a color as being the money color with only 3 of those flipped, it's irrelevant because you've already passed on 3 of those and whether it's the money color or not, you've missed your chance at that (sunk cost kind of deal). So i'm not sure how to represent it statistically, but I would say the soonest you'd be ready to open an envelope is on the 10th round (if the previous 9 rounds got 3 of 3 different colors) but from there, you just keep flipping until you do get 3 envelopes of 3 colors and then just take your next envelope from the 4th color. Quote Link to comment Share on other sites More sharing options...
0 superprismatic Posted February 8, 2011 Author Report Share Posted February 8, 2011 Nice puzzle. Thanks. Keep a count of how many envelopes of each color have been offered already. As there are only 3 envelopes of money color in the stack of 25. Other colored envelops will be offered more frequently. and Money colored envelops will show least frequently. Cut off a color one by one when third envelop appears. The color to show third envelop last is the money color. for example if the counts according to the color are as follows c1 6 c2 8 c3 5 c4 2 If at this stage color c4 envelop is shown, it will be the last one of that color (money color) so grab it. To compute the probability ... this strategy will fail if all three envelops are offered before three envelops of other colors. Though I think I can compute the probabilty .. right now I am not finding the elegant writable way. I will work on it. Yes, I believe you are off in the right direction! Quote Link to comment Share on other sites More sharing options...
0 superprismatic Posted February 8, 2011 Author Report Share Posted February 8, 2011 Also agreed, good puzzle! After walking through a previous, more complex solution in my head I think your best odds are just being patient enough to wait it out until you can rule out other colors and are certain of the money color. I'm not great with probabilities but you would basically need: 3 of 10 in one color 3 of 7 in one color 3 of 5 in one color to all show before your final money envelope shows. Now then, why only 3 instead of 4? Because even though you can't completely rule out a color as being the money color with only 3 of those flipped, it's irrelevant because you've already passed on 3 of those and whether it's the money color or not, you've missed your chance at that (sunk cost kind of deal). So i'm not sure how to represent it statistically, but I would say the soonest you'd be ready to open an envelope is on the 10th round (if the previous 9 rounds got 3 of 3 different colors) but from there, you just keep flipping until you do get 3 envelopes of 3 colors and then just take your next envelope from the 4th color. You just need to get this into an implementable strategy and decide if it does better than 75%. Quote Link to comment Share on other sites More sharing options...
0 Guest Posted February 8, 2011 Report Share Posted February 8, 2011 there are 25!/(10!*7!*5!*3!)= 1,177,930,353,600 possible arrangements of envelopes. if we pick the fourth color that shows up 3 times, then as long as the winning color shows up last, second to last, or 3rd to last, we are guaranteed a win. there are 24!/(10!*7!*5!*2!)= 141,351,642,432 ways it can be last, 23!/(10!*7!*4!*2!) +23!/(10!*6!*5!*2!) +23!/(9!*7!*5!*2!) = 129,572,338,896 ways it can be second to last, and 22!/(10!*7!*3!*2!) +22!/(10!*6!*4!*2!) +22!/(9!*7!*4!*2!) +22!/(10!*5!*5!*2!) +22!/(9!*6!*5!*2!) +22!/(8!*7!*5!*2!) = 78,614,047,512 ways it can be 3rd to last. adding those together we have 349,538,028,840/1,177,930,353,600 = roughly a 29.7% chance of winning, using this strategy. Quote Link to comment Share on other sites More sharing options...
0 bushindo Posted February 10, 2011 Report Share Posted February 10, 2011 (edited) Consider 25 colored envelopes. There are 10 envelopes of one color, 7 envelopes of a different color, 5 envelopes of yet another color, and 3 envelopes of still another color. Each of the envelopes of the rarest color (i.e., the color for which there are precisely 3 envelopes) contain $100. The other envelopes contain nothing. You don't know which number of envelopes is assigned to which of the four colors. Now, these envelopes are randomly shuffled and shown to you one at a time. As you are presented with an envelope you have two choices. You may stop the game at that point, in which case you get to keep the contents (if any) of that envelope. If you decide not to stop the game at that point, the envelope is thrown away without being opened and you are presented with the next envelope. You can only see one envelope at a time, but you may record the colors of the envelopes presented to you. Find a strategy which will give you the best chance of getting $100 from playing this game. I have done a simulation using the following strategy which gets the $100 with probability about .49: Keep a count of how many of each color you have seen so far, including the one you are currently looking at. If the count of the color you are currently seeing is less than or equal to the counts for each of the other colors, take the envelope you are looking at. Otherwise, continue the game. I have found another strategy which wins with probability a bit bigger than .75, according to my simulator. Can you find a better strategy? Of course you'd get a bonus if you could compute the probability of winning without resorting to computer simulation. Here's the computation of the winning percentage. It isn't as elegant as I would like, so if there's a better way, I'd love to hear about it. The strategy is to wait and only consider picking an envelope of any color on the third time that it shows up. In the entire game, that option will only present itself 4 times, 1 for each color. A little thought shows that it makes sense to pick the color that is the last to appear in 3 envelopes. Now, the computation of the winning chance. Let's suppose that we label the colors A, B, C, and D, which have the frequency of 10, 7, 5, and 3, respectively. Let the state of the game at any point be (a, b, c, d), where a is the number of color A we have seen so far, b is the number of color B, etc. Given such a state vector, the chance that our strategy wins, P( a, b, c, 3), is where a, b, c >= 3, and N = (a + b + c + 3). In order for our strategy to win, d must be equal to 3, and the N-th envelope to show up must be of color D. Now the task is to enumerate over 120 states where 3 <= a <= 10, 3 <= b <= 7, 3 <= c <= 5, and d = 3, and apply the previous equation to find the probability of winning. We then simply sum up all the probability. The total probability of winning is 0.7867886. I attach below the list of all 120 states and their respective winning probability. Color A Color B Color C Color D N Probability 1 3 3 3 3 12 0.00202 2 3 3 4 3 13 0.00093 3 3 4 3 3 13 0.00186 4 4 3 3 3 13 0.00326 5 3 3 5 3 14 0.00020 6 3 4 4 3 14 0.00101 7 3 5 3 3 14 0.00121 8 4 3 4 3 14 0.00177 9 4 4 3 3 14 0.00353 10 5 3 3 3 14 0.00424 11 3 4 5 3 15 0.00026 12 3 5 4 3 15 0.00077 13 3 6 3 3 15 0.00051 14 4 3 5 3 15 0.00045 15 4 4 4 3 15 0.00225 16 4 5 3 3 15 0.00270 17 5 3 4 3 15 0.00270 18 5 4 3 3 15 0.00540 19 6 3 3 3 15 0.00450 20 3 5 5 3 16 0.00023 21 3 6 4 3 16 0.00039 22 3 7 3 3 16 0.00011 23 4 4 5 3 16 0.00067 24 4 5 4 3 16 0.00202 25 4 6 3 3 16 0.00135 26 5 3 5 3 16 0.00081 27 5 4 4 3 16 0.00405 28 5 5 3 3 16 0.00486 29 6 3 4 3 16 0.00337 30 6 4 3 3 16 0.00675 31 7 3 3 3 16 0.00385 32 3 6 5 3 17 0.00014 33 3 7 4 3 17 0.00010 34 4 5 5 3 17 0.00072 35 4 6 4 3 17 0.00120 36 4 7 3 3 17 0.00034 37 5 4 5 3 17 0.00144 38 5 5 4 3 17 0.00432 39 5 6 3 3 17 0.00288 40 6 3 5 3 17 0.00120 41 6 4 4 3 17 0.00600 42 6 5 3 3 17 0.00720 43 7 3 4 3 17 0.00343 44 7 4 3 3 17 0.00685 45 8 3 3 3 17 0.00257 46 3 7 5 3 18 0.00004 47 4 6 5 3 18 0.00051 48 4 7 4 3 18 0.00036 49 5 5 5 3 18 0.00183 50 5 6 4 3 18 0.00306 51 5 7 3 3 18 0.00087 52 6 4 5 3 18 0.00255 53 6 5 4 3 18 0.00765 54 6 6 3 3 18 0.00510 55 7 3 5 3 18 0.00146 56 7 4 4 3 18 0.00728 57 7 5 3 3 18 0.00874 58 8 3 4 3 18 0.00273 59 8 4 3 3 18 0.00546 60 9 3 3 3 18 0.00121 61 4 7 5 3 19 0.00019 62 5 6 5 3 19 0.00157 63 5 7 4 3 19 0.00112 64 6 5 5 3 19 0.00393 65 6 6 4 3 19 0.00655 66 6 7 3 3 19 0.00187 67 7 4 5 3 19 0.00374 68 7 5 4 3 19 0.01123 69 7 6 3 3 19 0.00749 70 8 3 5 3 19 0.00140 71 8 4 4 3 19 0.00702 72 8 5 3 3 19 0.00843 73 9 3 4 3 19 0.00156 74 9 4 3 3 19 0.00312 75 10 3 3 3 19 0.00031 76 5 7 5 3 20 0.00071 77 6 6 5 3 20 0.00415 78 6 7 4 3 20 0.00296 79 7 5 5 3 20 0.00711 80 7 6 4 3 20 0.01186 81 7 7 3 3 20 0.00339 82 8 4 5 3 20 0.00445 83 8 5 4 3 20 0.01334 84 8 6 3 3 20 0.00889 85 9 3 5 3 20 0.00099 86 9 4 4 3 20 0.00494 87 9 5 3 3 20 0.00593 88 10 3 4 3 20 0.00049 89 10 4 3 3 20 0.00099 90 6 7 5 3 21 0.00237 91 7 6 5 3 21 0.00949 92 7 7 4 3 21 0.00678 93 8 5 5 3 21 0.01067 94 8 6 4 3 21 0.01779 95 8 7 3 3 21 0.00508 96 9 4 5 3 21 0.00395 97 9 5 4 3 21 0.01186 98 9 6 3 3 21 0.00791 99 10 3 5 3 21 0.00040 100 10 4 4 3 21 0.00198 101 10 5 3 3 21 0.00237 102 7 7 5 3 22 0.00711 103 8 6 5 3 22 0.01868 104 8 7 4 3 22 0.01334 105 9 5 5 3 22 0.01245 106 9 6 4 3 22 0.02075 107 9 7 3 3 22 0.00593 108 10 4 5 3 22 0.00208 109 10 5 4 3 22 0.00623 110 10 6 3 3 22 0.00415 111 8 7 5 3 23 0.01957 112 9 6 5 3 23 0.03043 113 9 7 4 3 23 0.02174 114 10 5 5 3 23 0.00913 115 10 6 4 3 23 0.01522 116 10 7 3 3 23 0.00435 117 9 7 5 3 24 0.05000 118 10 6 5 3 24 0.03500 119 10 7 4 3 24 0.02500 120 10 7 5 3 25 0.12000 Edited February 10, 2011 by bushindo Quote Link to comment Share on other sites More sharing options...
0 superprismatic Posted February 10, 2011 Author Report Share Posted February 10, 2011 Here's the computation of the winning percentage. It isn't as elegant as I would like, so if there's a better way, I'd love to hear about it. The strategy is to wait and only consider picking an envelope of any color on the third time that it shows up. In the entire game, that option will only present itself 4 times, 1 for each color. A little thought shows that it makes sense to pick the color that is the last to appear in 3 envelopes. Now, the computation of the winning chance. Let's suppose that we label the colors A, B, C, and D, which have the frequency of 10, 7, 5, and 3, respectively. Let the state of the game at any point be (a, b, c, d), where a is the number of color A we have seen so far, b is the number of color B, etc. Given such a state vector, the chance that our strategy wins, P( a, b, c, 3), is where a, b, c >= 3, and N = (a + b + c + 3). In order for our strategy to win, d must be equal to 3, and the N-th envelope to show up must be of color D. Now the task is to enumerate over 120 states where 3 <= a <= 10, 3 <= b <= 7, 3 <= c <= 5, and d = 3, and apply the previous equation to find the probability of winning. We then simply sum up all the probability. The total probability of winning is 0.7867886. I attach below the list of all 120 states and their respective winning probability. Color A Color B Color C Color D N Probability 1 3 3 3 3 12 0.00202 2 3 3 4 3 13 0.00093 3 3 4 3 3 13 0.00186 4 4 3 3 3 13 0.00326 5 3 3 5 3 14 0.00020 6 3 4 4 3 14 0.00101 7 3 5 3 3 14 0.00121 8 4 3 4 3 14 0.00177 9 4 4 3 3 14 0.00353 10 5 3 3 3 14 0.00424 11 3 4 5 3 15 0.00026 12 3 5 4 3 15 0.00077 13 3 6 3 3 15 0.00051 14 4 3 5 3 15 0.00045 15 4 4 4 3 15 0.00225 16 4 5 3 3 15 0.00270 17 5 3 4 3 15 0.00270 18 5 4 3 3 15 0.00540 19 6 3 3 3 15 0.00450 20 3 5 5 3 16 0.00023 21 3 6 4 3 16 0.00039 22 3 7 3 3 16 0.00011 23 4 4 5 3 16 0.00067 24 4 5 4 3 16 0.00202 25 4 6 3 3 16 0.00135 26 5 3 5 3 16 0.00081 27 5 4 4 3 16 0.00405 28 5 5 3 3 16 0.00486 29 6 3 4 3 16 0.00337 30 6 4 3 3 16 0.00675 31 7 3 3 3 16 0.00385 32 3 6 5 3 17 0.00014 33 3 7 4 3 17 0.00010 34 4 5 5 3 17 0.00072 35 4 6 4 3 17 0.00120 36 4 7 3 3 17 0.00034 37 5 4 5 3 17 0.00144 38 5 5 4 3 17 0.00432 39 5 6 3 3 17 0.00288 40 6 3 5 3 17 0.00120 41 6 4 4 3 17 0.00600 42 6 5 3 3 17 0.00720 43 7 3 4 3 17 0.00343 44 7 4 3 3 17 0.00685 45 8 3 3 3 17 0.00257 46 3 7 5 3 18 0.00004 47 4 6 5 3 18 0.00051 48 4 7 4 3 18 0.00036 49 5 5 5 3 18 0.00183 50 5 6 4 3 18 0.00306 51 5 7 3 3 18 0.00087 52 6 4 5 3 18 0.00255 53 6 5 4 3 18 0.00765 54 6 6 3 3 18 0.00510 55 7 3 5 3 18 0.00146 56 7 4 4 3 18 0.00728 57 7 5 3 3 18 0.00874 58 8 3 4 3 18 0.00273 59 8 4 3 3 18 0.00546 60 9 3 3 3 18 0.00121 61 4 7 5 3 19 0.00019 62 5 6 5 3 19 0.00157 63 5 7 4 3 19 0.00112 64 6 5 5 3 19 0.00393 65 6 6 4 3 19 0.00655 66 6 7 3 3 19 0.00187 67 7 4 5 3 19 0.00374 68 7 5 4 3 19 0.01123 69 7 6 3 3 19 0.00749 70 8 3 5 3 19 0.00140 71 8 4 4 3 19 0.00702 72 8 5 3 3 19 0.00843 73 9 3 4 3 19 0.00156 74 9 4 3 3 19 0.00312 75 10 3 3 3 19 0.00031 76 5 7 5 3 20 0.00071 77 6 6 5 3 20 0.00415 78 6 7 4 3 20 0.00296 79 7 5 5 3 20 0.00711 80 7 6 4 3 20 0.01186 81 7 7 3 3 20 0.00339 82 8 4 5 3 20 0.00445 83 8 5 4 3 20 0.01334 84 8 6 3 3 20 0.00889 85 9 3 5 3 20 0.00099 86 9 4 4 3 20 0.00494 87 9 5 3 3 20 0.00593 88 10 3 4 3 20 0.00049 89 10 4 3 3 20 0.00099 90 6 7 5 3 21 0.00237 91 7 6 5 3 21 0.00949 92 7 7 4 3 21 0.00678 93 8 5 5 3 21 0.01067 94 8 6 4 3 21 0.01779 95 8 7 3 3 21 0.00508 96 9 4 5 3 21 0.00395 97 9 5 4 3 21 0.01186 98 9 6 3 3 21 0.00791 99 10 3 5 3 21 0.00040 100 10 4 4 3 21 0.00198 101 10 5 3 3 21 0.00237 102 7 7 5 3 22 0.00711 103 8 6 5 3 22 0.01868 104 8 7 4 3 22 0.01334 105 9 5 5 3 22 0.01245 106 9 6 4 3 22 0.02075 107 9 7 3 3 22 0.00593 108 10 4 5 3 22 0.00208 109 10 5 4 3 22 0.00623 110 10 6 3 3 22 0.00415 111 8 7 5 3 23 0.01957 112 9 6 5 3 23 0.03043 113 9 7 4 3 23 0.02174 114 10 5 5 3 23 0.00913 115 10 6 4 3 23 0.01522 116 10 7 3 3 23 0.00435 117 9 7 5 3 24 0.05000 118 10 6 5 3 24 0.03500 119 10 7 4 3 24 0.02500 120 10 7 5 3 25 0.12000 Nice work! I hope you enjoyed the problem. You have the same value which I got experimentally with 1,000,000,000 trials. My strategy is equivalent to yours. Here's my strategy: Stop when the count of the color of the envelope you are looking at is the minimum of the counts of all four colors AND the counts of each the other 3 colors are all at least 3. So, it is possible under this strategy to stop when I see a fourth color for the first time. If my strategy says to stop, it really wouldn't hurt to keep going until you see all three of the stopping color (but it wouldn't help either). So, your insistence that d=3 may simply make it easier to calculate the probability of a win. I'm not sure about this as I have not thought it through yet. I'd also like to see a proof of optimality. Quote Link to comment Share on other sites More sharing options...
Question
superprismatic
Consider 25 colored envelopes. There are 10 envelopes of one color,
7 envelopes of a different color, 5 envelopes of yet another color,
and 3 envelopes of still another color. Each of the envelopes of the
rarest color (i.e., the color for which there are precisely 3 envelopes)
contain $100. The other envelopes contain nothing. You don't know
which number of envelopes is assigned to which of the four colors.
Now, these envelopes are randomly shuffled and shown to you one at
a time. As you are presented with an envelope you have two choices.
You may stop the game at that point, in which case you get to keep
the contents (if any) of that envelope. If you decide not to stop
the game at that point, the envelope is thrown away without being
opened and you are presented with the next envelope. You can only
see one envelope at a time, but you may record the colors of the
envelopes presented to you.
Find a strategy which will give you the best chance of getting $100
from playing this game.
I have done a simulation using the following strategy which gets
the $100 with probability about .49:
Keep a count of how many of each color you have seen so far,
including the one you are currently looking at. If the count of
the color you are currently seeing is less than or equal to the
counts for each of the other colors, take the envelope you are
looking at. Otherwise, continue the game.
I have found another strategy which wins with probability a bit bigger
than .75, according to my simulator. Can you find a better strategy?
Of course you'd get a bonus if you could compute the probability
of winning without resorting to computer simulation.
Link to comment
Share on other sites
9 answers to this question
Recommended Posts
Join the conversation
You can post now and register later. If you have an account, sign in now to post with your account.