Tower of Hanoi 4 peg

In class on Sept. 30, 2008, we had an interesting session. Elise and Adam lead the class with their recursive patterns for solving the 4 peg system.  The concept was that a 3 peg sytem can be used to give the answer for the minimal amount of moves needed to solve a 4 peg system. Elise came up with a mathematical calculation process to attain the least amount of moves.

{Let P denote the number of pegs and let the number of disks be at least .  We attempted to formulate a function .  P in the function denotes the number of available pegs. P-k denotes the number of disks moved.  found that the opening moves would always be   Let A denote the first parameter in the function and B denote the second.  Then, the function evaluates to the least number of moves to move B disks with A available pegs.  The function can be viewed as a sequence which ends when there are no more empty pegs.} from elise blog….

With the help of the class we were able to make logical sense of our classmates suggestions.

Tower of Hanoi

The edges of the graph are the legal moves of a single top disc. The graph is simple, connected and on a plane. For the Pascal triangle the odd numbers are the legal move and can be connected to form simple, connected triangle on a graph.

Tower of Hanoi

In playing the Tower of Hanoi for a 3 peg with n amount of disk. In order to get the least amount of moves, in class, we derived the formula
M(n) = 2*m(n-1) + 1
M(n)= m(n-1) + 1+ M(n-1)

M(n)= # of moves for n disk. This formula hold true for all n disks on a 3 peg. This formula simple states that you move twice the number of moves made for n-1 disks. Then since we have a extra disks that is the +1 move for the game.

Tower of Hanoi, Pascal triangle and sierpinski triangle

I realized that the Sierpinski graph is obtained from drawing a closed equilateral triangle. If we delete the middle triangle and do the same for the subtriangles we end up with the same graph has the tower of Hanoi. The pascal triange Graph if attach all the odd numbers forming triangles we have the same graph has the tower of hanoi for a 3 peg with n amount of disks.

Random walk 10/28/08

For class today we attempted to use Mathematica to come up with a simple code to write a random path with the use of probabilities. This is the code Gary, Matt and I came up with:

(*This makes the first step of the random path.*)

randompath = {{0, 0}};
(*This defines the neighbors of the point{x,y}.*)

left[{x_, y_}] := {x – 1, y};
right[{x_, y_}] := {x + 1, y};
up[{x_, y_}] := {x, y + 1};
down[{x_, y_}] := {x, y – 1};
lasteightsites = randompath[[-Min[{Length[randompath], 8}] ;; -1]];
neighbors[{x_, y_}] := {left[{x, y}], right[{x, y}], up[{x, y}],
down[{x, y}]};
beenthere[{x_, y_}] := Intersection[neighbors , lasteightsites];
p = If[Length[beenthere[{x, y}]] == 4, 0,
1/(4 – Length[beenthere[{x, y}]])];

basically the code start out at the point (0, 0).

Then define (x, y) for the four neighboring points. (left, right, up, and down)

After defining the neighboring points we have to come up with a code that defines the last eights sites visited in the walk and then we intersect those points with the neighboring points. This gives us the values of the (x, y) we have been in the random walk.

The probability of the random walk is 1/ 4 -the length of the been there (x,y) values.

Random walk1

In class we were introduced to the random walk concept. Elise came up with a concept that:

n= number  of steps

m= number of vertices

x= number of open vertices at each steps

Have been           Have not been at a place

P(x)= n/m           P(1-x) = 1-n/m

x >= 3   creates four mini squares in a pane

P(x=1) = (1- n/m)

P(x=2) = (1- n/m)^2

P(x=3) = (1- n/m)^3

if it is on a vertices a square we get (1- n/m)^0

has n goes to infinity.

Expected values

E(x) = 3 (P(x=3)….)) + 2 (P(x=2)….)+ P(x=1)…..)

random walk 2^n is linear

E(x)^n = approximation # of random walk

Prob. min memory path ending

In our class discussion we attempted to find the min memory path ending for the random walk graph. We decided it was 7 since if we start at a point there is only four possible moves left, right , up, dpwn(l,r,u, d). The branches of the four possible moves then create there own three possible moves since it cannot go back to the first move.

We then attempted to find a probability for getting seven has the min memory path ending. We tried to use Bernolli Trial. Which states that sqrt(p (1-p)).

p=(1/4)^7.

4^7= 16384

p= (1/16384)

sqrt [(1/16384)* (1-(1/16384))] = 0.0078

We then tried a different method:

P(x) = (0,1, 2, 3, 4, 5, 6, 7)

the possible move for the first is 4, any other move after is 3, and r = 20,000 (the mathemaitca program attempted a walk for 20, 00 step).

possible move 1st choice 2nd choice

                4  *   [(1/4)   (1/3)^6]

we have to repeat this 20,00o times since it is a walk of 20,000 steps.

Random Walk

Two weeks ago we attempted to do random walk starting at zero. Prof. Davis created a Mathematica program to show a random walk graph. He kept changing the values to get the session time it took to walk. Starting it a zero there is only four possible moves left, right, up or down (l, r, u, d).

Since random walk = {(0.0)}

a= random walk (1-> 4)

(x, y) = last point n random walk

(-1, 0) if a =1

(1, 0) if a =2

(0, -1) if a = 3

(0, 1) if a =4

By looking at the last four steps in the random walk add (x, y) to random walk if it does not intersect with the last four points other wise do not. In doing this we are trying to keep a track of the last four points we were located on. We next attempted to calcuate a program that not only check the last four points but also if one intersect with the new (x, y) value we simple check the other possible moves available and move to the next one.

Hello world!

Welcome to WordPress.com. This is your first post. Edit or delete it and start blogging!