Lecture Notes: Dice Problem and Polynomial Solutions

Introduction

• The lecture discusses a fascinating dice problem originally presented to the Greater Boston chapter of the ACM.
• Main question: Can two six-sided dice be labeled with positive integers in a non-standard way to yield the same probability distribution as standard dice?

Problem Statement

• Standard Dice Probability Distribution:
  • Rolling two six-sided dice and adding the results gives a probability distribution.
  • Most probable sum: 7
  • Probability of getting Snake Eyes (sum of 2): 1/36
• Challenge:
  • Finding a non-standard labeling that results in the same distribution.
  • Dice can have duplicate labels and different labeling schemes.

Traditional Approach

• Narrow down possibilities using pen and paper.
• Use programming to search a reduced space.

Miraculous Solution

• A pen and paper solution using polynomials was introduced by a friend.
• Polynomial Representation:
  • Each die can be represented by a polynomial where the coefficient of x^k is the number of faces labeled with k.
  • Example for a standard die: x + x² + x³ + x⁴ + x⁵ + x⁶
  • Non-standard example: 2x⁵ + 4x⁹ (die with labels 5 and 9)

Simplification Using Polynomials

• Key Insight:
  • The probability distribution on the sum of two dice relates to multiplying their polynomials.
  • Example: Sum of 7 corresponds to coefficient of x⁷ in the product of two polynomial dice.

Unique Factorization of Polynomials

• Objective:
  • Find two different polynomials (B and C) that multiply to the standard polynomial.
  • Factorization helps in reducing the search space and simplifying the solution.

Constraints for Polynomial Dice

• Constraints:
  • Coefficients must be non-negative integers.
  • Labels must be positive integers (a₀ = 0).
  • Sum of coefficients equals 6 (six faces per die).
• Evaluating Constraints:
  • At x = 0, polynomial evaluates to 0.
  • At x = 1, polynomial evaluates to 6.

Factorization and Solution

• Factorization:
  • Standard die polynomial: x * (1 + x) * (1 - x + x²) * (1 + x + x²)
  • Distribute factors among B and C to satisfy constraints.
• Resulting Non-Standard Dice (Sierman Dice):
  • B: x + 2x² + 2x³ + x⁴
  • C: x + x³ + x⁴ + x⁵ + x⁶ + x⁸*

Conclusion

• The solution finds a unique alternate set of labels that result in the same distribution.
• Significant use of polynomial factorization demonstrates the power of algebraic methods in problem-solving.
• The solution, introduced by George Sierman in 1978, highlights the unsuspected relevance of polynomials in the dice problem.