Dicey Permutations

[superprismatic]

If we have any 4-tuple of distinct real

numbers, there is a simple way to have

this determine a permutation on 4 things:

Just replace each number with its ranking

amongst the 4 numbers. For example,

suppose I had the 4-tuple, (36,95,1,18).

By replacing each number with its rank,

I get the permutation (2,1,4,3).

I would like to be able to use 4 fair

dice to generate a permutation in this

way. The dice would give me the 4-tuple

(each die would have its own spot in the

tuple) and I would use the ranks to

determine a permutation. Of course, In

order to insure that I get 4 distinct

numbers, no die can have a number which

is on any other die. But it may be the

case that a paricular die has two or more

faces having the same value. The number

of faces on the dice may be any positive

integer (I'm assuming that fair dice can

always be made this way). It is not

necessary that all of the dice have the

same number of faces.

Can you construct a set of 4 dice which

can produce all 24 permutations of 4

things, each with probability 1/24 ?

I have several such sets with 12 faces

on each die. Can you find a set with

fewer total faces?

[CaptainEd]

What an interesting puzzle! Unfortunately, I don't see how to make incremental progress on it.

One of the dice has the lowest value. Call that value "1" and that die "A".

One of the dice has the highest value. Call that value "w" (for omega) and that die "Z".

Does "1" appear on more than 1/4 of A's faces? No, else it would receive more than 1/4 of permutations in first position.

Does "1" appear on exactly 1/4 of A's faces? Does "w" appear on exactly 1/4 of Z's faces?

Not both, else the other two dice could not be lowest or highest often enough (details can be provided....). I'm guessing, on the basis of symmetry, that if it isn't both, it's neither. This could be fallacious...

So "1" appears on less than 1/4 of A's faces and "w" appears on less than 1/4 of Z's faces.

This implies that at least one of A's other (ie. non-"1") faces is sometimes lowest and at least one of Z's other (ie non-"w") faces is sometimes highest. Big deal...

[phil1882]

d1 2 5 11 16

d2 1 7 12 14

d3 4 6 9 15

d4 3 8 10 13

[CaptainEd]

