Jump to content
BrainDen.com - Brain Teasers
  • 0

Dicey Permutations


superprismatic
 Share

Question

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?

Link to comment
Share on other sites

9 answers to this question

Recommended Posts

  • 0

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...

Link to comment
Share on other sites

  • 0

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.

Link to comment
Share on other sites

  • 0

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.

Link to comment
Share on other sites

  • 0

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.)

Link to comment
Share on other sites

  • 0

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.

Link to comment
Share on other sites

Join the conversation

You can post now and register later. If you have an account, sign in now to post with your account.

Guest
Answer this question...

×   Pasted as rich text.   Paste as plain text instead

  Only 75 emoji are allowed.

×   Your link has been automatically embedded.   Display as a link instead

×   Your previous content has been restored.   Clear editor

×   You cannot paste images directly. Upload or insert images from URL.

Loading...
 Share

  • Recently Browsing   0 members

    • No registered users viewing this page.
×
×
  • Create New...