The Cups and Stones Counting Problem, The Sierpinski Gasket, Cellular Automata, Fractals and Pascal's Triangle

摘要

In 1992 Barry Cipra posed an interesting combinatorial counting problem. In essence, it asks for the number S_(k,σ) of configurations possible if a circular arrangement of k cups, each having σ stones, is modified by applying a particular transition rule that changes the distribution of stones. Carbonara and Green (1998) studied the integer sequence S_(k,1) and presented a recursive formula for it: S_k = 2S_(2~r+1) + 2~(r-j)S_(d+1)+ d2~r - 2~(r+1) where k = 2, + 1+d>2, r ≥ 0 and 0 < d ≤ 2~r. Ettestad and Carbonara (2010) noted that this system is a finite Cellular Automaton, showed two interesting non-recursive formulas for S_k, and claimed that the shape of the non-zero terms in the reduced matrix for the Cups and Stones Counting Problem (CSCP) with 2~n + 1 cups is equivalent to the Sierpinski Gasket. We are proving that claim in this paper. In doing this, we extend the classic definition of the Sierpinski Gasket to discrete geometric figures.