Walk This Way

In class on Tuesday, we discussed self-avoiding walks. Professor Davis wrote up the following code using Mathematica:

randomwalk = {{0, 0}};
Do[
p = RandomInteger[{1, 4}];
{x, y} =
randomwalk[[-1]] +
If[p == 1, {1, 0},
If [p == 2, {-1, 0},
If [p == 3, {0, 1}, If [p == 4, {0, -1}, {0, 0}]]]];
randomwalk = Append[randomwalk, {x, y}], {n, 1, 5000}]
ListPlot[randomwalk, Joined -> True]

This code gave us the following graph:

graph-5000

Andrew proceeded to use MatLab to create a similar graph, but it actually showed up each step. It was pretty cool.

ToH Discovery?

In class today, Adam and Elise came up with an amazing discovery. The entire explanation can be found on Adam‘s blog or Elise‘s blog.

With some inadvertent help from Andrew, I was able to see a pattern of sorts. To test out Adam and Elise’s equation, Andrew wrote up a code in MatLab to make sure it works. Something he stumbled upon, which I had mulled over in my head, is the differences between moves.

One-disk, 4-peg ToH will have no difference (per se, it’s the constant variable I suppose), two disks will have 2 more than the one peg, 3 will have 2 more, 4 will have 4. The pattern looks as follows:

#Disks: Move Differences

1: -

2: 2

3: 2

4: 4

5: 4

6: 4

7: 8

8: 8

Looking at this pattern and with Andrew’s code, it confirms that 9 and 10 pegs will have an 8 move difference from the prior disk amount. Disks 11 through 15 will have a 16 move difference. It follows a pattern that every time you add a disk, the move difference will double and appear one time more than the move difference before it. Basically, 2 apears twice, 4 appears three times, 8 appears 4 times, 16 will appear 5, 32 will appear 6 times, and so on. The thing I’m happiest about is Andrew’s code was able to prove my thought/theory correct.

I noticed another pattern as well that had me intrigued. Each disk moves a certain number of times. Having 6 disks or less, a disk will either move once, twice or four times (I know, I mentioned this in the post right before this one, but bare with). After 6, 8 comes into play because it’s the next move difference to appear. However, the pattern in which they appear is what caught my eye. Take a look:

1: 1

2: 1 2

3: 1 2 2

4: 1 2 2 4

5: 1 2 4 2 4

6: 1 2 4 2 4 4

7: 1 2 4 8 2 4 4

8: 1 2 4 8 2 4 4 8

I hope I can develope this thought more soon. With my upcoming schedule it’ll be tough. But I’ll find the time. Until next time ToH fanatics!

Tower of Hanoi and Gray Codes

The past couple of weeks we’ve been looking at Gray Codes and how they help with the Tower of Hanoi game. After painstaking brainstorms, Professor Davis realized that the Gray Codes indicate when a disk is moved, and not where it is moved to. With this epiphany, it made Gray Codes significantly easier to read and decipher. Using Gray Codes, we can find patterns the game “creates” with any amount of disks for the game.

The downside to Gray Codes is without a visual, you can’t really write up the code frame. It’s easiest to use when you can see where you are moving each disk. Last week, we discussed the ToH game with 4 and 5 pegs. Playing the game through the first couple of disks we reached the following:

n disks…. # of moves

….2………….3

….3………… 5

….4………… 9

From here, a pattern seemingly appeared with the number of moves. The moves followed 2, 2, 4, and the “logical” thought was the next move will be 17, since it doubled from 3 disks to 4. With some manual work, I found that 5 disks gives you 13 moves, and 6 disks gives you 17. This shot down the pattern idea.

One thing I did notice is each disk will be moved once, twice, or four times for three disks or more. The odd this is it doesn’t stay constant. For example (with disks being 1 to n, 1 being the largest), the pattern for 4 disks is 1, 2, 2, 4 (starting with disk 1 through disk 4 respectively). With 5 disks, the pattern is 1, 2, 4, 2, 4, and with 6 disks it’s 1, 2, 4, 2, 4, 4.

Tower of Hanoi, Pascal’s Triangle, Sierpinski

In class we discussed the game, the Tower of Hanoi. It’s a fairly simple game to play. There are three pegs (usually), with different sized disks on one peg. The object of the game is to move all the disks from one peg to another, one disk at a time, and a larger disk cannot be put on a smaller one.

In class, we discussed how do we know we’re finishing the game in the smallest amount of moves. The way to explain this is to play the game with three pegs. When playing the game with three disks, the least amount moves one can make is 7. We know this is the smallest amount because when played with two disks, the move amount is 3. Now, let’s have the number of moves for two disks be represented by , and the moves made by three disks represented by .

When you play with three disks, you automatically have to make three moves to get the top two disks on to another peg to make the third peg free for the third disk. Then move the third disk, and make the same beginning three moves, only in reverse, to get all disks on one peg. So, you make the same three moves twice, and move the final disk once, giving you:

.

No matter how you analyze it, this is the best mathematical explanation to show we’re making the least amount of moves.

Pascal’s, Sierpinski, ToH

At first glance of Pascal’s Triangle, Sierpinski’s Gasket, and the Tower of Hanoi graph, one may not see the resemblance. However, if you look at the ToH graph and Pascal’s Triangle side by side very closely, you can see a great resemblance. An even greater resemblance is seen between the Tower of Hanoi graph and Sierpinski’s Gasket. The two triangle setups are virtually identical. But why is this? Also, as I browsed through fellow classmates’ blogs, Matt Huberman made a nice little discovery in his September 10 post. When you have Pascal’s Triangle written up, if you add all the number in a line and ignore the last 1, it equals the least number of moves needed to complete a game of Tower of Hanoi with number of disks. Why is this? Did Pascal do this on purpose? I think it may be possible. I think Pascal was able to see something we can’t, and while creating his Triangle, he incorporated it with the Tower of Hanoi graph.

Collatz Complex Function

Yesterday in class, while looking at this graph:

I realized that it follows a retrograde motion, much like the planet Mars appears to make in correlation to Earth.