Submit All submissions Best solutions PDF Back to list

PROG0519 - Sichermans dice

What's unusual about these dice is obvious, but what's normal about them?

sicherman
Sicherman dice

These dice were discovered by George Sicherman (Buffalo, New York, USA) and were originally reported by Martin Gardner in a 1978 article in Scientific American. When the dice are thrown together, they produce the same probability distribution as a pair of ordinary dice. There are six ways to throw a 7, five ways to throw an 8, etc. Moreover, the Sicherman dice are the only possible alternate arrangement of strictly positive integers that result in the same probability distribution as a pair of ordinary dice.

It is a standard exercise in elementary combinatorics to calculate the number of ways of rolling any given value with a pair of fair six-sided dice (by taking the sum of the two rolls). The table shows the number of such ways of rolling a given value $n$:

$n$ 2 3 4 5 6 7 8 9 10 11 12
# of ways 1 2 3 4 5 6 5 4 3 2 1

A question arises whether there are other ways of relabeling the faces of the dice with positive integers that generate these sums with the same frequencies. The surprising answer to this question is that there does indeed exist such a way. These are the Sicherman dice. Three additional rearrangements having the same probability distribution as  a pair of ordinary dice are possible if the dice are allowed to have empty sides.

The table below lists all possible totals of dice rolls with standard dice and Sicherman dice. One Sicherman die is coloured for clarity 1–2–2–3–2–4 and the other is all black 1–3–4–5–6–8.


2 3 4 5 6 7 8 9 10 11 12
ordinary dice 1+1 1+2
2+1		 1+3
2+2
3+1		 1+4
2+3
3+2
4+1		 1+5
2+4
3+3
4+2
5+1		 1+6
2+5
3+4
4+3
5+2
6+1		 2+6
3+5
4+4
5+3
6+2		 3+6
4+5
5+4
6+3		 4+6
5+5
6+4		 5+6
6+5		 6+6
Sicherman dice 1+1 2+1
2+1		 3+1
3+1
1+3		 1+4
2+3
2+3
4+1		 1+5
2+4
2+4
3+3
3+3		 1+6
2+5
2+5
3+4
3+4
4+3		 2+6
2+6
3+5
3+5
4+4		 1+8
3+6
3+6
4+5		 2+8
2+8
4+6		 3+8
3+8		 4+8

Assignment

In this exercise, the outcome of a throw with a pair of dice is represented as a tuple $(x, y)$ where $x \in \mathbb{N}$ represents the number of pips at the top side of the first die, and $y \in \mathbb{N}$ the number of pips at the top side of the second die. Note that we do not limit ourselves in this exercise to six-sided dice, and that the a single die may have sides carrying the same number of pips. A pair of dice is represented a list or tuple of two dice. Your task:

  • Write a function combinations that takes two dice. The function must return a dictionary that maps all possible outcomes of a throw with the pair of dice (obtained by taking the sum of the two rolls) onto the list of throws that gives a particular outcome. The throws must be listed in increasing order according to the number of pips on the first die.
  • Write a function distribution that takes two dice. The function must return a dictionary that maps all possible outcomes of a throw with the pair of dice (obtained by taking the sum of the two rolls) onto the number of throws that gives a particular outcome.
  • Write a function equalDistribution that takes two pair of dice. The function must return a Boolean value that indicates whether or not both pairs of dice produce the same probability distribution of possible outcomes (obtained by taking the sum of the two rolls).

Example

>>> dice6_1 = {1, 2, 3, 4, 5, 6}
>>> dice6_2 = [1, 2, 2, 3, 3, 4]
>>> dice6_3 = (1, 3, 4, 5, 6, 8)

>>> throw = combinations(dice6_1, dice6_1)
>>> throw[8]
[(2, 6), (3, 5), (4, 4), (5, 3), (6, 2)]
>>> throw = combinations(dice6_2, dice6_3)
>>> throw[8]
[(2, 6), (2, 6), (3, 5), (3, 5), (4, 4)]

>>> distribution(dice6_1, dice6_1)
{2: 1, 3: 2, 4: 3, 5: 4, 6: 5, 7: 6, 8: 5, 9: 4, 10: 3, 11: 2, 12: 1}
>>> distribution(dice6_2, dice6_3)
{2: 1, 3: 2, 4: 3, 5: 4, 6: 5, 7: 6, 8: 5, 9: 4, 10: 3, 11: 2, 12: 1}

>>> equalDistribution([dice6_1, dice6_1], (dice6_2, dice6_3))
True

