Problem Description
Today's program was prompted by this recent feedback email to DFF:
My local bar has a game. 5 dice in a cup. You have
to roll 5 Two's in two shakes and you
can "farm". i.e. Roll the first time, save any two's, pick up the remaining
dice and roll
them. What are the odds that five two's will be rolled this way? The
bet is $2 and the pot is
currently over $2,800.00
Just curious. Thanks.
Background & Techniques
This was just the right size problem to provide a week's worth of
entertainment figuring out how to solve and in writing the code.
I ended up with 3 different approaches which all give the same answer, so
there's some degree of confidence in the results. Here's a summary:
Method 1: A mathematical representation of the
problem. We'll assume two rolls; the first of all 5 dice and a second
roll of those which did not show a "2" on the first. I defined a a
function P(M,N) to evaluate the probability that a roll of N
dice with produce M "2"s. More about defining P later.
Since the two rolls are independent, the probability of winning a game
can be represented as the product of the two individual probabilities.
If we roll A twos on the first roll, the probability of winning that
game is P(A,5) x P(5-A,5-A). The total probability of
winning is the sum of the probabilities for all possible A's (0
through 5). The probability seemed surprisingly high to me,
about 1 in 375 games.
Method 2: It took a night's worth of insomnia to come
up a way to check the results from Method 1. I reformulated the
problem as a series of individual rolls. A version of the game which
should produce the same results as the original has us roll each die two
times and score it as a success if either roll (or both rolls) for each die
shows a two. Using the definition of probability (successful outcomes
divided by total possible outcomes), we have 36 possible outcomes ( [1,1]
though [6,6]), of which 11 are successful outcomes (6 outcomes for the
first roll when the 2nd roll is a two plus 6 outcomes for 2nd roll when the
1st roll is a two minus the [2,2] outcome which would otherwise be counted
twice). So each die has a 11/36 or 0.30555 chance of success and the
chance that all 5 dice scored a "2" is the product of the 5 individual
probabilities = (0.30555) 5 = 0.002663. This
agrees with the result from Method 1.
Method 3: The implementation of Method 2 in the program is
slightly different than described above. Since P(M,N) returns
the probability of M twos in N rolls, I used P(1,2) +
P(2,2) as the probability that the two rolls of a die produces 1 or 2
twos. Because I like simulations, I decided to simulate a
million games at a time and see how the result compared . The answer
is "quite well" as you be able to see from the program (.0026x typically
after 1 million games and .0266x after 30 to 50 million games).
The P(M,N) probability function: The probability that
exactly M twos occur when N dice are rolled depends on
occurrence of M twos (each having a 1/6 probability) and N-M
non-twos (each with a 5/6 probability). The product of these two
probabilities describes a particular arrangement of the outcomes, for
example M twos followed by the (N-M) non-twos if the dice were
numbered or a single die was rolled N times. Specifically
Q=(1/6)M x (5/6)(N-M). This probability applies to all
other arrangements as well which means that we must multiply Q by the
number of ways that the M twos could be placed in the N
locations. That is the number of ways that M items can be selected
from N things or the number of combinations for N things taken M
at a time. Mathematicians like to denote this as C(N,M). (Or
more "standardly" as C(n,k) and read as "n choose k").
So our definition of P(M,N) is P(M.N) = (1/6)M x
(5/6)(N-M) x C(N,M).
Non-programmers are welcome to read on, but may
want to skip to the bottom of this page to download
executable version of the program.
Notes for programmers
All of the code is fairly straightforward implementation of what is
described above. A TPageControl with Tabsheets is used
to display the original problem and each of the result types.
The "Combination count" function required to calculate P(M,N) was
initially implemented using our TComboset class from the UComboV2
unit in the DFF Library which is fast and reliable. To eliminate the
need to download the library file for first time users, I wrote a
simple C(N,M) function to compute the definition of combinations: C(N,M)=N!/((N-M)!*M!).
There is no error checking, but it works fine for small integers with valid
inputs.
There were a few "tricks" used here that I'll mention in case you haven't
run across them before: