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

Wizard
Administrator
Wizard
Joined: Oct 14, 2009
  • Threads: 1337
  • Posts: 22076
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.

  1. There are 12 players, 12 boxes, each numbered 1 to 12.
  2. Inside the 12 gift boxes are the numbers 1 to 12, randomly placed, one in each box.
  3. 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.
  4. 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.
  5. If a player does not find his own number, then the entire group is said to fail and the game is over.
  6. If a player survives, then he must place the numbers back in their original boxes for the next player.
  7. Players may not watch other players or communicate once the game begins.
  8. Before beginning, the entire group is allowed to collaborate on a strategy.
  9. 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
It's not whether you win or lose; it's whether or not you had a good bet.
ThatDonGuy
ThatDonGuy
Joined: Jun 22, 2011
  • Threads: 95
  • Posts: 4339
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).
unJon
unJon
Joined: Jul 1, 2018
  • Threads: 13
  • Posts: 1866
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?
The race is not always to the swift, nor the battle to the strong; but that is the way to bet.
Wizard
Administrator
Wizard
Joined: Oct 14, 2009
  • Threads: 1337
  • Posts: 22076
January 10th, 2020 at 5:12:32 PM permalink
Quote: ThatDonGuy

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).



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.
It's not whether you win or lose; it's whether or not you had a good bet.
Wizard
Administrator
Wizard
Joined: Oct 14, 2009
  • Threads: 1337
  • Posts: 22076
January 10th, 2020 at 5:13:43 PM permalink
Quote: unJon

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?



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
It's not whether you win or lose; it's whether or not you had a good bet.
Wizard
Administrator
Wizard
Joined: Oct 14, 2009
  • Threads: 1337
  • Posts: 22076
January 11th, 2020 at 11:11:37 AM permalink
Okay, all may jump in and participate. The beer is still unclaimed.
It's not whether you win or lose; it's whether or not you had a good bet.
djtehch34t
djtehch34t
Joined: May 7, 2016
  • Threads: 2
  • Posts: 42
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...
Wizard
Administrator
Wizard
Joined: Oct 14, 2009
  • Threads: 1337
  • Posts: 22076
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
It's not whether you win or lose; it's whether or not you had a good bet.
jpmurga
jpmurga
Joined: Aug 10, 2014
  • Threads: 5
  • Posts: 25
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
Wizard
Administrator
Wizard
Joined: Oct 14, 2009
  • Threads: 1337
  • Posts: 22076
January 11th, 2020 at 3:26:49 PM permalink
Quote: jpmurga

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



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
It's not whether you win or lose; it's whether or not you had a good bet.

  • Jump to: