The Problem:
I encountered an interesting riddle recently called the "go first dice problem". The challenge is to come up with a set of dice (one per player) such that:- No two faces share the same label.
- The dice can be used to determine a fair turn order for the players after a single roll. That is, the player with the highest roll goes first, the second highest goes second, etc. A set of dice is fair if and only if every possible turn ordering is equally likely given random rolls.
More Information:
There are some stack exchange threads discussing the problem: Eric Harshbarger (puzzle designer/Lego sculptor/programmer/mathematician/Scrabble player) sells a set of 12 sided dice that solve the go first problem for four players: http://www.ericharshbarger.org/dice/#gofirst_4d12. As far as I know there is no known solution for five players. For fewer than five players:- 2 players: minimum 2 faces
- 3 players: minimum 6 faces
- 4 players: minimum 12 faces
The Challenge:
Find a set of go first dice for five players. This will require at least 30 faces per die.I have been working on trying to solve this (with a computer) for a few days. The search space is too large for a naïve brute-force search, so I think to make this computationally feasible you need to either:
- find a clever way to constrain the solution space (to make it small enough to exhaustively search), or
- come up with a heuristic so that your program is more likely to search in regions where a solution exists.
10 comments:
Given that you need to have 5 different dice and need to distribute them amongst the players anyway, here is an alternative solution to the root problem (but not the math/computational challenge): One dice with all 1's, one with all 2's, etc. Put them in a bag and have each player pick one at random and roll it. The turn order is now uniquely chosen. This method is so brilliant it also works without rolling.
You should try a constructivist approach.
The pattern is almost trivial when you consider the first set of five numbers, then the second, then the third and so on.
For example, the first set of numbers for the dice should be 1,2,3,4,5. Now, four of the five have an advantage. Give each advantage die a +1 in the 'advantage' attribute for that die. Now distribute the second set of numbers 6,7,8,9,10 in a way that minimizes the face total between the die for the currently distributed numbers and minimizing the difference between total cumulative advantage (this can only be reduced by one, overall, on each iteration.
Continue until you have no cumulative advantage and the face toatals on each of the die match each of the others and you are done.
Well so here's my math so far. This is a permutation of the actual players involved which is order dependent. That turns into 5 factorial or 120 permutations. Since we need to spread these permutations over five dice that means we need a 24 sided die. The next problem is how to make it fair. We can;t just assign 1,2,3,4,5 in order as the die that gets "5,10 .. etc" will always get the highest number. So we must rotate which die gets the highest number for every set of 5. The problem occurs when you actually go and try to assign the numbers. 24 is not divisible by 5 so assigning each die an even amount will not work. I believe that this can be done simple for 6 players with 120 sided dice.
While messing around with this problem today, I came across an interesting result. There are (xy)!/(x!(y!)^x) ways of placing x*y labels on x dice with y faces each.
I have not rigorously proven this, but every test case I have tried works out correctly.
While messing around with this problem today, I came across an interesting result. There are (xy)!/(x!(y!)^x) ways of placing x*y labels on x dice with y faces each.
I have not rigorously proven this, but every test case I have tried works out correctly.
There's a simple solution using (strangely-shaped) dice of different size.
5 sided with 5, 0, 0, 0, 0
4 sided with 4, 0, 0, 0
3 sided with 3, 0, 0
2 sided with 2, 0
1 sided with 1
multiply these to possible sizes of physical dice, and you're done!
Whoops, forgot about ordering players that do not win, or duplicate faces. More thought required.
Why would this configuration not be ok with the use of 5 sided dice?
die 1: 1,7,13,19,25
die 2: 2,8,14,20,21
die 3: 3,9,15,16,22
die 4: 4,10,11,17,23
die 5: 5,6,12,18,24
@anonymous (the comment above this one): that solution does not work because all possible turn orderings are not equally likely. In fact, it can be proven that the minimum number of faces per die for 5 players is 30 (see the math.stackexchange post for the proof).
How about this: each die face has a "swap positions" (two numbers) on it. You start with the order 1-2-3-4-5, apply all the "swap positions" shown by the five players' rolls (I believe they can be applied in any order and will yield the same result), and the resultant order is the order in which folks can go first. Doesn't meet the requirement of "biggest number goes first", though.
example: current order is 1-3-4-5-2, after applying "swap positions 1-2", order would be "2-3-4-5-1".
All die have the following 10 faces: 1-2,1-3,1-4,1-5
2-3,2-4,2-5
3-4,3-5,4-5
I'm going to run some computations to see if all orders are equally likely from the 10^5 resultant rolls. Symmetry would suggest so...
Post a Comment