Secret Santa Problem #2
Thread Rating:
Poll
 | 5 votes (71.42%) | ||
| | 1 vote (14.28%) | ||
| | 2 votes (28.57%) | ||
| | 1 vote (14.28%) | ||
| | 1 vote (14.28%) | ||
| | 2 votes (28.57%) | ||
| | 1 vote (14.28%) | ||
| | 2 votes (28.57%) | ||
| | 1 vote (14.28%) | ||
| | 1 vote (14.28%) |
7 members have voted
January 10th, 2020 at 3:01:39 PM
permalink
In our continued celebration of 2020, the year of math appreciation, I present another Secret Santa problem. If you missed the fun of the last one, here is it.
Here are the rules of the puzzle at hand.
The question is what strategy should they follow and what is the probability of success with that strategy?
For example, if the strategy were to pick six random boxes, then the probability of success would be (1/2)^12. However, there is a better strategy.
Usual rules apply:
1. Beer for the first person with the correct answer and solution.
2. Those who have won a beer in the past year are put on a 24-hour delay.
3. Please just don't plop down a YouTube link that works out the problem. That defeats the point.
Here are the rules of the puzzle at hand.
- There are 12 players, 12 boxes, each numbered 1 to 12.
- Inside the 12 gift boxes are the numbers 1 to 12, randomly placed, one in each box.
- Each player, one at a time, shall be allowed to open six boxes of his choosing. He may choose and open them one at a time.
- Each players goal is to find his own number inside a box, among his six choices. If he does, that person is said to survive.
- If a player does not find his own number, then the entire group is said to fail and the game is over.
- If a player survives, then he must place the numbers back in their original boxes for the next player.
- Players may not watch other players or communicate once the game begins.
- Before beginning, the entire group is allowed to collaborate on a strategy.
- The goal is for all 12 players to survive (in other words find his own number inside a box)
The question is what strategy should they follow and what is the probability of success with that strategy?
For example, if the strategy were to pick six random boxes, then the probability of success would be (1/2)^12. However, there is a better strategy.
Usual rules apply:
1. Beer for the first person with the correct answer and solution.
2. Those who have won a beer in the past year are put on a 24-hour delay.
3. Please just don't plop down a YouTube link that works out the problem. That defeats the point.
Last edited by: Wizard on Jan 10, 2020
"For with much wisdom comes much sorrow." -- Ecclesiastes 1:18 (NIV)
January 10th, 2020 at 4:54:19 PM
permalink
Questions:
Do the players know in advance the order in which they will choose?
I am assuming that the boxes themselves are numbered 1-12 (when you say in rule 1 that the "12 gifts" are numbered 1-12).
Do the players know in advance the order in which they will choose?
I am assuming that the boxes themselves are numbered 1-12 (when you say in rule 1 that the "12 gifts" are numbered 1-12).
January 10th, 2020 at 5:09:18 PM
permalink
If a player opens the bid with his number does he stop even if he has more guesses? Can he choose to keep opening boxes?
Can players watch which boxes the other players open?
Is any other communication allowed between players once the game begins?
Can players watch which boxes the other players open?
Is any other communication allowed between players once the game begins?
The race is not always to the swift, nor the battle to the strong; but that is the way to bet.
January 10th, 2020 at 5:12:32 PM
permalink
Quote: ThatDonGuyQuestions:
Do the players know in advance the order in which they will choose?
I am assuming that the boxes themselves are numbered 1-12 (when you say in rule 1 that the "12 gifts" are numbered 1-12).
The players may choose any order to play they wish.
I should have stuck with the word "boxes" through the entire wording. There are 12 boxes, numbered 1 to 12, like on Deal or No Deal.
"For with much wisdom comes much sorrow." -- Ecclesiastes 1:18 (NIV)
January 10th, 2020 at 5:13:43 PM
permalink
Quote: unJonIf a player opens the bid with his number does he stop even if he has more guesses? Can he choose to keep opening boxes?
It wouldn't help to keep opening more. See next questions.
Quote:Can players watch which boxes the other players open?
No
Quote:Is any other communication allowed between players once the game begins?
No
"For with much wisdom comes much sorrow." -- Ecclesiastes 1:18 (NIV)
January 11th, 2020 at 11:11:37 AM
permalink
Okay, all may jump in and participate. The beer is still unclaimed.
"For with much wisdom comes much sorrow." -- Ecclesiastes 1:18 (NIV)
January 11th, 2020 at 12:54:22 PM
permalink
I'm pretty sure this isn't the optimal solution, but it's the best I could come up with after a few minutes:
Use the following strategy - Have the people picking boxes in odd positions take from boxes 1-6, and have people picking boxes in even positions take from boxes 7-12. Odd pickers will have probability 1/2 of getting the right box. But, we know from conditioning on the fact that the Odd picker survived that the even pickers have a better chance of getting their own box, as one more of the 1-6 boxes was taken out of play than the 7-12 boxes. So, in the 2nd pick, we get chance 6/11 of survival. In the 4th pick, we get chance 5/9, 6th: 4/7, 8th: 3/5, 10th: 2/3, and 11th: 1/1. So, our total probability of survival over all 12 picks (1/2^6)(5/9)(4/7)(3/5)(2/3).
It's possible we can do better by partitioning into something smarter, but I'm not sure. By maximizing the probability of survival on pick 2, we might be limiting the chance of survival overall. Might think about it more later...
January 11th, 2020 at 1:13:37 PM
permalink
Quote: djtehch34t
I'm pretty sure this isn't the optimal solution, but it's the best I could come up with after a few minutes:
Use the following strategy - Have the people picking boxes in odd positions take from boxes 1-6, and have people picking boxes in even positions take from boxes 7-12. Odd pickers will have probability 1/2 of getting the right box. But, we know from conditioning on the fact that the Odd picker survived that the even pickers have a better chance of getting their own box, as one more of the 1-6 boxes was taken out of play than the 7-12 boxes. So, in the 2nd pick, we get chance 6/11 of survival. In the 4th pick, we get chance 5/9, 6th: 4/7, 8th: 3/5, 10th: 2/3, and 11th: 1/1. So, our total probability of survival over all 12 picks (1/2^6)(5/9)(4/7)(3/5)(2/3).
It's possible we can do better by partitioning into something smarter, but I'm not sure. By maximizing the probability of survival on pick 2, we might be limiting the chance of survival overall. Might think about it more later...
I agree that is better than everyone picking randomly. However, I submit there is a much better way. Maybe my way isn't even best. I will say my strategy has about a 35% chance of group survival.
Last edited by: Wizard on Jan 27, 2020
"For with much wisdom comes much sorrow." -- Ecclesiastes 1:18 (NIV)
January 11th, 2020 at 1:47:07 PM
permalink
Not sure if is optimal but I would suggest to make sure every box is chosen the same amount of times
Person 1 chooses 1 through 6
Person 2 chooses 2 through 7
And so forth
Then each box is opened 6 times, at least each person (box) has the same chance of survival
Person 1 chooses 1 through 6
Person 2 chooses 2 through 7
And so forth
Then each box is opened 6 times, at least each person (box) has the same chance of survival
January 11th, 2020 at 3:26:49 PM
permalink
Quote: jpmurgaNot sure if is optimal but I would suggest to make sure every box is chosen the same amount of times
Person 1 chooses 1 through 6
Person 2 chooses 2 through 7
And so forth
Then each box is opened 6 times, at least each person (box) has the same chance of survival
That may be in improvement, but there is a much better strategy. I will put in spoiler tags the probability of success under my strategy.
34.6789%
Last edited by: Wizard on Jan 27, 2020
"For with much wisdom comes much sorrow." -- Ecclesiastes 1:18 (NIV)
January 12th, 2020 at 7:49:20 AM
permalink
OK. I think I got something better. I started by experimenting with a smaller case, N = 4 people who select 2 boxes each. It seemed like no matter the order you pick the boxes, that I couldn't get better than 1/6, (IE, choose 1/2 and then 3/4, 1/2 then 3/4, or choose 1/2 twice, and then 3/4 twice). Then, I realized that we could use the information that each person sees to influence their choices. For example, if the first person checks box 1, and sees number M, they check box M next. More generally, person i should check box i first and then check the number that they opened. If they see their own number, then they are done. In the N = 4 case, person 2 will check box 2. If it's 2, they are done. If it's 1, then they check box 1, which we know has a 2 in it since person 1 survived, so they checked box 2 after seeing a 2 in box 1. Extending this strategy to all 4 players gives us a chance of survival of 10/24.
Then, I realized that this can be reformulated. Since we are checking the boxes that we saw, we are really looking at the permutation generated by the box labels. Then, we succeed if and only if this permutation has cycle lengths of at most N/2, as it means we can reach back to position i in at most N/2 box picks. In the N = 4 case, this corresponds to the 10 Permutations that have cycle length at most 2 (listed in appendix). At this point, I cheated a little, and found the number of permutations with this property on OEIS (N! - the sequence found at https://oeis.org/A201546) as I was not in the mood to derive it from scratch. For N = 12, this is equal to 12! - 312888960. So, we can calculate the probability of our strategy succeeding for N = 12 as (12! - 312888960)/12! = 9613/27720 ~= 34.7%. According to WolframAlpha, for N->Infinity, this will converge to 1-log(2).
Appendix:
Permutations for N = 4 with cycle length <= 2:
(1)(2)(3)(4)
(12)(34)
(12)(3)(4)
(1)(2)(34)
(13)(24)
(13)(2)(4)
(1)(3)(24)
(14)(23)
(14)(2)(3)
(1)(4)(23)
Edit: Props to my fiancee for helping solve the N = 4 case.
Last edited by: djtehch34t on Jan 12, 2020
January 12th, 2020 at 3:56:33 PM
permalink
I had an idea and then a little play using 6 cards.
edit I didn't realise when initially posting this but the number I get agrees with the previous post, so I'm really happy (except for the long winded way I had to do it!)
It's all based on loops. Assume that players start at their own number and just follow the number in the box until they either find their own number or lose. If your box number is lower than yours then you know that following your loop will find your number - that is because the earlier player must have come through your box to find theirs and they started at their box to get to yours - so you must be on a loop of size six or less.
Lemma : The largest loop is 6 or less then all players will win.
Lemma : If #1 is on a loop of size six then all players will win.
Lemma : If six players are on loops of 6 or less, then the other six players must be as well.
Lemma A : Probability of each loop size is the same.
Pr of loop size 1 = 1/12 * 11/11 * 10/10 *1/1
Pr of loop size 2 = 11/12 * 1/11 * 10/10 *1/1
Pr of loop size 3 = 11/12 * 10/11 * 1/10 *1/1
The numerators will have 11 thru 1 for having to miss the current number plus a 1 when you hit.
The denominators are 12 thru 11.
So say player #1 has a loop of size 5, then assume lowest number player not on that loop is #2 (etc.)
#2 needs to be on a loop of 1-6 to win, lose on 7.
Probabiity of this is 6/7 and 1/7.
Then by brute force, I worked through all the ways of winning and losing.
Lemma : The largest loop is 6 or less then all players will win.
Lemma : If #1 is on a loop of size six then all players will win.
Lemma : If six players are on loops of 6 or less, then the other six players must be as well.
Lemma A : Probability of each loop size is the same.
Pr of loop size 1 = 1/12 * 11/11 * 10/10 *1/1
Pr of loop size 2 = 11/12 * 1/11 * 10/10 *1/1
Pr of loop size 3 = 11/12 * 10/11 * 1/10 *1/1
The numerators will have 11 thru 1 for having to miss the current number plus a 1 when you hit.
The denominators are 12 thru 11.
So say player #1 has a loop of size 5, then assume lowest number player not on that loop is #2 (etc.)
#2 needs to be on a loop of 1-6 to win, lose on 7.
Probabiity of this is 6/7 and 1/7.
Then by brute force, I worked through all the ways of winning and losing.
| Loops | Result | Pr | .346 789 321 789 | .653 210 678 211 |
| 12 | LOSE | 1/12 | .083 333 333 333 | |
| 11 | LOSE | 1/12 | .083 333 333 333 | |
| 10 | LOSE | 1/12 | .083 333 333 333 | |
| 9 | LOSE | 1/12 | .083 333 333 333 | |
| 8 | LOSE | 1/12 | .083 333 333 333 | |
| 7 | LOSE | 1/12 | .083 333 333 333 | |
| 6 | WIN | 1/12 | .083 333 333 333 | |
| 5 1-6 | WIN | 1/12 6/7 | .071 428 571 429 | |
| 5 7 | LOSE | 1/12 1/7 | .011 904 761 905 | |
| 4 1 1-6 | WIN | 1/12 1/8 6/7 | .008 928 571 429 | |
| 4 1 7 | LOSE | 1/12 1/8 1/7 | .001 488 095 238 | |
| 4 2-6 | WIN | 1/12 5/8 | .052 083 333 333 | |
| 4 7-8 | LOSE | 1/12 2/8 | .020 833 333 333 | |
| 3 1 1 1-6 | WIN | 1/12 1/9 1/8 6/7 | .000 992 063 492 | |
| 3 1 1 7 | WIN | 1/12 1/9 1/8 1/7 | .000 165 343 915 | |
| 3 1 2-6 | WIN | 1/12 1/9 5/8 | .005 787 037 037 | |
| 3 1 7-8 | LOSE | 1/12 1/9 2/8 | .002 314 814 815 | |
| 3 2 1-6 | WIN | 1/12 1/9 6/7 | .007 936 507 937 | |
| 3 2 7 | LOSE | 1/12 1/9 1/7 | .001 322 751 323 | |
| 3 3-6 | WIN | 1/12 4/9 | .037 037 037 037 | |
| 3 7-9 | LOSE | 1/12 3/9 | .027 777 777 778 | |
| 2 1 1 1 1-6 | WIN | 1/12 1/10 1/9 1/8 6/7 | .000 099 206 349 | |
| 2 1 1 1 7 | LOSE | 1/12 1/10 1/9 1/8 1/7 | .000 016 534 392 | |
| 2 1 1 2-6 | WIN | 1/12 1/10 1/9 5/8 | .000 578 703 704 | |
| 2 1 1 7-8 | LOSE | 1/12 1/10 1/9 2/8 | .000 231 481 481 | |
| 2 1 2 1-6 | WIN | 1/12 1/10 1/9 6/7 | .000 793 650 794 | |
| 2 1 2 7 | LOSE | 1/12 1/10 1/9 1/7 | .000 132 275 132 | |
| 2 1 3-6 | WIN | 1/12 1/10 4/9 | .003 703 703 704 | |
| 2 1 7-9 | LOSE | 1/12 1/10 3/9 | .002 777 777 778 | |
| 2 2 1 1-6 | WIN | 1/12 1/10 1/8 6/7 | .000 892 857 143 | |
| 2 2 1 7 | LOSE | 1/12 1/10 1/8 1/7 | .000 148 809 524 | |
| 2 2 2-6 | WIN | 1/12 1/10 5/8 | .005 208 333 333 | |
| 2 2 7-8 | LOSE | 1/12 1/10 2/8 | .002 083 333 333 | |
| 2 3 1-6 | WIN | 1/12 1/10 6/7 | .007 142 857 143 | |
| 2 3 7 | LOSE | 1/12 1/10 1/7 | .001 190 476 190 | |
| 2 4-6 | WIN | 1/12 3/10 | .025 000 000 000 | |
| 2 7-10 | LOSE | 1/12 4/10 | .033 333 333 333 | |
| 1 1 1 1 1 1-6 | WIN | 1/132 1/10 1/9 1/8 6/7 | .000 009 018 759 | |
| 1 1 1 1 1 7 | LOSE | 1/132 1/10 1/9 1/8 1/7 | .000 001 503 127 | |
| 1 1 1 1 2-6 | WIN | 1/132 1/10 1/9 5/8 | .000 052 609 428 | |
| 1 1 1 1 7-8 | LOSE | 1/132 1/10 1/9 2/8 | .000 021 043 771 | |
| 1 1 1 2 1-6 | WIN | 1/132 1/10 1/9 6/7 | .000 072 150 072 | |
| 1 1 1 2 7 | LOSE | 1/132 1/10 1/9 1/7 | .000 012 025 012 | |
| 1 1 1 3-6 | WIN | 1/132 1/10 4/9 | .000 336 700 337 | |
| 1 1 1 7-9 | LOSE | 1/132 1/10 3/9 | .000 252 525 253 | |
| 1 1 2 1 1-6 | WIN | 1/132 1/10 1/8 6/7 | .000 081 168 831 | |
| 1 1 2 1 7 | LOSE | 1/132 1/10 1/8 1/7 | .000 013 528 139 | |
| 1 1 2 2-6 | WIN | 1/132 1/10 5/8 | .000 473 484 848 | |
| 1 1 2 7-8 | LOSE | 1/132 1/10 2/8 | .000 189 393 939 | |
| 1 1 3 1-6 | WIN | 1/132 1/10 6/7 | .000 649 350 649 | |
| 1 1 3 7 | LOSE | 1/132 1/10 1/7 | .000 108 225 108 | |
| 1 1 4-6 | WIN | 1/132 3/10 | .002 272 727 273 | |
| 1 1 7-10 | LOSE | 1/132 4/10 | .003 030 303 030 | |
| 1 2 1 1 1-6 | WIN | 1/12 1/11 1/9 1/8 6/7 | .000 090 187 590 | |
| 1 2 1 1 7 | LOSE | 1/12 1/11 1/9 1/8 1/7 | .000 015 031 265 | |
| 1 2 1 2-6 | WIN | 1/12 1/11 1/9 5/8 | .000 526 094 276 | |
| 1 2 1 7-8 | LOSE | 1/12 1/11 1/9 2/8 | .000 210 437 710 | |
| 1 2 2 1-6 | WIN | 1/12 1/11 1/9 6/7 | .000 721 500 722 | |
| 1 2 2 7 | LOSE | 1/12 1/11 1/9 1/7 | .000 120 250 120 | |
| 1 2 3-6 | WIN | 1/12 1/11 4/9 | .003 367 003 367 | |
| 1 2 7-9 | LOSE | 1/12 1/11 3/9 | .002 525 252 525 | |
| 1 3 1 1-6 | WIN | 1/12 1/11 1/8 6/7 | .000 811 688 312 | |
| 1 3 1 7 | WIN | 1/12 1/11 1/8 1/7 | .000 135 281 385 | |
| 1 3 2-6 | WIN | 1/12 1/11 5/8 | .004 734 848 485 | |
| 1 3 7-8 | LOSE | 1/12 1/11 2/8 | .001 893 939 394 | |
| 1 4 1-6 | WIN | 1/12 1/11 6/7 | .006 493 506 494 | |
| 1 4 7 | LOSE | 1/12 1/11 1/7 | .001 082 251 082 | |
| 1 5-6 | WIN | 1/12 2/11 | .015 151 515 152 | |
| 1 7-11 | LOSE | 1/12 5/11 | .037 878 787 879 |
edit I didn't realise when initially posting this but the number I get agrees with the previous post, so I'm really happy (except for the long winded way I had to do it!)
January 12th, 2020 at 8:31:13 PM
permalink
This is a really elegant problem and solution. I was banging my head against this trying to get the ideal strategy. I even started coding a brute force simulation to get the best strategy (then quickly gave up).
But a key mistake I made was selecting all 6 boxes at once, instead of one at a time.
Funnily enough, even if I ran the simulation with players pre-selecting the 6 boxes to pick over all the possibilities, which would take too long, it would miss this solution since it uses information from previous picks to inform the next pick.
I would be curious to know the solution for the variant of this problem if the players have to pre-select the 6 boxes they are going to pick.
Based on my calculations, each player has 924 ways to pick 6 boxes out of 12. So there are 924^12 = 4*10^35 distinct ways to play.
Running each against the 12! number of box configurations to get a success rate for each would take forever, and still miss the mark!
Funnily enough, even if I ran the simulation with players pre-selecting the 6 boxes to pick over all the possibilities, which would take too long, it would miss this solution since it uses information from previous picks to inform the next pick.
I would be curious to know the solution for the variant of this problem if the players have to pre-select the 6 boxes they are going to pick.
Based on my calculations, each player has 924 ways to pick 6 boxes out of 12. So there are 924^12 = 4*10^35 distinct ways to play.
Running each against the 12! number of box configurations to get a success rate for each would take forever, and still miss the mark!
January 12th, 2020 at 8:50:09 PM
permalink
I agree with your basic logic.
However, let's look at the probability of a loop of 11 and one of 1.
There are 12 possibilities for the loop of 1.
Then pick any arbitrary person in the other 11. There are 10 people he can loop with (everyone but himself). With the next person there are 9 people he can link to, With the next person, there are 8 left. And so on.
Thus, shouldn't the number of combination for one loop of 11 and one of 1 bet 12*fact(10). Shouldn't the probability of that be 12*fact(10)/fact(12) = fact(10)/fact(11) = 1/11.
You have 1/12.
However, let's look at the probability of a loop of 11 and one of 1.
There are 12 possibilities for the loop of 1.
Then pick any arbitrary person in the other 11. There are 10 people he can loop with (everyone but himself). With the next person there are 9 people he can link to, With the next person, there are 8 left. And so on.
Thus, shouldn't the number of combination for one loop of 11 and one of 1 bet 12*fact(10). Shouldn't the probability of that be 12*fact(10)/fact(12) = fact(10)/fact(11) = 1/11.
You have 1/12.
"For with much wisdom comes much sorrow." -- Ecclesiastes 1:18 (NIV)
January 12th, 2020 at 9:19:10 PM
permalink
With two correct answers out there, I think we can discuss this without spoiler tags.
First, I admit my probability was off. It was for getting only 5 picks per player, not 6. Even then, it was still probably off.
So the two correct answers are those of djtehch34t and Charlie. In the previous post I challenged Charlie's probability of a loop of 11 and 1, but he still gets the right bottom line.
The following table shows my combinations for each set of loops, where the longest is 7 or more.
The following table shows the summary.
While djtehch34 had some online help (wives are allowed), I think Charlie has quite a few beers coming his way. I don't remember about djtehch34t. If it's okay with Charlie, I'd like to award the prize to djtehch34t.
First, I admit my probability was off. It was for getting only 5 picks per player, not 6. Even then, it was still probably off.
So the two correct answers are those of djtehch34t and Charlie. In the previous post I challenged Charlie's probability of a loop of 11 and 1, but he still gets the right bottom line.
The following table shows my combinations for each set of loops, where the longest is 7 or more.
| Pattern | combinations | Probability |
|---|---|---|
| 12 | 39,916,800 | 0.083333 |
| 11,1 | 43,545,600 | 0.090909 |
| 10,2 | 23,950,080 | 0.050000 |
| 10,1,1 | 23,950,080 | 0.050000 |
| 9,3 | 17,740,800 | 0.037037 |
| 9,2,1 | 26,611,200 | 0.055556 |
| 9,1,1,1 | 8,870,400 | 0.018519 |
| 8,4 | 14,968,800 | 0.031250 |
| 8,3,1 | 19,958,400 | 0.041667 |
| 8,2,2 | 7,484,400 | 0.015625 |
| 8,2,1,1 | 14,968,800 | 0.031250 |
| 8,1,1,1,1 | 2,494,800 | 0.005208 |
| 7,5 | 13,685,760 | 0.028571 |
| 7,4,1 | 17,107,200 | 0.035714 |
| 7,3,2 | 11,404,800 | 0.023810 |
| 7,3,1,1 | 11,404,800 | 0.023810 |
| 7,2,2,1 | 8,553,600 | 0.017857 |
| 7,2,1,1,1 | 5,702,400 | 0.011905 |
| 7,1,1,1,1,1 | 570,240 | 0.001190 |
| Total | 483,264,000 | 0.653211 |
The following table shows the summary.
| event | combinations | probability |
|---|---|---|
| death | 312,888,960 | 0.653211 |
| survival | 166,112,640 | 0.346789 |
While djtehch34 had some online help (wives are allowed), I think Charlie has quite a few beers coming his way. I don't remember about djtehch34t. If it's okay with Charlie, I'd like to award the prize to djtehch34t.
"For with much wisdom comes much sorrow." -- Ecclesiastes 1:18 (NIV)
January 13th, 2020 at 3:04:34 AM
permalink
There's actually a much more elegant solution (especially if you're happy to have a figure rather than a formula) using recursion based on how many people are left to be considered. For instance if you have six or fewer left then you must win. If you have seven left then they only fail if in a loop of 7. If you have eight then win if in a loop of 2-6, lose if in a loop of 7-8, and if in a loop of 1, look at scenario 7. ... If you have twelve then win in a loop of 6, lose if in a loop of 7-12, and if in a loop of 1-5 look at scenarios 7 thru 11.
P win with 7 left = 6 / 7.
P win with 8 left = 5 / 8 + 1 / 8 * P(7)
P win with 9 left = 4 / 9 + 1 / 9 * ( (P(7)+P(8) )
etc.
Put that in a spreadhseet and it gets the same answer.
Now someone smart may be able to detect a pattern and simplify the formulae.
My way there are two ways to get loops of {11 1}.
The first is when #1 is in a loop of 11: Pr = 1/12.
The second is when #1 is in a loop of 1, and then #2 is in a loop of 11: Pr = 1/12 * 1/11.
1/12 + 1/12*1/11 = 1/12*11/11+1/12*1/11 = 1/12*12/11 = 1/11.
P win with 7 left = 6 / 7.
P win with 8 left = 5 / 8 + 1 / 8 * P(7)
P win with 9 left = 4 / 9 + 1 / 9 * ( (P(7)+P(8) )
etc.
Put that in a spreadhseet and it gets the same answer.
Now someone smart may be able to detect a pattern and simplify the formulae.
| 7 | 6/7 | .857 142 857 | .857 142 857 | |
| 8 | 5/8 | .625 000 000 | P(8)+1/8*P(7) | .732 142 857 |
| 9 | 4/9 | .444 444 444 | P(9)+1/9*[P(7)+P(8)] | .621 031 746 |
| 10 | 3/10 | .300 000 000 | .521 031 746 | |
| 11 | 2/11 | .181 818 182 | .430 122 655 | |
| 12 | 1/12 | .083 333 333 | .346 789 322 |
Quote: wizardI agree with your basic logic....However, let's look at the probability of a loop of 11 and one of 1...[as I get] 1/11.
My way there are two ways to get loops of {11 1}.
The first is when #1 is in a loop of 11: Pr = 1/12.
The second is when #1 is in a loop of 1, and then #2 is in a loop of 11: Pr = 1/12 * 1/11.
1/12 + 1/12*1/11 = 1/12*11/11+1/12*1/11 = 1/12*12/11 = 1/11.
January 13th, 2020 at 3:36:24 AM
permalink
Quote: charliepatrick
P win with 8 left = 5 / 8 + 1 / 8 * P(7)
I am not fully digesting this. Where does the 5/8 come from?
"For with much wisdom comes much sorrow." -- Ecclesiastes 1:18 (NIV)
January 13th, 2020 at 4:03:03 AM
permalink
Looking at eight people then consider how big a loop #1 is.
#1 can be in a loop of size 1, 2, 3, 4, 5, 6, 7 or 8 - each with Pr = 1/8.
[7 8] If #1 is in a loop of 7 or 8 then it's a LOSE.
[2 3 4 5 6] If #1 is in a loop of 2 to 6, then the biggest loop possible is now known to be 6 (as there is a maximum of six left once the ones in #1 loop are discounted), so it's WIN. There are five (2 3 4 5 6) chances out of the original eight so the probability is 5/8.
[1] If #1 is in a loop of 1, then there are now seven people left to think about. The probability of this scenario is 1/8 and the probability of the seven winning = Pr (win when starting with seven) "P(7)".
Thus the probability of winning with eight people = 5/8 + 1/8 * 6/7 = (35+6)/56 = 41/56.
You then continue the process working from nine up to twelve, finishing with
[7 8 ... 12] LOSE (pr=6/12)
[6] WIN (pr=1/12)
[1...5] look at P(7) thru P(11), each being pr(WIN)=1/12 * P(N)
#1 can be in a loop of size 1, 2, 3, 4, 5, 6, 7 or 8 - each with Pr = 1/8.
[7 8] If #1 is in a loop of 7 or 8 then it's a LOSE.
[2 3 4 5 6] If #1 is in a loop of 2 to 6, then the biggest loop possible is now known to be 6 (as there is a maximum of six left once the ones in #1 loop are discounted), so it's WIN. There are five (2 3 4 5 6) chances out of the original eight so the probability is 5/8.
[1] If #1 is in a loop of 1, then there are now seven people left to think about. The probability of this scenario is 1/8 and the probability of the seven winning = Pr (win when starting with seven) "P(7)".
Thus the probability of winning with eight people = 5/8 + 1/8 * 6/7 = (35+6)/56 = 41/56.
You then continue the process working from nine up to twelve, finishing with
[7 8 ... 12] LOSE (pr=6/12)
[6] WIN (pr=1/12)
[1...5] look at P(7) thru P(11), each being pr(WIN)=1/12 * P(N)
Last edited by: charliepatrick on Jan 13, 2020
January 13th, 2020 at 7:47:30 AM
permalink
I have just seen this and have not read any of the previously posted answers.
Each player will be entering the room and looking in some number of boxes. I assume that each player can change the spatial location of boxes and rotate the boxes.
The best strategy would be for the first player in the room to arrange all the boxes in a clockwise arrangement as follows:
-Half the unopened boxes are placed in a stack or cluster at the center of the clock.
-The other half of the boxes are stacked or cluster at a place above the 12 o'clock position and further from the entrance than the boxes at the center. This, along with the central stack, unambigously marks the 6:00/12:00 axis on the clock.
-Each box that is opened is placed at a clock position corresponding to the number that was found inside and rotated such that they are aligned radially and pointing toward the center.
Each subsequent player either opens the box at their clock position so as to successfully find their number (if a box is already at their clock position) or proceeds to open up previously unopened boxes and places them at their correct clock position so as to identify their contents.
It would be helpful to create a convention to designate the 12:00 position unambiguously as all of the boxes are opened -such as standing the box on end (if it is not a cube) or by placing the box at 12 o'clock at somewhat further radial distance.
If the first person is allowed to open 6 boxes even if he has already found his number, then the groups chance of success is 50% by using this strategy.
If the rule is that you must stop opening boxes after you have found the box that matches your number, then the strategy should be that each player that arrives to find that the number that they are seeking already has a box on its corresponding clock position (and thus is known), should proceed to open up 5 unopened boxes and place them on the clock before opening up his correct box.
Each player will be entering the room and looking in some number of boxes. I assume that each player can change the spatial location of boxes and rotate the boxes.
The best strategy would be for the first player in the room to arrange all the boxes in a clockwise arrangement as follows:
-Half the unopened boxes are placed in a stack or cluster at the center of the clock.
-The other half of the boxes are stacked or cluster at a place above the 12 o'clock position and further from the entrance than the boxes at the center. This, along with the central stack, unambigously marks the 6:00/12:00 axis on the clock.
-Each box that is opened is placed at a clock position corresponding to the number that was found inside and rotated such that they are aligned radially and pointing toward the center.
Each subsequent player either opens the box at their clock position so as to successfully find their number (if a box is already at their clock position) or proceeds to open up previously unopened boxes and places them at their correct clock position so as to identify their contents.
It would be helpful to create a convention to designate the 12:00 position unambiguously as all of the boxes are opened -such as standing the box on end (if it is not a cube) or by placing the box at 12 o'clock at somewhat further radial distance.
If the first person is allowed to open 6 boxes even if he has already found his number, then the groups chance of success is 50% by using this strategy.
If the rule is that you must stop opening boxes after you have found the box that matches your number, then the strategy should be that each player that arrives to find that the number that they are seeking already has a box on its corresponding clock position (and thus is known), should proceed to open up 5 unopened boxes and place them on the clock before opening up his correct box.
So many better men, a few of them friends, are dead. And a thousand thousand slimy things live on, and so do I.
January 13th, 2020 at 8:44:48 AM
permalink
According to the wizard I've come up with the answer so can't say too much but the puzzle was that the boxes had to be left in exactly the same state as you found them.
Thus earlier players cannot "leave" information for later players except that when it's their turn they know all previous player(s) will have managed to find their numbers (as they're all still in a chance of winning). Note it is not a puzzle where a given strategy will always work, even adopting the best strategy there is some chance the players cannot win.
I found it useful to compare it to playing cards (assumed they're numbered 1-12) and deal them in a row face down. Each player can turn over upto six cards, one at a time, look at each and turn them back over - leaving them in the same order but no clue left which ones you looked at.
In the puzzle the boxes are (say in a row) numbered 1 thru 12. Inside, placed randomly, are the numbers 1 thru 12. Each player, in turn, goes into the room and sees the row of boxes. They choose a box, open the door, look inside, see the number and close the door. They can repeat this for upto six boxes. If they find a box with their own number then they "WIN". If they don't then the entire group loses. Every player has to find their number for the group to win.
As a helpful hint I found the puzzle very interesting as there were two bits of thinking needed.
1) Come up with an an idea that might work.
I'm not sure whether there's a logical approach that can be used as that's not how I solved it. I admit I came up/stumbled over with some ideas (without knowing one was the same one that someone else had posted). It seemed like a plan and also gave a better chance than wizard's first number. However I still don't know for sure if it's the minimum answer.
2) Calculate the chances (percentage) the players can win.
The second challenge is, having found a secnario, trying to determine a method to work out the chances of success. After I posted my first answer "a penny dropped" which gave me the same answer but much quicker to work out the percent chance.
Thus earlier players cannot "leave" information for later players except that when it's their turn they know all previous player(s) will have managed to find their numbers (as they're all still in a chance of winning). Note it is not a puzzle where a given strategy will always work, even adopting the best strategy there is some chance the players cannot win.
I found it useful to compare it to playing cards (assumed they're numbered 1-12) and deal them in a row face down. Each player can turn over upto six cards, one at a time, look at each and turn them back over - leaving them in the same order but no clue left which ones you looked at.
In the puzzle the boxes are (say in a row) numbered 1 thru 12. Inside, placed randomly, are the numbers 1 thru 12. Each player, in turn, goes into the room and sees the row of boxes. They choose a box, open the door, look inside, see the number and close the door. They can repeat this for upto six boxes. If they find a box with their own number then they "WIN". If they don't then the entire group loses. Every player has to find their number for the group to win.
As a helpful hint I found the puzzle very interesting as there were two bits of thinking needed.
1) Come up with an an idea that might work.
I'm not sure whether there's a logical approach that can be used as that's not how I solved it. I admit I came up/stumbled over with some ideas (without knowing one was the same one that someone else had posted). It seemed like a plan and also gave a better chance than wizard's first number. However I still don't know for sure if it's the minimum answer.
2) Calculate the chances (percentage) the players can win.
The second challenge is, having found a secnario, trying to determine a method to work out the chances of success. After I posted my first answer "a penny dropped" which gave me the same answer but much quicker to work out the percent chance.
January 13th, 2020 at 9:10:22 AM
permalink
Quote: charliepatrick#1 can be in a loop of size 1, 2, 3, 4, 5, 6, 7 or 8 - each with Pr = 1/8.
I did not realize this. Let me convince myself why it's true (not asking you to).
"For with much wisdom comes much sorrow." -- Ecclesiastes 1:18 (NIV)
January 13th, 2020 at 9:33:30 AM
permalink
Quote: charliepatrick...Lemma A : Probability of each loop size is the same.
Pr of loop size 1 = 1/12 * 11/11 * 10/10 *1/1
Pr of loop size 2 = 11/12 * 1/11 * 10/10 *1/1
Pr of loop size 3 = 11/12 * 10/11 * 1/10 *1/1
The numerators will have 11 thru 1 for having to miss the current number plus a 1 when you hit.
The denominators are 12 thru 11....
The length of the loop that person #1 is in.
Size 1 : 1 is in box 1, others doesn't matter. P = 1/12.
Size 2 : (i) X is in box1 (ii) 1 is in box X. Pr(i) = 11/12; Pr (ii) = 1/11 (as X can't be in box X because we've already seen it, so there are 11 possibilities left). P = 11/12 * 1/11 = 1/12.
Size N : (i) not 1 in box 1 (ii) other boxes keep missing #1 (iii) Nth box contains a "1". Pr(i) = 11/12; Pr(ii) other probabilities are 10/11 9/10 etc. so the product of those are N/12 as all the 11s 10s cancel each other out. Pr (iii) = 1/N (as by then there's N unseen numbers). so P = N/12 * 1/N = 1/12.
So all the probabilities are 1/12 and hence equal.
January 13th, 2020 at 9:45:39 AM
permalink
Quote: charliepatrickAccording to the wizard I've come up with the answer so can't say too much but the puzzle was that the boxes had to be left in exactly the same state as you found them.
Okay. Kinda disappointed that the puzzle statement lacked that information.
I have been offline since Friday afternoon, got online this morning (Monday), read the first post and answered without looking at the rest of the thread. That's why my post was such a non sequitur.
So many better men, a few of them friends, are dead. And a thousand thousand slimy things live on, and so do I.
January 13th, 2020 at 10:27:15 AM
permalink
If you use this method for larger N, like 10,000 boxes, the answer seems to converge to 0.307 = 1 - Ln (2)Quote: charliepatrick
7 6/7 .857 142 857 .857 142 857 8 5/8 .625 000 000 P(8)+1/8*P(7) .732 142 857 9 4/9 .444 444 444 P(9)+1/9*[P(7)+P(8)] .621 031 746 10 3/10 .300 000 000 .521 031 746 11 2/11 .181 818 182 .430 122 655 12 1/12 .083 333 333 .346 789 322
Last edited by: Ace2 on Jan 13, 2020
Its all about making that GTA
January 13th, 2020 at 7:09:43 PM
permalink
Quote: Ace2If you use this method for larger N, like 10,000 boxes, the answer seems to converge to 0.307 = 1 - Ln (2)
Very interesting. Funny how e comes up in so many probability questions.
"For with much wisdom comes much sorrow." -- Ecclesiastes 1:18 (NIV)
January 13th, 2020 at 9:02:13 PM
permalink
Any takers on what the solution is for the slight variant where players have to pick 6 boxes at once, instead of picking one at a time and using information from the current box to inform next pick
January 13th, 2020 at 9:33:55 PM
permalink
Quote: tyler498Any takers on what the solution is for the slight variant where players have to pick 6 boxes at once, instead of picking one at a time and using information from the current box to inform next pick
I'm intrigued. Offhand, I think every box should get picked the same number of times. I will try to give it more thought.
"For with much wisdom comes much sorrow." -- Ecclesiastes 1:18 (NIV)
January 14th, 2020 at 1:27:14 AM
permalink
My gut feeling is player #1 picks (say) boxes 1-6. Player #2 knows that there are 5 chances of being in 1-6 (as one of them contains #1) and 6 of being in 7-12, so should pick the second half. Player #3 has no information so might as well pick boxes 1-6 again. Similarly odd numbered players have no useful information and even numbered players have some. Pr(win) = ( 1/2 * 5/11 ) ^ 6.Quote: tyler498Any takers on what the solution is for the slight variant where players have to pick 6 boxes at once...
[edit] : obviously I shouldn't do too much thinking before my first cup of coffee so didn't see the better answer given later in the thread.
Last edited by: charliepatrick on Jan 14, 2020
January 14th, 2020 at 6:02:30 AM
permalink
Quote: charliepatrickMy gut feeling is player #1 picks (say) boxes 1-6. Player #2 knows that there are 5 chances of being in 1-6 (as one of them contains #1) and 6 of being in 7-12, so should pick the second half. Player #3 has no information so might as well pick boxes 1-6 again. Similarly odd numbered players have no useful information and even numbered players have some. Pr(win) = ( 1/2 * 5/11 ) ^ 6.
This is the same strategy as my first post. You actually do better on the even picks. Consider the last pick for instance. You are guaranteed success as all 6 of the 1-6 picks are correct. So you get (1/2)^6(6/11)(5/9)(4/7)(3/5)(2/3) = 1/924.
Another strategy is to pick the 1-6 on the first 6 picks. We get (1/2)(5/11)(4/10)(3/9)(2/8)(1/7) and guaranteed success on the last 6 picks. This again comes to 1/924.
Based on these being equal (and getting 1/6 for every fixed n = 4 case), I had conjectured than in general, any fixed strategy that picks every box an equal number of times will give the same probability of success. Based on the above calculations, this would generalize to ((n/2)!)^2/n!. I haven't thought about how to prove that though.
January 14th, 2020 at 8:08:44 AM
permalink
I now see Charlie's solution, although I might visualize it a little differently.
I can see the probability of failure with 6 boxes and 12 people is (1/2)+(1/2)*(5/7 + 4/8 + 3/9 + 2/10 + 1/11)
I think the general case of p people where p is even and everyone may open half the boxes the probability of failure is (1/2) + (1/p)*sum(n=1 to (p/2)-1) of n/(p-n))
I can see the probability of failure with 6 boxes and 12 people is (1/2)+(1/2)*(5/7 + 4/8 + 3/9 + 2/10 + 1/11)
I think the general case of p people where p is even and everyone may open half the boxes the probability of failure is (1/2) + (1/p)*sum(n=1 to (p/2)-1) of n/(p-n))
"For with much wisdom comes much sorrow." -- Ecclesiastes 1:18 (NIV)
January 14th, 2020 at 9:13:06 AM
permalink
Quote: djtehch34tThis is the same strategy as my first post. You actually do better on the even picks. Consider the last pick for instance. You are guaranteed success as all 6 of the 1-6 picks are correct. So you get (1/2)^6(6/11)(5/9)(4/7)(3/5)(2/3) = 1/924.
Another strategy is to pick the 1-6 on the first 6 picks. We get (1/2)(5/11)(4/10)(3/9)(2/8)(1/7) and guaranteed success on the last 6 picks. This again comes to 1/924.
Based on these being equal (and getting 1/6 for every fixed n = 4 case), I had conjectured than in general, any fixed strategy that picks every box an equal number of times will give the same probability of success. Based on the above calculations, this would generalize to ((n/2)!)^2/n!. I haven't thought about how to prove that though.
1/924 is also the best I got by trying few different strategies.
924 surprisingly is also the number of ways to pick 6 boxes out of 12.. 12!/(6!* (12!-6!))
Funny coincidence
January 14th, 2020 at 10:01:27 AM
permalink
I can now see that if the first six agree on which six boxes they'll open, once they've won the other six must win (by picking the other six). Thus it's just the chance of the boxes 1 thru 6 being in positions 1 thru 6, which is the same as picking six random boxes and picking 1 thru 6 (in any order). This is one combination of the combinations of picking 6 boxes from 12.Quote: tyler4981/924 is also the best I got by trying few different strategies.
924 surprisingly is also the number of ways to pick 6 boxes out of 12.. 12!/(6!* (12!-6!))
Funny coincidence
January 15th, 2020 at 8:26:08 PM
permalink
Responding before spoiling it by reading the thread...
Player 1 checks boxes 1-6.
If he survives, then we know the 1 is in the first half, so player 2 must check exactly boxes 7-12 to maximize his probability of finding the 2.
Assuming player 2 survives, we know there's a 1 in the first half and a 2 in the second half, so player 3 is indifferent about which half to check. He checks the first half.
Assuming player 3 survives, we know there's a 1 & 3 in the first half and a 2 in the second half, so player 4 must check the second half to maximize his probability of finding the 4. Then Player 5 is indifferent so he checks the first half. And so on.
Let P(Sn) be the probability of player n surviving
P(S1) = 6/12
P(S2|S1) = 6/11
P(S3|S2) = 5/10
P(S4|S3) = 5/9
P(S5|S4) = 4/8
P(S6|S5) = 4/7
P(S7|S6) = 3/6
P(S8|S7) = 3/5
P(S9|S8) = 2/4
P(S10|S8) = 2/3
P(S11|S10) = 1/2
P(S12|S11) = 1
The probability of overall success is P(S12) which is given by P(S1) *P(S2|S1) * P(S3|S2) * ... * P(S12|S11) = 6!*6!/12! = 0.00108225108 which is a 343% improvement over random box selection.
January 15th, 2020 at 9:40:51 PM
permalink
My first attempt was embarrasingly suboptimal because I didn't consider using the information inside the boxes. Then I read the cycle strategy posted by others, and it made sense, so I decided to do a brute force simulation of it and got 0.346 chance of success. 1 million iterations in python runs in about 10 seconds.
from random import shuffle
n = 12
reps = 1000000
successes = 0
for rep in range(reps):
perm = list(range(n))
shuffle(perm)
playersuccess = False
for player in range(n):
boxtocheck = player
playersuccess = False
for attempt in range(int(n/2)):
if perm[boxtocheck] == player:
playersuccess = True
break
else:
boxtocheck = perm[boxtocheck]
if not playersuccess:
break
if(playersuccess): #12th player succeeded
successes += 1
print(float(successes)/reps)
January 17th, 2020 at 5:24:25 AM
permalink
Slight adjustment. The formula is actually:
Ln ((N/2 + 1/2) / (N + 1/2)) + 1
In this case we have Ln(6.5 / 12.5) + 1 = 0.3461
Which is within 0.0007 of the exact answer of 0.3468
Initially I thought the adjustment would be the Euler-Mascheroni constant of 0.577 (and maybe it is) but 0.5 brought my trials even closer to the expectations. The adjustment is negligible as N gets large since the result gets extremely close to Ln (2) + 1.
Ln ((N/2 + 1/2) / (N + 1/2)) + 1
In this case we have Ln(6.5 / 12.5) + 1 = 0.3461
Which is within 0.0007 of the exact answer of 0.3468
Initially I thought the adjustment would be the Euler-Mascheroni constant of 0.577 (and maybe it is) but 0.5 brought my trials even closer to the expectations. The adjustment is negligible as N gets large since the result gets extremely close to Ln (2) + 1.
Last edited by: Ace2 on Jan 17, 2020
Its all about making that GTA
