You are right. This problem is hard. I wrote a series of computer
programs to gain insight, but all I found were huge sets of
combinations which to my mind were inscrutable. Nevertheless I have
some findings to report:
First, to clarify what is meant by "set up such a game with N dice,"
my understanding is that we are required to find a cycle of N dice in
which each die has an advantage over the next die in the cycle. Also I
have assumed that dice with M faces may be marked with values chosen
from a set of M distinct values, customarily taken to be
{1,2,3,...,M}.
Results:
4-sided dice may be used for N equal to 3 or 4. The sets of dice are:
N=3: (1, 1, 4, 4), (1, 3, 3, 3), (2, 2, 2, 4).
N=4: (1, 1, 4, 4), (1, 3, 3, 3), (2, 2, 3, 3), (2, 2, 2, 4).
Of course, cyclic permutations of length N are equally valid.
5-sided dice may be used for N from 3 to 96. For small values of N,
there is a tremendous number of combinations of dice which fulfill the
requirement of the game. Even for N=96 there are several unique
combinations.
6-sided dice may be used for N from 3 to 398.
7-sided dice may be used for N from 3 to 1634.
8-sided dice may be used for N from 3 to 6335.
9-sided dice may be used for N from 3 to 24190.
I will describe an algorithm which in principle can generate cycles of
dice for any N. I implemented it first in Python and then in C. There
is a tradeoff between memory requirement and speed, and I mostly
programmed for speed. On my desktop computer (2.2 GHz Intel Core 2 Duo
with 2 GB of RAM), memory was sufficient to solve up to the 9-sided
case with a run time of a few hours.
Method
Step 1: Generate a table of all possible M-sided dice, using
"combination with replacement." For 4-sided dice, there are 35
possible dice which may be ordered as follows:
(1, 1, 1, 1)
(1, 1, 1, 2)
(1, 1, 1, 3)
(1, 1, 1, 4)
(1, 1, 2, 2)
(1, 1, 2, 3)
(1, 1, 2, 4)
(1, 1, 3, 3)
(1, 1, 3, 4)
(1, 1, 4, 4)
(1, 2, 2, 2)
(1, 2, 2, 3)
(1, 2, 2, 4)
(1, 2, 3, 3)
(1, 2, 3, 4)
(1, 2, 4, 4)
(1, 3, 3, 3)
(1, 3, 3, 4)
(1, 3, 4, 4)
(1, 4, 4, 4)
(2, 2, 2, 2)
(2, 2, 2, 3)
(2, 2, 2, 4)
(2, 2, 3, 3)
(2, 2, 3, 4)
(2, 2, 4, 4)
(2, 3, 3, 3)
(2, 3, 3, 4)
(2, 3, 4, 4)
(2, 4, 4, 4)
(3, 3, 3, 3)
(3, 3, 3, 4)
(3, 3, 4, 4)
(3, 4, 4, 4)
(4, 4, 4, 4)
Step 2: Search for and eliminate any die which cannot win or cannot
lose. For example, (1, 1, 1, 1) cannot win, and (4, 4, 4, 4) cannot
lose, so we delete them from the list. Do it again. In the next round,
(1, 1, 1, 2) and (3, 4, 4, 4) will be eliminated. Repeat until there
is no further elimination. This yields the largest possible set of
dice in which each die can win against at least one other die and lose
against at least one other die. For 4-sided dice, we are left with
only 4 dice:
(1, 1, 4, 4)
(1, 3, 3, 3)
(2, 2, 2, 4)
(2, 2, 3, 3)
We shall call the length of this list L.
Step 3: To speed up the next steps (not needed for 4-sided but useful
for larger dice), create a lookup table which will be used to quickly
determine, for any two dice in the list, whether one of them is a
winner (has the advantage). I implemented this as a L-by-L square
array where the two array indices are the list positions of the two
dice, and the array elements are True (first die wins) or False (first
die does not win, which means either the second die wins or it is a
tie).
Step 4: Make a random selection of 3 dice from the list. Let's call
them A, B, and C. Test whether A wins over B, B wins over C, and C
wins over A. That would be our N=3 cycle. If it is not such a cycle,
repeat the random selection until a cycle of N=3 is found.
Steps 5 through 7: Expand the cycle by inserting one die at a time
according to the following procedure:
Step 5: Randomly select a position in the cycle. Let's call it the
insertion point.
Step 6: For the die at that position and the die at the next position,
wrapping around at the ends as needed, determine the set of all die
which are still available (not already in the cycle) and which may be
inserted between the two while preserving the cyclic property. In
other words, find all available dice which lose to the die at the
insertion point and win over the die immediately following the
insertion point.
Step 7: From that set of "insertable" dice, randomly select one die
and insert it into the sequence, thereby creating a new cycle of
length N increased by 1. Go back to Step 5 and do it all over
again. Continue until there are no more dice available (that is, until
N=L).
The above procedure must be modified if progress cannot be made at some point:
Test A: If Step 6 fails to find any die which satisfies the
conditions, go back to Step 5 and try again, randomly selecting a new
insertion point.
Test B: If Step 6 fails repeatedly to find an insertable die, and
there are still available (unused) dice, go back to Step 4 and start
over with a different N=3 cycle. Alternatively, one could abandon the
random selection of Step 5 and simply try every position in the cycle,
and if that too fails, go back to Step 4.
Test C: If Test B goes back to Step 4 many times and one is always
left with a few dice that cannot be inserted, it may be that it is
just impossible to expand the cycle past a certain limit. I found this
to be the case for 5-sided dice; of the L=98 available dice, I could
fit no more than N=96 of them into any cycle. In every other case that
I examined (M=4, 6, 7, 8, 9), I was able to find cycles using all
available dice, that is, cycles of length N from 3 to L.
I have attached a C program that roughly follows the above
method. Feel free to share the it with anyone who is interested.
================================================================
// dice_cycles.c
// designed and written by Tony Bielecki
// to investigate the dice game described in
// Puzzle Corner, problem S/O 2, MIT News section,
// Technology Review, September/October 2017
// In Linux it may be compiled and executed as follows:
// gcc -O3 -o dice_cycles dice_cycles.c
// ./dice_cycles M # (M = number of faces on the die)
// The program output, written to the terminal via stdout,
// can be rather large, e.g., 1.9 GB for M=9. I suggest
// you redirect it to a file or rewrite the program
// to use fprintf or another file output method.
#include
#include
int next_combination_with_replacement(char * array, int place, int base)
{
int i;
if (place==0)
array[place] += 1;
else if (next_combination_with_replacement(array, place-1, base))
{
array[place] += 1;
for (i=0;i 0)
++win;
else if (diff < 0)
++lose;
}
return win-lose;
} // closing bracket of function first_wins()
int random_integer_in_range(int range)
{
int my_rand;
int power = 1;
while (power=range);
return my_rand;
}
int main(int argc, char *argv[])
{
if (argc != 2)
{
fprintf(stderr, "command requires one integer argument (number of faces)\n");
return 1;
}
int faces;
faces = strtol(argv[1], NULL, 10);
if (faces<3)
{
fprintf(stderr, "command requires number of faces >= 3\n");
return 1;
}
srand(time(NULL));
int i, j, k, win, lose, del_forward, del_reverse, temp;
printf("create dice table\n");
// calculate number of dice
// using standard formula for combinations with replacement
int ndice = 1;
for (i=faces+1;i 0)
win = 1;
if (temp < 0)
lose = 1;
}
if ((win==0)||(lose==0))
{
// tag by setting the first face to zero
alldice[i][0] = 0;
del_forward = 1;
break;
}
}
// search alternately in the reverse direction
// (this reduces the search time by about a factor of 4)
del_reverse = 0;
for(i=0;i 0)
win = 1;
if (temp < 0)
lose = 1;
}
if ((win==0)||(lose==0))
{
alldice[ndice-i-1][0] = 0;
del_reverse = 1;
break;
}
}
} while (del_forward || del_reverse);
// compact dice table after elimination
j = 0;
for(i=0;i0)
wins[i][j] = 1;
else
wins[i][j] = 0;
}
// allocate array for insertion table
int * insert = (int *)malloc(ndice*sizeof(int));
if (!insert)
{
fprintf(stderr, "Error: failed to allocate memory for insert\n");
return 1;
}
// allocate array for dice cycle
int * dcycle = (int *)malloc(ndice*sizeof(int));
if (!dcycle)
{
fprintf(stderr, "Error: failed to allocate memory for dcycle\n");
return 1;
}
// allocate array for all cycles
int ** allcycles = (int **)malloc((ndice-2)*sizeof(int *));
if (!allcycles)
{
fprintf(stderr, "Error: failed to allocate memory for allcycles (pointer array)\n");
return 1;
}
// allocate data space
// the formula below is for the sum of integers from 3 to ndice, inclusive.
allcycles[0] = (int *)malloc(((ndice*(ndice+1)/2)-3)*sizeof(int));
if (!allcycles[0])
{
fprintf(stderr, "Error: failed to allocate memory for allcycles[0] (data array)\n");
return 1;
}
// set up array of pointers to data
for(i=0;iplace+1;--j)
dcycle[j] = dcycle[j-1];
// insert new_die in place
dcycle[place+1] = new_die;
// update cycle length
++ncycle;
// append dcycle to allcycles
for(j=0;j