One of the things that is both wonderful and difficult about being the stay-at-home-in-the-morning father of an 18 month-old baby is the kind of "thinking time" you get.
Here's what I mean: hanging out with Zoe isn't like brain surgery. There are no complicated problems to figure out, no serious problems to solve. All of that comes later, I think. For now, we say, "look!" to each other a lot, and roll around on the floor laughing, and carry toys from one room to the next. There's a lot of space in my brain for thinking during these times, though when she's awake, I try to be present as much as possible. Every day is new and wondrous.
But when she goes down for her nap, I have to spring into action. Dishes need to be washed, the animals need food, I have to grab a shower, lunches need to be packed, etc. Again, none of this is like doing calculus, or solving a complicated strategic problem. It's all busy work that just has to get done NOW.
So I tend to play games with myself while I'm doing the dishes or picking up toys. I make up problems—usually ones that grow out of some kind of day-to-day experience I'm having, but not always—and I try to solve them. Anyone who knows me knows that I'm that kind of geek.
The one I did most recently kept me up into the night and required some work in a spreadsheet program, but I solved it. For the pleasure of geeks everywhere, I present it to you now:
The Scenario
You are buying groceries one evening with your family. While checking out, sirens and lights go off everywhere and balloons drop out of the ceiling. The manager of the store comes running out to you and says, "you may have won 1 million dollars!"
Excited?
He brings you over to the customer service counter, where they've set up a green felt gaming board. You see a stack of red dice on the board.
Here's what the manager tells you:
We're going to roll these dice once to see if you've actually won 1 million dollars. Here's the deal: you decide whether you want to roll 1, 2, 3, 4, 5, 6, or 7 dice. When you've decided on the number of dice to roll, I'm going to grab the same number of dice for myself.
We'll roll our dice at the same time, we'll count up all of the numbers from each of the dice, and whoever has the higher number wins.
But to make it a bit more interesting, and because you are a valued customer, I'm going to give you a tiny advantage: I'll give you a win if we tie.
Go ahead and grab the number of dice you want to roll, and let's see if you walk out of this store a millionaire! Remember, you can choose to roll 1, 2, 3, 4, 5, 6 or 7 dice.
The Question
Here's what I want to know from you: What number of dice gives you the highest probability of winning?
All seven possibilities are better than 50%, simply because a tie goes to you, as the attacker. But I want to know how much better than 50% each of the seven possibilities is.
Everyone will have an intuitive answer, but that's not what I want. Give me the intuition, but I also want to know what the percentage chance is to win for each of the seven scenarios. I'll need to see your work, too. Tell me how you got there.
The Spoils
I don't expect a lot of people to play this game, but post the right answer in the comments first, and you could win something geeky. Maybe a t-shirt, probably a gadget. You'll have to play to find out. But you have to be a complete dork (like me) to want to solve this problem at all, so I know that it doesn't matter what you win. Getting the right answer will be the best reward of all.
The answer is 3, 5, or 7.
With three die there are 27 combination possibilities for both 10 and 11(being the total number of all die added together), thus giving you TWO chances to tie on a number (instead of one which is true of 2, 4, and 6).
With five die there are 780 combination possibilities for both the numbers 17 and 18.
With seven die there are 24,017 combination possibilities for 24 and 25.
All things being equal (you both rolling the same number of dice) it may seem that it doesn't really matter which of these you choose.
However, if we are talking probabilities, then choose three die. With probabilities and dice there is an equal percentage of the top and bottom of numbers to roll. Take craps for instance, if you are rolling 2 die, there is actually a greater number of chances to roll 7, equal chances to roll 6 and 8, and then 5 and 9, 4 and 10, 3 and 11, and 2 and 12 (snake eyes and box cars), respectively. Hence the odds being paid out with these numbers being equal on the craps table.
So with 1, 2, 4, and 6 die you only have ONE median number. With 3, 5, and 7 you have two median numbers. And a tie goes to you so you have more of a chance to win.
With 3 dice, 24% (rough average) of the time you have the probability of rolling these middle numbers (percentages combined). With 5 dice your percentages drop to 20% (rough again) and with 7 dice your percentages are 17% (again, very rough). All 'bookmarking' dice have an equal up and down (a 2 for every 12, a 2 for every 11, etc).
So I say go for the ones that have the highest probability of a tie. And the best on for that is 3.
I would have to say that the best chance you have of winning is going to be if you choose to only roll 1 die. Here's how it works in my mind.
The more die that you roll the more chance that you have of rolling combinations of high and low numbers thereby giving your total a more mid-line result.
With the tie going to you, and there only being 6 possible outcomes, you have a greater chance of victory. Even with 2 dice, there is a spread from 2-12 allowing for more possible defeats.
My "logic" may be off but my intuition leads me to the result I've come up with and even if it wasn't right, in my mind I was and when I go to sleep at night it is my mind I have to listen to.
I never planned on thinking this much right before bed... funny how that happens...
Actually, Ryan is correct. The best option is only 1 die.
Jeremy told me that he expected an "elegant formula" to calculate his little problem. So, here it is:
Weibull Model: y=a-b*exp(-c*x^d)
Coefficient Data:
a = 0.66358619
b = 0.1590585
c = 0.6836542
d = -1.1793267
The percent chances of winning are as follows:
1 Die 58.3%
2 Dice 54.6%
3 Dice 53.2%
4 Dice 52.4%
5 Dice 52.0%
6 Dice 51.7%
7 Dice 51.5%
Lloyd, I'm so glad to see a formula, but those aren't the same results I got. Let's compare our work and see if we can find some agreement.
Anne-Marie pointed me to your post on Facebook.
I wrote a program that randomly plays this game a million times for each number of dice. Here are the outcomes:
1 58.3%
2 55.6%
3 54.6%
4 54.1%
5 53.6%
6 53.3%
7 53.0%
8 52.9%
9 52.8%
10 52.6%
I won't write a closed-form solution for these probabilities, but I think I can prove that rolling once gives you the best chance of getting a tie and therefore winning.
Suppose you've already rolled N times and your opponent has rolled N times. At this point, the chance that you have a tie is P(N). If you choose to roll again, is P(N+1) bigger than P(N)? If so, then you should roll again. If not, then you should quit rolling.
If you're already at a tie, the chances that you'll still be tied after one more roll is 16.6% (6/36). If you're not at a tie, the chances that you'll be tied after the next roll is at most 13.8% (5/36), but probably worse. So, this is an upper bound on P(N+1):
P(N+1) <= P(N) * 0.1666 + (1-P(N)) * 0.1388
We know that P(1) = 0.1666. These upper bounds form an infinite sequence where P(N+1) is always less than P(N), so rolling once is your best choice.
Here's some more data (I wrote another program)
1 die: 6 ties, 36 unique rolls, 16.6% ties
2 dice: 146 ties, 1296 unique rolls, 11.3% ties
3 dice: 4332 ties, 46656 unique rolls, 9.3% ties
4 dice: 135954 ties, 1679616 unique rolls, 8.1% ties
5 dice: 4395456 ties, 60466176 unique rolls, 7.3% ties
Trevor, your numbers are spot on (and they should be with a million random permutations), but I'm hoping for a closed-form solution. Too hard? Impossible?
Okay. I think I've gotten it finally.
I have a recursive formula; it's not as clean as a closed-form, but it's a start. Furthermore, it will allow us with certainty to (a) prove the sequence is monotone decreasing [although this has been demonstrated with some rigor above] and (b) derive a specific probability for n dice.
Our tactic here will have several steps. First, we will present a recursive formula to calculate the number of possible kth sums for n dice from k = (1,...,nk) for any n. Next, we will employ these sums to come up with the probability of ties. Finally, we will relate ties to the overall chance of winning and losing.
Let n be the number of dice rolled, and k[n] be the value of any given sum for n dice. The recursive formula is that the k[n] = k-6[n-1] + k-5[n-1] + k-4[n-1] + k-3[n-1] + k-2[n-1] + k-1[n-1] for (k-i) > 0. If (k-i)
Next, we take the sum of (k[n+1])^2 from k = 1 to nk. Denote this sum by x. Then, x/6^(2n) is the probability of occurrence of any tie.
Since we're interested not in ties but total successes, we need only plug x into the following formula to find the probability, y, of winning:
y = [({6^2n-x}/2)+x]/6^(2n)
A proof of this would be too long and complicated, and I've already spent a lot of time on this problem. However, submitted for your approval is the generated probability of n=8 dice for a six sided dice: 0.528909273
It should also be noted that this formula can easily be generalized to a multivariate function f(m,n) where m is the number of sides of the dice, and n is the number of dice.
Here is a copy of the spreadsheet that finally led me to this conclusion: http://dl.dropbox.com/u/276652/Solved.xlsx
Please note that the third paragraph should read:
The recursive formula is k[n] = k-6[n-1] + k-5[n-1] + k-4[n-1] + k-3[n-1] + k-2[n-1] + k-1[n-1] for (k-i) > 0. If (k-i) &le 0, then define (k-i) as 0.