It will be lowest when d1 = 2 and d2 <> 1 (1/4 * 3/4 = 3/16) or when d1 = 5 and d2 > 1 and d3 > 4 and d4 > 3 (1/4 * 3/4 * 3/4 * 3/4 = 27/128. Total is already greater than .25, and I haven't considered the lower probability case of d1 = 11.

[superprismatic]

d1 2 5 11 16

d2 1 7 12 14

d3 4 6 9 15

d4 3 8 10 13

No, that can't work because there are 24 permutations of 4 things and your dice can produce 256 different results, but 256 results can't be split evenly amongst 24 permutations. Some permutations would have to get more dice results than others.

[EventHorizon]

You do not need to allow a die to have more than one of the same number. You can just increase the value of all faces above it by one to make room for the other.

Also, the relative ordering is all that matters. This means you can simply use the numbers 1 to N, where N is the sum of the number of faces on the dice.

This means that an isomorphic problem would be to find a string of the digits 1 to D, with repititions and where D was the amount of dice in the first problem, with the property if you (uniformly) randomly pick one of each digit and discard the rest, you'll end up with a (uniformly) randomly picked permutation. The length of the string would be N, the sum of the number of faces of the dice from the first problem. An example would be 01101001 is equivalent to two dice with values {1,4,6,7} and {2,3,5,8}.

One thing to notice about these problems is that if you ignore a die (equivalently, all of a given digit in the second problem), you will still be picking uniformly random.

This can lead to insights in the four dice case such as:

1. At least 3 of the dice need an even number of faces.

2. At least 2 of the dice need a number of faces that is a multiple of 3.

3. The product of the number of faces must be a multiple of 72. (The number of permutations of 4 objects (=4!=24) times the extra 3 from (2))

I'm not sure if one of the dice need a number of faces that is a multiple of 4 or not. With prime numbers it is simpler (need at least D+1-p dice with faces that are a multiple of p, where p is any prime number and D is the number of dice)

The fewest total faces is 12. It requires a coin (2 faces), a 4-sided die, and a 6-sided die.

The faces, using the string of digits notation, can be one of the following three (ignoring swapping numbers):

012001100210

012010010210

012100001210

I'm fairly certain the fewest number of faces is greater than 18.

I wrote some code to try and find the fewest, but it ran really slow. I have had a few extra thoughts on optimizations, which should speed things up. It requires a rewrite though.

I thought of limiting the search to palindromes, as the fewest faces for 2 and 3 dice were palindromes. I'll try not to do this unless the code is still far too slow.

[superprismatic]

You do not need to allow a die to have more than one of the same number. You can just increase the value of all faces above it by one to make room for the other.

Also, the relative ordering is all that matters. This means you can simply use the numbers 1 to N, where N is the sum of the number of faces on the dice.

This means that an isomorphic problem would be to find a string of the digits 1 to D, with repititions and where D was the amount of dice in the first problem, with the property if you (uniformly) randomly pick one of each digit and discard the rest, you'll end up with a (uniformly) randomly picked permutation. The length of the string would be N, the sum of the number of faces of the dice from the first problem. An example would be 01101001 is equivalent to two dice with values {1,4,6,7} and {2,3,5,8}.

One thing to notice about these problems is that if you ignore a die (equivalently, all of a given digit in the second problem), you will still be picking uniformly random.

This can lead to insights in the four dice case such as:

1. At least 3 of the dice need an even number of faces.

2. At least 2 of the dice need a number of faces that is a multiple of 3.

3. The product of the number of faces must be a multiple of 72. (The number of permutations of 4 objects (=4!=24) times the extra 3 from (2))

I'm not sure if one of the dice need a number of faces that is a multiple of 4 or not. With prime numbers it is simpler (need at least D+1-p dice with faces that are a multiple of p, where p is any prime number and D is the number of dice)

The fewest total faces is 12. It requires a coin (2 faces), a 4-sided die, and a 6-sided die.

The faces, using the string of digits notation, can be one of the following three (ignoring swapping numbers):

012001100210

012010010210

012100001210

I'm fairly certain the fewest number of faces is greater than 18.

I wrote some code to try and find the fewest, but it ran really slow. I have had a few extra thoughts on optimizations, which should speed things up. It requires a rewrite though.

I thought of limiting the search to palindromes, as the fewest faces for 2 and 3 dice were palindromes. I'll try not to do this unless the code is still far too slow.

Nice solution for 3 dice! I hope you can beat my 4 dice solution of 48 faces. I suspect a solution with fewer than 48 faces exists, but I haven't found one.

[EventHorizon]

So, after reading your post and looking at the fewest for 3 again. I thought of one configuration to try. Since testing a configuration with my code is fast, I threw it into my code and...

Dice needed are 4-sided, 6-sided, 8-sided, and 12-sided. So 30 total faces.

301210000121033330121000012103

I simply noticed how the best configuration for 3 has two of the best configurations for 2 in it (121), and extrapolated the same way.

I'll still work on code to try and find a shorter one.

Also, will test if I can get a solution with 5 dice the same way...

(Edit: It doesn't work for 5 dice. Which makes sense due to needing one die with a number of faces that is a multiple of 5.)

[superprismatic]

So, after reading your post and looking at the fewest for 3 again. I thought of one configuration to try. Since testing a configuration with my code is fast, I threw it into my code and...

Dice needed are 4-sided, 6-sided, 8-sided, and 12-sided. So 30 total faces.

301210000121033330121000012103

I simply noticed how the best configuration for 3 has two of the best configurations for 2 in it (121), and extrapolated the same way.

I'll still work on code to try and find a shorter one.

Also, will test if I can get a solution with 5 dice the same way...

(Edit: It doesn't work for 5 dice. Which makes sense due to needing one die with a number of faces that is a multiple of 5.)

Nice! I just checked your 30-face solution and it works just fine. I hope you can go lower.

[superprismatic]

I found another 30-face one: 201300110031022220130011003102 but I couldn't find any from n=20 through n=28 after exhausting all for which any die which had i on it, also had n+1-i (where n is even and between 20 and 28). The first one I found was for n=30 and is given above.