Conway’s Game of Life ( Cellular Automata)

• Each cell with one or no neighbors dies, as if by solitude.

   ++            ++
  #     -->     .

• Each cell with four or more neighbors dies, as if by overpopulation.

  ++         ++
  #+    -->  .+
   +         ++ 

• Each cell with two or three neighbors survives.

   +          +
  #+    -->  #+ 

• For a space that is empty or unpopulated: Each cell with three neighbors becomes populated.

   +           +
   +    -->   #+
   +           +

https://playgameoflife.com

Polynomial of power \(n\)

• General Polynomial

\[x = a_0 + a_1 x+ a_2 x^2+ ... + a_{n}x^n\]

• Let’s use a random polynomial to general

\[y=2x^3-4x\]

• Calculate the first 7 entries of the sequence.

-2  8  42  112  230  408  658  

• Calculate derivative differentials to determine power of the polynomial

   x   y    Diff  Diff2 Diff3
   1   -2   
        >  10 
   2    8        >  24
        >  34           > 12
   3   42        >  36
        >  70           > 12
   4  112        >  48
        >  118          > 12
   5  230        >  60
        >  178          > 12
   6  408        >  72
        >  250
   7  658

• Set up to determine the coefficients

\[\eqalign{ x:& &ax^3 + bx^2 + cx + d &=& y\\ 1:& &a + b + c + d &=& -2\\ 2:& & 8a + 4b + 2c +d &=&8\\ 3:& & 27a + 9b + 3c + d&=&42\\ 4:& & 64a + 16b + 4c + d&=&112\\ }\]

• Convert to a solution matrix

\[\left[\matrix{1&1&1&1&|& -2\\ 8 & 4 & 2 & 1 &|&8\\ 27 & 9 & 3& 1&|&42\\ 64 & 16 & 4 & 1&|&112\\ }\right]\]

• Use Gaussian elimination to reduce the lower echelon

\[\left[\matrix{1&1&1&1&|& -2\\ 0 & 1 & \frac{3}{2} & \frac{7}{4}&|&-6\\ 0 & 0 & 1& \frac{11}{6}&|&-4\\ 0 & 0 & 0 & 1&|&0\\ }\right]\]

• Use back substitution to solve the unknowns

\[\left[\matrix{1&0&0&0&|& 2\\ 0 & 1 & 0 & 0&|&0\\ 0 & 0 & 1& 0&|&-4\\ 0 & 0 & 0 & 1&|&0\\ }\right]\]

• Convert to the polynomial

\[y=2x^3-4x\]

Confirmation by Trapezoida Rule

Bars and Stars:

Distribution of \(n\) items among \(k\) bins

• We need n stars (the objects)

• We need k-1 bars (to create k bins)

• Total positions: n + k - 1

• The number of ways =

\[\binom{n+k-1}{k-1} = \binom{n+k-1}{n}\]

• Example: 3 cookies distribute among 2 children

   ***|
   **|*
   *|**
   |***

\[\binom{3+2-1}{2-1}= \binom{4}{1}= \frac{4!}{3!1!}=4\]

Pigeon Hole Principle

There are 10 pigeons and 9 holes:

There is at least one hole with 1 or more pigeons.

If there are \(P\) individuals in the group and \(k\) boxes:

There are at least one box that will contain at least \(\left\lceil \frac{P}{k}\right\rceil\) objects

Chopsticks in a drawer

5 pairs of chopstick are thrown into a drawer and mixed up. With the draw of each chopstick what is the probability that a match is made?

\[\eqalign{Draw&&Permutation&&Sum&\quad Acc &Sum&&10000\\ 1& & \frac{0}{10} &=& 0.000 && 0.000\\ 2& & \frac{10\times 1}{10\times9} &=& 0.111&& 0.111 &&1126\\ 3 & & \frac{10\times 8\times 2}{10\times9\times 8} &=& 0.222&& 0.333& \\ 4 & & \frac{10\times 8\times 6\times3}{10\times9\times 8\times7} &=& 0.286 && 0.508\\ 5 & & \frac{10\times 8\times 6\times4\times 4}{10\times9\times 8\times7\times 6} &=& 0.254&& 0.762\\ 6 & & \frac{10\times 8\times 6\times4\times 2\times 5}{10\times9\times 8\times7\times 6\times 5} &=& 0.127&&1.000\\}\]