>>> dice8_1 = {1, 2, 3, 4, 5, 6, 7, 8}
>>> dice8_2 = (1, 3, 5, 5, 7, 7, 9, 11)
>>> dice8_3 = (1, 2, 2, 3, 3, 4, 4, 5)
>>> dice8_4 = (1, 2, 5, 5, 6, 6, 9, 10)
>>> dice8_5 = (1, 2, 3, 3, 4, 4, 5, 6)
>>> equalDistribution((dice8_1, dice8_1), (dice8_2, dice8_3))
True
>>> equalDistribution((dice8_1, dice8_1), (dice8_3, dice8_4))
False
>>> equalDistribution((dice8_1, dice8_1), (dice8_4, dice8_5))
True

References

  • Broline D (1979). Renumbering of the faces of dice. Mathematics Magazine 52(5), 312-315.
  • Brunson BW, Swift RJ (1999). Equally likely sums. Mathematical Spectrum 30(2), 34-36.
  • Fowler BC, Swift RJ (1999). Relabeling dice. College Mathematics Journal 30(3), 204-208.
  • Gallian JA, Rusin DJ (1979). Cyclotomic polynomials and nonstandard dice. Discrete Mathematics 27(3), 245-259.
  • Garnder M (1978). Mathematical Games. Scientific American 238(2), 19-32.

Het is onmiddellijk duidelijk dat dit geen gewone dobbelstenen zijn, maar wat is er dan wel gewoon aan deze dobbelstenen?

sicherman
De dobbelstenen van Sicherman

Deze dobbelstenen werden ontdekt door George Sicherman (Buffalo, New York, VSA) en werden voor het eerst gepubliceerd door Martin Gardner in een editie van Scientific American uit 1978. Als de dobbelstenen samen gegooid worden, dan hebben ze dezelfde kansverdeling als een paar gewone dobbelstenen. Er zijn bijvoorbeeld zes manieren om een 7 te gooien, vijf manieren om een 8 te gooien, enzoverder. De dobbelstenen van Sicherman vormen bovendien de enige mogelijke alternatieve schikking van strikt positieve natuurlijke getallen die dezelfde kansverdeling geven als gewone dobbelstenen.

Het is een basisoefening uit de combinatoriek om het aantal mogelijke manieren te bepalen waarop een gegeven waarde kan gegooid worden met een paar gewone zeszijdige dobbelstenen (door de som van het aantal ogen op beide dobbelstenen te nemen). Onderstaande tabel toont het aantal mogelijke manieren voor elke mogelijke uitkomst $n$:

$n$ 2 3 4 5 6 7 8 9 10 11 12
# manieren 1 2 3 4 5 6 5 4 3 2 1

De vraag die zich stelt is of de ogen op de dobbelstenen ook op een andere manier kunnen geschikt worden zodat de mogelijke uitkomsten van de dobbelstenen dezelfde kansverdeling opleveren. Het verrassende antwoord op deze vraag is dat er inderdaad een mogelijkheid bestaat, onder de vorm van de dobbelstenen van Sicherman. Indien het toegelaten is om dobbelstenen te maken met zijden die geen ogen hebben, dan zijn er nog drie bijkomende combinaties van dobbelstenen met dezelfde kansverdeling mogelijk.

Onderstaande tabel toont alle mogelijke uitkomsten die kunnen bekomen worden met een paar gewone dobbelstenen en met de dobbelstenen van Sicherman. Voor de duidelijk hebben we één van de dobbelstenen van Sicherman gekleurd 1–2–2–3–2–4 en hebben we de andere zwart gelaten 1–3–4–5–6–8.


2 3 4 5 6 7 8 9 10 11 12
gewone dobbelstenen 1+1 1+2
2+1		 1+3
2+2
3+1		 1+4
2+3
3+2
4+1		 1+5
2+4
3+3
4+2
5+1		 1+6
2+5
3+4
4+3
5+2
6+1		 2+6
3+5
4+4
5+3
6+2		 3+6
4+5
5+4
6+3		 4+6
5+5
6+4		 5+6
6+5		 6+6
dobbelstenen van Sicherman 1+1 2+1
2+1		 3+1
3+1
1+3		 1+4
2+3
2+3
4+1		 1+5
2+4
2+4
3+3
3+3		 1+6
2+5
2+5
3+4
3+4
4+3		 2+6
2+6
3+5
3+5
4+4		 1+8
3+6
3+6
4+5		 2+8
2+8
4+6		 3+8
3+8		 4+8

Opgave

