10
$\begingroup$

Recently, I stumbled upon the puzzle: Make Two Dice out of Three, which asks for a solution to a case of the following question:

Suppose I roll $n$ indistinguishable dice. From purely the $n$ numbers showing, and no information about the ordering of the dice, what algorithm can I use, spitting out an unordered pair of numbers $a$ and $b$ such that the distribution of the unordered pair $(a,b)$ is the same as the distribution of a roll of two unordered dice?

After reading through the solutions posed on the question, none of which seemed particularly easy to remember, I sent the question along to one of my mathematician friends, Cassandra. She proposed the following general form for a more elegant strategy:

Well, obviously if you wanted to make one die from many, you could do so by taking the sum of the dice mod $6$. That is, if the dice come up as $x_1,x_2,\ldots,x_n$ you combine them into one value as $$x_1+x_2+\ldots + x_n \pmod6.$$ Rather than adopt some complicated scheme for getting two rolls, it would make more sense to me to try and salvage this strategy. In particular, choose two functions $f$ and $g$ and then say that if the dice come up as $x_1,x_2,\ldots,x_n$, you read the two rolls as the following: $$f(x_1)+f(x_2)+\ldots + f(x_n)\pmod6$$ $$g(x_1)+g(x_2)+\ldots + g(x_n)\pmod6.$$ I'm sure this is possible for large enough $n$ and some $f$ and $g$.

I like this idea, since one would only have to memorize two functions on a domain and range of six elements and it avoid any casework. To ease my work a bit, I have decided to only consider whether this is possible for even $n$. After much trying, I have been unable to find such functions. I'm sure I could go back and ask her for clarification, but I'm too embarassed - so I'll ask all of you: Can Cassandra's prediction be true for any even $n$?


As a couple answers below interpret the question differently than intended, let me write out the condition formally: Let $$F=f(x_1)+\ldots +f(x_n)\pmod 6$$ $$G=g(x_1)+\ldots+g(x_n)\pmod 6.$$ We wish to have that for any suitable $a$ and $b$ we have that $$P(F=a\text{ and }G=b) + P(F=b\text{ and }G=a)=\frac{1}{18}.$$ where $P$ is the probability of an event happening. This is what is meant by saying that $(F,G)$ has the same distribution as a roll of two unordered dice.

As a hint, let me say that the intended solution is not a counting argument, nor does it have to do with examining probabilities too carefully; it is rather more analytical in nature.

$\endgroup$
  • $\begingroup$ Where it says "From purely the three numbers showing...", should that be $n$ instead of three? Or perhaps, in the first sentence, it should be three instead of $n$? $\endgroup$ – hexomino May 24 '16 at 9:03
  • $\begingroup$ @hexomino Thanks for pointing that out; I fixed it to be $n$ in both places. $\endgroup$ – Milo Brandt May 24 '16 at 14:04
  • $\begingroup$ I feel question should be here too math.stackexchange.com $\endgroup$ – Adit Kirtani May 28 '16 at 18:36
2
+25
$\begingroup$

[This answer formerly claimed to prove that the thing can't be done for any $n$, odd or even, but there were at least two big holes in the proof. The following now claims to be no more than what might some day be the beginning of a proof. I'm still thinking about it.]

Write $p=x^{f(1)}y^{g(1)}+\cdots+x^{f(6)}y^{g(6)}$. Then the probability of getting sums $i,j$ after rolling $n$ dice is given by the coefficient of $x^iy^j$ in $(p/6)^n$. To reduce the sums mod 6 we need to work in polynomials mod $(x^6-1,y^6-1)$. And the question is then whether we can arrange that $p^n/6^{n-2}=(1+\cdots+x^5)(1+\cdots+y^5)$ mod $(x^6-1,y^6-1)$ or, equivalently, that $p^n/6^{n-2}=(1+\cdots+x^5)(1+\cdots+y^5)+(1-x^6)a+(1-y^6)b$ where $a,b$ are polynomials.

... Except that we're supposed to be looking at unordered pairs of results, which means what we want is that a corresponding thing holds not for $p(x,y)^n$ but for $p(x,y)^n+p(y,x)^n$. If we put $x=y$ then this is just $2p(x,x)^n$.

Suppose $x$ is a 6th root of unity other than 1. Then clearly the RHS is zero, so the LHS is too. So $p(x,x)^n=0$ for every such choice of $x$; so $p(x,x)=0$ for every such choice of $x$. In particular, when $\omega^6=1$, $(x-\omega)$ is a factor of $p(x,x)$ and therefore so is the product of all these factors, namely $(x^6-1)/(x-1)=1+\cdots+x^5$.

Now, what exactly is $p(x,x)$? It's $\sum x^{f(i)+g(i)}$; and remember that we only care about $f,g$ mod 6. So what this tells us is that each residue mod 6 appears exactly once among the $f(i)+g(i)$. So we can write $p=\sum x^i(y/x)^{h(i)}$ with the usual caveats about exponents being mod 6. (If you're queasy about non-polynomials, say $x^5y$ instead of $y/x$.)

