Monster Dice

Ricky · 2007-12-21 13:45:15

This is a game my company played today at our annual Christmas party. The rules to the game are fairly uninteresting, however, here is a math problem which occurred naturally which is not.

We have 7 players and a pair of dice. When the dice are rolled, we choose 3 numbers from 1 to 7. So for example, I could say that if I rolled a 4, I choose 1, 4, and 6. Now this naturally leads to a function:

We want to find such a function so that every integer modulo 7 appears exactly the same number of times.

Have at it. Remember, the idea is also to generalize this into n players, k sided dice, and selecting m numbers.

JaneFairfax · 2007-12-21 14:35:56

How can you roll a 1 with a pair of dice?

Ricky · 2007-12-21 14:48:48

Good point. I worded the question improperly.

Try it now... Note the creation of a new variable: we have L dice which are k sided. And just a hint to all of you, go one variable at a time. Find if there are or aren't solutions to the problem I posed (without the generalization), then generalize it for n players. We can then move on from there. Don't try to take every variable into account at once, that would be very difficult.

Computing them by brute force to give us an answer is a good start, but having logic and noticing patterns is always better.

Ricky · 2007-12-21 15:25:41

Ok, for consistency, here are the variable names:

k: k-sided dice.
L (or lowercase l, hard to tell that from a 1): number of dice
p: number of players
c: number of players to choose.

An additional requirement that I implied but did not say explicitly was that those chosen had to be unique. For example, (2, 2, 5) is not in the range of the function.

Proof that (k, L, p, c) with (6, 2, 7, 3) does not exist:

We note that we are mapping 36 possible combinations to 3-tuples. So we have 108 numbers (not unique). For every integer modulo 7 to appear an equal amount of times, it must appear exactly 108/7 times, which is not an integer.

This immediately generalizes into the first theorem:

Ricky · 2007-12-21 15:47:58

After wording the question that way, it has become apparent to me that this is simply a Balanced Incomplete Block Design problem. If anyone wants an introduction to those, let me know.

luca-deltodesco · 2007-12-21 22:19:27

i would like an introduction since i have no idea what you were talking about there, havnt done any modulo maths before or anything to do with tuples etc

Ricky · 2007-12-22 05:16:58

Sure you have. Have you ever plotted points on a graph like (2, 1)? Thats a 2-tuple. You just never knew the official name for it, that's all. Likewise, a k-tuple just has k entries.

So here is the problem. As I said before, we are mapping a domain of size k * l (number of dice times number of faces on each die) to c-tuples which are integers modulo p. In my (k=6, l=2, p=7, c=3) example, this is:

noting that elements with repeats are not in the range, such as (4, 3, 3).

Now put this on hold and consider this problem, which is much easier to visualize. We have 6 baseball teams playing in a league. We want each baseball team to play each other 1 time. We need to come up a schedule for them. So:

(1, 2)
(1, 3)
(1, 4)
(1, 5)
(1, 6)
(2, 3)
(2, 4)
(2, 5)
(2, 6)
(3, 4)
(3, 5)
(3, 6)
(4, 5)
(4, 6)
(5, 6)

That was pretty easy. However, now we are testing cars for their gasoline usage. We are testing with 8 different types of gasoline, driving the car for 30,000 miles with each type of gasoline. Problem is, we can only start the test when the car is at 10,000 miles, and we can't test anymore past 100,000 because the car my affect our results. Also, it could be that one gasoline puts wear on the car engine where others don't. So in addition, we want for every gasoline we test, to have it used in the same car as every other gasoline. So the tuples would look like:

(a, b, c)
(a, d, e)
(a, f, b)
(b, d, e)
(c, d, f)
(c, e, f)

Which was by no means trivial. These problems generalize into what is called block designs. Each tuple is referred to as a block. The number of blocks is labeled with the variable b. The length of the blocks is k. The number of vertices in the problem is v. The number of times a single vertex appears is r (repeats). And each vertex appears with every other vertex exactly the same number of times, we call this number lambda. If a lambda exists, we call it a (b, v, r, k, lambda) design, if lambda doesn't, then it is a (b, v, r, k) design.

So for our first example, we have a (15, 6, 5, 2, 1) design. Our second example was a (6, 6, 3, 3) design. Note that lambda doesn't exist in the 2nd example because a is paired with b twice (in the 1st and 3rd block), while a is paired with c only once (1st block).

Going back to our original problem, we see that we want each number to occur the same number of times in the blocks. However, we don't have the restriction that each number must be paired will all others at least once. So it is a generalization of a BIBD. Thus, whenever we have a BIBD, we have a solution to the proposed problem. However, more solutions exist to our problem then do those to the BIBD problem.

Math Is Fun Forum

#1 2007-12-21 13:45:15

Monster Dice

#2 2007-12-21 14:35:56

Re: Monster Dice

#3 2007-12-21 14:48:48

Re: Monster Dice

#4 2007-12-21 15:25:41

Re: Monster Dice

#5 2007-12-21 15:47:58

Re: Monster Dice

#6 2007-12-21 22:19:27

Re: Monster Dice

#7 2007-12-22 05:16:58

Re: Monster Dice

Board footer