In deze opgave stellen we een worp met twee dobbelstenen voor als tuple $(x, y)$ waarbij $x \in \mathbb{N}$ het aantal ogen voorstelt op de bovenste zijde van de eerste dobbelsteen, en $y \in \mathbb{N}$ het aantal ogen op de bovenste zijde van de tweede dobbelsteen. Een dobbelsteen wordt voorgesteld als een collectie (een lijst, tuple, verzameling, …) van natuurlijke getallen. Merk dus op dat we ons in deze opgave niet beperken tot zeszijdige dobbelstenen, en dat het mogelijk is dat sommige zijden van eenzelfde dobbelsteen eenzelfde aantal ogen hebben. Een paar dobbelstenen wordt voorgesteld als een lijst of een tuple van twee dobbelstenen. Gevraagd wordt:

  • Schrijf een functie combinaties waaraan twee dobbelstenen moeten doorgegeven worden. De functie moet een dictionary teruggeven, die alle mogelijke uitkomsten van een worp met de twee geven dobbelstenen (bekomen door de som van het aantal ogen op beide dobbelstenen te nemen) afbeeldt op de lijst van alle worpen die een bepaalde uitkomst opleveren. De worpen moeten in oplopende volgorde opgelijst worden volgens het aantal ogen op de eerste dobbelsteen.
  • Schrijf een functie verdeling waaraan twee dobbelstenen moeten doorgegeven worden. De functie moet een dictionary teruggeven, die alle mogelijke uitkomsten van een worp met de twee geven dobbelstenen (bekomen door de som van het aantal ogen op beide dobbelstenen te nemen) afbeeldt op het aantal worpen die een bepaalde uitkomst opleveren.
  • Schrijf een functie gelijkeVerdeling waaraan twee paar dobbelstenen moeten doorgegeven worden. De functie moet een Booleaanse waarde teruggeven die aangeeft of beide paren dobbelstenen dezelfde kansverdeling van mogelijke uitkomsten hebben (bekomen door de som van het aantal ogen op beide dobbelstenen te nemen).

Voorbeeld

>>> dobbel6_1 = {1, 2, 3, 4, 5, 6}
>>> dobbel6_2 = [1, 2, 2, 3, 3, 4]
>>> dobbel6_3 = (1, 3, 4, 5, 6, 8)

>>> worp = combinaties(dobbel6_1, dobbel6_1)
>>> worp[8]
[(2, 6), (3, 5), (4, 4), (5, 3), (6, 2)]
>>> worp = combinaties(dobbel6_2, dobbel6_3)
>>> worp[8]
[(2, 6), (2, 6), (3, 5), (3, 5), (4, 4)]

>>> verdeling(dobbel6_1, dobbel6_1)
{2: 1, 3: 2, 4: 3, 5: 4, 6: 5, 7: 6, 8: 5, 9: 4, 10: 3, 11: 2, 12: 1}
>>> verdeling(dobbel6_2, dobbel6_3)
{2: 1, 3: 2, 4: 3, 5: 4, 6: 5, 7: 6, 8: 5, 9: 4, 10: 3, 11: 2, 12: 1}

>>> gelijkeVerdeling([dobbel6_1, dobbel6_1], (dobbel6_2, dobbel6_3))
True

>>> dobbel8_1 = {1, 2, 3, 4, 5, 6, 7, 8}
>>> dobbel8_2 = (1, 3, 5, 5, 7, 7, 9, 11)
>>> dobbel8_3 = (1, 2, 2, 3, 3, 4, 4, 5)
>>> dobbel8_4 = (1, 2, 5, 5, 6, 6, 9, 10)
>>> dobbel8_5 = (1, 2, 3, 3, 4, 4, 5, 6)

>>> gelijkeVerdeling((dobbel8_1, dobbel8_1), (dobbel8_2, dobbel8_3))
True
>>> gelijkeVerdeling((dobbel8_1, dobbel8_1), (dobbel8_3, dobbel8_4))
False
>>> gelijkeVerdeling((dobbel8_1, dobbel8_1), (dobbel8_4, dobbel8_5))
True

Bronnen

  • Broline D (1979). Renumbering of the faces of dice. Mathematics Magazine 52(5), 312-315.
  • Brunson BW, Swift RJ (1999). Equally likely sums. Mathematical Spectrum 30(2), 34-36.
  • Fowler BC, Swift RJ (1999). Relabeling dice. College Mathematics Journal 30(3), 204-208.
  • Gallian JA, Rusin DJ (1979). Cyclotomic polynomials and nonstandard dice. Discrete Mathematics 27(3), 245-259.
  • Garnder M (1978). Mathematical Games. Scientific American 238(2), 19-32.
Submit solution!
Added by:Peter Dawyndt
Date:2014-11-11
Time limit:10s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:PY_NBC
Resource:None
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.