$\endgroup$
  • $\begingroup$ As somewhat of a hint, this is the start of the solution I was intending*, though some of the material that you used to analyze $p(x,y)^n$ in the first draft of your post before you edited is relevant to analyzing $p(x,y)^n+p(y,x)^n$ as well. (*I was envisioning using somewhat different tools, but I worked things out using these polynomials, and everything is about the same) $\endgroup$ – Milo Brandt May 30 '16 at 21:05
1
$\begingroup$

If the statement holds for any even $n$, it holds for $n=2$.

$x_1'=f(x_1)+f(x_2) \mod 6\\ x_2'=g(x_1)+g(x_2) \mod 6$

Since $+$ is commutative, the order of the two input dice is not important (e.g. $(3, 5)$ will give the same result as $(5,3)$). This means that the number of unique ordered pairs $(x_1',x_2')$ is at most $21$ (the number of unique inputs). However, the number of unique ordered pairs of two dice roll results is $36>21$, which means that not every result can be produced, and the statement is false.

$\endgroup$
  • $\begingroup$ I don't see why it holding for any even $n$ implies it holds for $n=2$. Also, the idea is that the result $(x_1',x_2')$ is also taken to be unordered - so there are equally many unordered pairs $(x_1,x_2)$ coming in as there are going out. (That said, you can prove that not every unordered pair $(x_1',x_2')$ shows up for two dice rolls, but this is not trivial) $\endgroup$ – Milo Brandt May 24 '16 at 14:55
  • 3
    $\begingroup$ I think Fons may be taking "P holds for any even n" to mean "for all even n, P holds" whereas you're asking the question "is there any even n for which P holds?". $\endgroup$ – Gareth McCaughan May 24 '16 at 15:28
  • $\begingroup$ @MiloBrandt : You're using "ordered" in a different sense than Fons is. You need to be able to say "the red die came up 3, and the blue die came up 4" in the output as a distinct event from "the red die came up 4 and the blue die came up 3," but you don't get that information about the input. $\endgroup$ – Matthew Graves May 25 '16 at 18:41
  • $\begingroup$ As Milo says, this answer shows the result for ordered pairs, not unordered. E.g. suppose (forgetting about the sum-a-function thing) we took $x'_1 = \min(x_1,x_2)$, and $x'_2 = \max(x_1,x_2)$. Then this does accurately simulate the distribution of an unordered pair of dice, even though (for the same reasons as your example) it only gives 21 possible outputs. It will never give $(4,3)$, but it will give $(3,4)$ (which yields the same unordered pair) twice as often, so at the level of the induced probability distribution on unordered pairs, it comes out correct. $\endgroup$ – Peter LeFanu Lumsdaine May 27 '16 at 8:29
0
$\begingroup$

(Check the edit history of this post to see my old answer, which was missing the point.)

Now that I see what's going on, I'm not confident that such a function does exist of the form described.

That is, we need it to be the case where there are at least six $\bf{x}$ vectors such that $\sum f(x_i) \mod 6 = 0$, which also satisfy the property that $\sum g(x_i) \mod 6$ is uniformly distributed from 0 to 5.

The number of input and output states line up--for basically any number of dice--but I think the functional constraint that the function is applied to individual rolls, and then summed, destroys your ability to sufficiently distinguish between states. It's not clear how you're going to get rid of the correlation between the sum of $f$ and the sum of $g$, but it's also not immediately obvious to me how to prove they're always linked. Perhaps there's a group theory argument here that's neat?

$\endgroup$
  • 2
    $\begingroup$ The idea of "unordered" output is that $(a,b)$ and $(b,a)$ are taken to be the same - which is what I was trying to get at under Fons' answer. So, for two dice, there are 21 inputs and 21 outputs. Additionally, your answer suggests that it is necessary that the number of possible inputs divide the number of possible outputs. This is true when both input and output are distributed uniformly, but the input, when taken as combinations, is definitely not distributed uniformly, so the condition fails. (e.g. $(6,6,6,6)$ comes up $24$ times less often than $(1,2,3,4)$) $\endgroup$ – Milo Brandt May 25 '16 at 19:41
  • $\begingroup$ @MiloBrandt You're right, I misread the clarification on the other question, where (3,6) and (6,3) are allowed to be the same result. My impression was you had to be able to tell the difference between them. My intuition is that division is required to get any sort of convenient mapping, but that doesn't have to be the case. $\endgroup$ – Matthew Graves May 25 '16 at 20:32
0
$\begingroup$

Let $x_i$ be the $i$ th element of the sequence of results sorted into increasing order.

Let $k$ be the roll iteration.

Using Iverson bracket notation:

$F = \Big( {\large{\scriptsize [k \in \{2j:j \in \mathbb N\}]} \sum_{i=1}^n {\scriptsize [i \in \{2j−1:j \in \mathbb N\}]} ~ x_i} \Big )(mod~6) + \Big( {\scriptsize [k \in \{2j-1:j \in \mathbb N\}]} \sum_{i=1}^n {\scriptsize[i \in \{2j:j \in \mathbb N\}]} ~ x_i \Big) (mod~6)$

$G = \Big( {\large{\scriptsize [k \in \{2j-1:j \in \mathbb N\}]} \sum_{i=1}^n {\scriptsize [i \in \{2j−1:j \in \mathbb N\}]} ~ x_i} \Big )(mod~6) + \Big( {\scriptsize [k \in \{2j:j \in \mathbb N\}]} \sum_{i=1}^n {\scriptsize[i \in \{2j:j \in \mathbb N\}]} ~ x_i \Big)(mod~6)$

Here $n$ can be odd or even. $(mod ~6)$ makes it irrelevant.

$\endgroup$
  • 1
    $\begingroup$ So you have $f(x, i, k)$ and $g(x, i, k)$ I wonder if that is acceptable? $\endgroup$ – Jonathan Allan May 30 '16 at 3:44
-1
$\begingroup$

Let $x_i$ be the $i$th element of the sequence of results sorted into increasing order.

Let $k$ be the roll iteration.

Let $E = \Sigma x_i \ (mod ~6)\ $ for even $i$

Let $O = \Sigma x_i \ (mod ~ 6)\ $ for odd $i$

Let $F = E$ if $k$ is even, otherwise $F=O$

Let $G = O$ if $k$ is odd, otherwise $G=E$

$\endgroup$
  • 1
    $\begingroup$ This solution is not of the form specified in the question. $\endgroup$ – Gareth McCaughan May 27 '16 at 10:03
-1
$\begingroup$

Perhaps I'm being too lazy... perhaps I misunderstand the question.

Let f(x) be the sum of rolls modulo 6 of all the dice i <= n/2: $f(x) = \sum_0^{n/2} x_i \ ,mod ~6$

Let g(x) be the sum of rolls modulo 6 of all the dice i > n/2: $g(x) = \sum_{(n/2)+1}^n x_i \ ,mod ~6$

For any even n, an equal number of dice are combined for F and for G, but as each probability on a single roll is equal, you can simply split the rolled dice into two arbitrary piles and take the sum modulo 6 of each pile separately.

What remains is trivially equivalent to two single rolls.

$\endgroup$
  • 1
    $\begingroup$ Yes, I think you misunderstand the question. The idea is that you have functions f,g that are applied uniformly to all the die rolls and added up. $\endgroup$ – Gareth McCaughan May 27 '16 at 10:05
-1
$\begingroup$

Doesn't the following yield normal distribution, for any $n$, any number of unordered outputs, and any type of dice?

Let $d$ = number of virtual output dice
Let $s$ = number of honest die sides
Given $n>d$

$$x'_1=f(x_1)+...+f(x_{n-d}) \text{ } [Mod \text{ }s] $$ $$x'_2=f(x_2)+...+f(x_{n-d+1}) \text{ } [Mod \text{ }s] $$ $$x'_3=f(x_3)+...+f(x_{n-d+2}) \text{ } [Mod \text{ }s] $$ $$\cdot$$ $$\cdot$$ $$\cdot$$ $$x'_d=f(x_d)+...+f(x_{n}) \text{ } [Mod \text{ }s] $$


$\endgroup$
  • 1
    $\begingroup$ You can't distinguish the dice (that is you don't know which one is $x_1$ and which one is $x_{n-d+1}$) so you can't deduce $x_1'$ or $x_2'$ from what you know using these formulae. $\endgroup$ – JiK May 31 '16 at 12:35
  • $\begingroup$ I see what you mean, and therefore I can imagine no possible way to map 16 possible input states $\Sigma n$ into the 21 necessary output states to preserve normal distribution. $\endgroup$ – SteveRacer May 31 '16 at 21:09
-4
$\begingroup$

$F = f(x_1)+…+f(x_n) = x_1$

$G = g(x_1)+…+g(x_n) = x_2$

Since the die are indistinguishable by design, $x_i$ is a random assignment. Use whatever assignment the OP used in framing the the puzzle. The formulas satisfy the problem. It's not a counting argument, and it doesn't examine probabilities too carefully.

$\endgroup$
  • $\begingroup$ Please explain.  And use spoiler markdown. $\endgroup$ – Peregrine Rook May 27 '16 at 1:02
  • 1
    $\begingroup$ You aren't allowed to set F = x1. You have to choose F indirectly by specifying what f is, which along with the equation F = f(x1) + ... + f(xn) defines F. $\endgroup$ – Mike Earnest May 27 '16 at 2:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.