# The Chaos Game

The Chaos Game is played on a board in the shape of a Sierpinski Triangle, this is a fractal shape that is made by dividing an equilateral triangle into 4 smaller triangles, then removing the central one -- but then repeating this procedure on the triangles that remain: forever!

A Sierpinski triangle:

The game is played as follows. You start with a "bug" at one of the corners of the (big) triangle, which we will label N, E and W (for North, East and West). A turn consists of moving your bug half way to any of these three vertices. The goal is to move your bug into a pre-specified small triangle in the fewest possible moves. As an example, how would you move the red bug into the blue triangle in this instance of the Chaos game? (This game is being played on the 2nd iteration of the process of creating a Sierpinski triangle.)

Harder versions of the game are played on successive stages of the Sierpinski triangle.

A Java applet is available at http://math.bu.edu/DYSYS/applets/chaos-game.html that allows one to play the Chaos game on the board above, as well as on the next three iterates. The puzzle is this: find a winning strategy for the Chaos game. That is, develop a strategy that moves your bug into the designated triangle in the fewest moves. The game above can be completed in 4 moves.

A hint.