Experiment: 10 chopsticks (5prs) selected to make 1 pair

How many chopsticks do you need to pick before you definitely have a matching pair?

\[\tiny \matrix{ Sticks & Unpaired&&Calc & Not & Single & Doble & Triple \\ Picked & Permut& &Fraction & Paired & Pairs & Pairs & Pairs \\ 0 &\frac{10}{10}&=&1.000 &10000\pm 0.0 & 0& 0 & 0 \\ 1 &\frac{10}{10}&=&1.000 &10000\pm 0.0 &0 & 0 & 0 \\ 2 &\frac{10\cdot8}{10\cdot9}&=&0.889 &8890.8\pm24.7&1109.2\pm24.7& 0 & 0 \\ 3 &\frac{10\cdot8\cdot6}{10\cdot9\cdot8}&=&0.667 &6644.0\pm51.1&3358.0\pm51.1 & 0 & 0 \\ 4 &\frac{10\cdot8\cdot6\cdot4}{10\cdot9\cdot8\cdot7}&=&0.381 &3810.6\pm74.6 & 5718.2\pm66.6 &471.2\pm 26.3 & 0 \\ 5 &\frac{10\cdot8\cdot6\cdot4\cdot2}{10\cdot9\cdot8\cdot7\cdot6}&=&0.127 &1292.2\pm 18.3 & 6311.0\pm 65.3 & 2396.9\pm67.1 & 0 \\ 6 &\frac{10\cdot8\cdot6\cdot4\cdot2\cdot0}{10\cdot9\cdot8\cdot7\cdot6\cdot5}&=&0 & 0\pm 0& 3812\pm 51.9 & 5692.6\pm 28.7 & 495.4\pm 32.8\\ }\]

Structures

• linked nodes: A list of neighbors

  a = Node.new(0)
  b = Node.new(72)
  c = Node.new(144)
  d = Node.new(216)
  e = Node.new(288)
  f = Node.new(nil)

  a.neighbors([b,c,d,e,f])
  b.neighbors([a,c,d,e])
  c.neighbors([a,b,d,e])
  d.neighbors([a,b,c,e])
  e.neighbors([a,b,c,d])
  f.neighbors([a])

• Connectivity Matrix:

  a matrix to map connections to the next

\[\matrix{&\tiny a &\tiny b&\tiny c &\tiny d&\tiny e &\tiny f\\ \tiny a &0&1&1&1&1&1\\ \tiny b &1&0&1&1&1&0\\ \tiny c &1&1&0&1&1&0\\ \tiny d &1&1&1&0&1&0\\ \tiny e &1&1&1&1&0&0\\ \tiny f &1&0&0&0&0&0\\ }\]

• Connectivity matrix records number of steps needed

     [,1] [,2] [,3] [,4]
[1,]    0    1    1    1
[2,]    1    0    1    0
[3,]    1    1    0    1
[4,]    1    0    1    0

     [,1] [,2] [,3] [,4]
[1,]    3    1    2    1
[2,]    1    2    1    2
[3,]    2    1    3    1
[4,]    1    2    1    2

Chromatic number of a graph

Assign colors to vertices ensuring no two connected vertices share the same color—a concept called proper coloring.

• Start by coloring the vertex with the highest degree.

• Continue coloring other vertices, using the fewest colors possible without violating the adjacency rule.

• The chromatic number is the total number of unique colors used once all vertices are colored properly.

Euler’s test for planarity

Planar if:

\[v-e+f = 2\] *

\[\forall v\ge 3:\left\{\begin{matrix} e\le 3v-6 &\qquad planar\\ e\gt 3 v-6 &\qquad nonplanar\\ \end{matrix}\right.\]

\[\begin{matrix} shape & v & e & f & eulers & Modified\\ butterfly & 5 & 6 & 3 & 2 & 6\lt9\\ K_4 & 4 & 6 & 4 & 2 & 6 = 6\\ K_5 & 5 & 10 & 6& 1 &10 \gt 9\\ K3,3 & 6 & 9 & 6 &3 &9 \gt 12\\ \end{matrix}\]

Ruby code

class Node
   attr_accessors :value, :leftnode; :rightnode

   def initialize(value,left,right)
      @value = value
      @leftnode = left
      @rightnode = right
   end
   
   def to_s
      @value.to_s
   end
end