CHAOS GAME PROBLEMS

 

This part of the homework may be a joint effort with another person if you like (put both your names at the top on the page you turn in).

 

PART ONE:

 

Go to the website

http://www.neuro.sfc.keio.ac.jp/~masato/jv/chaos/gasket/

You should notice two windows at the top of the page. In the left window, type in and the number of points as 100, and then click start. The program is playing the chaos game just as we attempted at the cabin. This is about the number of points that we superimposed on the transparency.

Try starting with 5000 points.

 

Question: At what number of points do you begin to see a reasonable likeness of the Sierpinski Gasket (this is the fractal pictured with the Homework Bonus Problem).

 

PART TWO:

 

Go to the website

http://math.bu.edu/DYSYS/applets/chaos-game.html. 

 

When you open the chaos game applet, you see a game board that consists of the Sierpinski triangle computed down to level 2, i.e., with nine smaller triangles. One of these triangles is colored green; this is the Target. You also see a point colored red at the lower right hand corner of the triangle. This is the Seed. Your goal is to move the Seed into the INTERIOR of the Target in as few moves as possible. Each time you make a "move" in the chaos game, this point will move to a new location in the game board. This becomes your current location.

 

The Moves: There are three possible moves in this chaos game. If you click on the top (red) vertex, your current location moves half the distance to the topmost vertex. Similarly, clicking on the lower left (blue) or lower right (green) vertex, moves the current location half the distance to that vertex. By a judicious choice of moves, you should be able to move your point into the INTERIOR of the Target in just 4 moves. This is indicated in the Best Score window. Your score (the number of moves you have made) is recorded in the window called Your Score.  In the upper left corner of the screen your successive moves are recorded as a series of red, green, and blue dots. When you succeed in moving your current location into the interior of the Target, you receive a message telling you so.

Resetting the Target: To replay the current game again (without changing Target), click on Try Again. To change to a new Target, click on Restart. The computer randomly selects a new Target.

The Algorithm: There is an algorithm for moving the starting point into the interior of the Target in exactly 4 moves, no matter what Target you start with. Your job is to discover this algorithm. You should be able to explain in advance how to move the Starting Point into the Target in a couple of sentences, no matter where the Target is located.

More difficult Targets: If you click on the Medium, Hard, or Master buttons at the top of the game board, you find chaos games with a Target at deeper levels of the Sierpinski triangle. The Best Score panel is appropriately modified. The algorithm that you developed at the Novice level should help you maneuver through these more difficult games.

Your Mission: Play the chaos game at the Novice level until you understand the algorithm that allows you to hit the target in exactly 4 moves. Write up a clear explanation of the algorithm that would allow a person reading it to carry it out with ease. As much as possible, find a general pattern to the algorithm so you do not have to discuss lots of different cases.  You and your partner should turn in this description of the algorithm and your best explanation of why you think it should work. Also explain how your understanding of the algorithm helps you see why the Chaos Game leads to the shape in the Bonus Question which is called Sierpinski’s triangle. (For example, what would happen if you set as a target one of the triangles missing in Sierpinski’s triangle, and why?)

Bonus: If you have time and interest, try the Medium, Hard, or Master levels, and describe how your algorithm should be modified to fit these games. As part of this additional challenge, try to explain how to tell what the minimum number of moves required is for any target at any level.