Friday, November 26, 2004

Loaded Dice

With a single honest die, your an equal chance of rolling a number equivalent to the number of sides of the die. That is, with a standard six-sided die, you have equal chances of getting a 1, 2, 3, 4, 5, or 6. We can represent this dice as an ordered list of numbers, each number representing the relative probability of each side appearing.

An honest six-sided die could therefore be represented as [1,1,1,1,1,1]; the first number represents the relative probability of a “one” turning up; the second number represents the relative probability of a “two” turning up; and so on and so forth.

The game becomes a little more interesting if you combine two or more honest dice. Some numbers have more combinations, and therefore appear more often. Throw two six-sided honest die together, and the best number to bet on is a seven which gives you get a 1-in-6 chance. This is because there are 6 combinations which lead to a seven -- (1,6) (2,5) (3,4) (4,3) (5,2) (6,1) -- out of a total of 36 combinations, or 16.7%.

When you throw three six-sided die together, the best numbers to bet on are either 10 or 11. This is because there are 27 combinations which sum up to each number. This gives you a 12.5% chance of landing 10, and another 12.5% chance of landing an 11.

However, for cheating gamblers, these odds aren’t nearly good enough. This is why they use loaded dice. Loaded dice look like regular dice, except that they are weighted inside so as to favor some numbers more than others. For example, we could have a die where the “three” side is four times as likely to come up as any of the other sides.

Following our notation above, this relative probabilities of the loaded die could be represented as [1,1,4,1,1,1].

If you throw two loaded dice -- [1,1,4,1,1,1] and [1,1,1,4,1,1] -- the best number to bet on would still be a seven but the odds will have changed significantly in your favor. You would now get 21-in-81 chances of landing a seven, or 25.93%.

Remember that not all dice have six sides. Some dice have four sides, some have eight, some have 12, some have 20, and some have even funnier shapes.

If you were given a number of varying shapes of dice, some honest, some loaded, but each one consecutively numbered from one to whatever number of sides each had, what would be the best combination (or combinations) to bet on, and what is its probability?


INPUT
The input file consists of several test cases. Each test case starts with n (4 <= n <= 20), the number of dice for that test case. This is followed by n lines containing the probability list for each die.

Probabilities are indicated as a series of numbers separated by a single space, with each number representing the relative probability of one side of the die. The relative probability number is an integer between 1 and 200, inclusive.

OUTPUT
For each case, print out a header indicating the number of the test. On the next line, print out the most probable sum given the set of loaded dice. In case of a tie, print out the list of sums in ascending order, separating numbers with a space. Lastly, print the absolute probability of such an occurrence, accurate to 3 decimal places, rounding off if necessary. Print any trailing zeroes.

5 comments:

  1. This is an interesting problem. Was this asked in the competition? How long do the students have to solve this?

    I guess the key here is how fast can you write a program that generates all possible dice throws (i.e. the cross product).

    ReplyDelete
  2. I love probability problems.

    For some odd reason, though, I hate programming problems that involve probability.

    *Sigh*

    ReplyDelete
  3. Hiya, guys! Thanks for the comments. Well, Roy, the solution is actually much simpler. If you do it the brute-force way, it's gonna take forever.

    The answer is actually the summation of the products of the probabilities of combinations adding up to the number. Easier to write as a formula, but I can't do that now, so I hope you get the gist.

    I'll post the solution in Python. Only consisted of a few lines, actually.

    ReplyDelete
  4. I don't understand. You do have to generate all possible combinations of the dice throws, right?

    I mean, if there are n dice and each has corresponding number of sides {s1, s2, s3 ... sn}, then you need to compute s1 * s2 * s3 ... sn probability values, right? Is there a way to not need to compute some of these?

    ReplyDelete
  5. No, you don't need to generate all the combinations of the dice throws. You only need to look at the probabilities (or, in my case, the relative probabilities -- I don't know if there's a better term) of each side of the dice.

    Generating the combinations also works, but it's very inefficient. Check the Python code in another section of the blog.

    My actual description of the solution is slightly graphical in nature, so I'm going to need a table napkin and a scanner....

    ReplyDelete