Tower of Hanoi

Please view this website for the application:

http://www.mathsisfun.com/games/towerofhanoi.html

Tower of Hanoi

The Tower of Hanoi puzzle was invented by the French mathematician Edouard Lucas in 1883. We are given a tower of eight disks (initially four in the applet below), initially stacked in increasing size on one of three pegs.

The objective: To transfer the entire tower to one of the other pegs (the rightmost one in the applet below), moving only one disk at a time and never a larger one onto a smaller.

This puzzle touches on the topic of recursive function and stacks, and recurrence relations.

Recursive solution

Let us call the three pegs Src (Source), Aux (Auxiliary) and Dst (Destination). As you solve the problem, sooner or later the bottom disk will have to be moved from Src to Dst. Then, the remaining disks will then have to be stacked in decreasing size order on Aux. After moving the bottom disk from Src to Dst these disks will have to be moved from Aux to Dst. Therefore, for a given number N of disks, the problem appears to be solved if we know how to accomplish the following tasks:

1. Move the top disk from Src to Aux (using Dst as an intermediary peg)
2. Move the bottom disk from Src to Dst
3. Move the smallest disk from Aux to Dst (using Src as an intermediary peg)

Suppose there is a function "Solve" with four arguments - number of disks(N) and three pegs (source, intermediary and destination - in this order). Then the body of the function might be as follows:

 Solve(N, Src, Aux, Dst)

if N is 0        exit

else 

Solve(N-1, Src, Dst, Aux)

Move from Src to Dst

Solve(N-1, Aux, Src, Dst) 

This actually serves as the definition of the function Solve. The function is recursive in that it calls itself repeatedly with decreasing values of N until a terminating condition (in this case N=0) has been met. It is indeed amazing how this puzzle could be solve by a method of such simplicity.

When there are 3 disk, the function thus translates into

1. Move from Src to Dst
2. Move from Src to Aux
3. Move from Dst to Aux
4. Move from Src to Dst
5. Move from Aux to Src
6. Move from Aux to Dst
7. Move from Src to Dst

Of course "Move" means moving the topmost disk. For N=4 we get the following sequence

1. Move from Src to Aux
2. Move from Src to Dst
3. Move from Aux to Dst
4. Move from Src to Aux
5. Move from Dst to Src
6. Move from Dst to Aux
7. Move from Src to Aux
8. Move from Src to Dst
9. Move from Aux to Dst
10. Move from Aux to Src
11. Move from Dst to Src
12. Move from Aux to Dst
13. Move from Src to Aux
14. Move from Src to Dst
15. Move from Aux to Dst

Recurrence relations

Let T_N be the minimum number of moves needed to solve the puzzle with N disks. From the previous section, we can see that T₃ and T₄ are 7 and 15. One can easily convince oneself that T₂ is 3 and T₁, 1 of course. It does not take one to be a trained mathematician to notice that T₀=0.

A general formula:

The recursive solution above involves moving twice (N-1) disks from one peg to another and making one additional move in between. It then follows that

T_N<=T_N-1+1+T_N-1 = 2T_N-1+1

The inequality suggests that it might be possible to move N disks with fewer than 2T_N-1+1 moves, which is actually not the case. Indeed, when the time comes to move the bottom disk (N-1) disks will have been moved from Src to Aux in at least T_N-1 moves. Since we are trying to use as few steps as possible, we may assume that that portion of the task took exactly T_N-1 moves. It takes just one move to move the biggest disk from Src to Dst. One then needs exactly T_N-1 more steps to finish the task. Therefore the minimum number of moves needed to solve the puzzle with N disks equals T_N-1 + 1 + T_N-1 = 2T_N-1 + 1 moves.

In other words,

T_N = 2T_N-1 + 1

Thus we can define the quantity T_N as

T₀ = 0

T_N = 2T_N-1 + 1 for N>0

From here, we may compute T₁ = 2T₀ + 1 = 1, T₂ = 2T₁ + 1= 3, T₃ = 2T₂ + 1 = 7 and so on sequentially. The above expression is known as a recurrence relation which is but a recursive function. T_N is defined in terms of only one of its preceding values.

Returning to the definition of T_N, define S_N = T_N + 1. Then S₀ = 1 and S_N = T_N + 1 = (2T_N-1 + 1) + 1 = 2T_N-1 + 2 = 2(T_N-1 + 1) = 2S_N-1. Which is to say that S_N could be defined as

S₀ = 1

S_N = 2S_N-1 for N>0

The latter is solved easily in the non-recurrent form of S_N=2^N. Wherefrom

T_N = 2^N-1 for N>=0

Enjoy life as it comes,

skk

Yes, I'm back for a second installment of doing card tricks with math.

I just found a cool one on the net. Here goes:

The spectator cuts a deck in half,chooses a card from one pile, memorizes it and places it on top of the pile. He then proceeds to place the other on top to "mix the cards". After discarding some cards along the way, the spectators card is magically found!

This trick calls for a certain aptitude in dealing and handling cards. The prerequisite is that you will have to try to cut the deck into almost equal halves, and this requires practice.

Procedure:

Cut a deck in halve, or as close to as you can.

Have the spectator choose one pile and pick any card he wishes from it.

Have him place the card on the top of the pile.

Place the other pile upon the one chosen to seemingly "lose the card."

Have the spectator deal the cards into four piles, naturally, there will be 13 in each.

Then flip over all the piles and ask him if his card is in it.

Discard the three piles without.

Now, deal the pile of 13 into four piles again.

There should be one pile of four cards, discard it.

Now we have three piles of three.

*The middle card of the middle pile is theirs

Using your own creativity, reveal the magic to your spectator and blow him away.

Troy

Mind Reader

Let RiverBoat Lil read your mind!

Steps
1. Pick a two digit number
2. add the two digits together
3. subtract the answer from the 2 digit number
4. click the "click here"
5. look at the picture for your number.
6. The mind reader is able to predict the picture for your number

http://www.murderousmaths.co.uk/games/mindreader/index.htm


it really works !!










How does it work??!!

For every 2 digit number, subtracting the sum of the two digits from the number, would give a number that is a multiple of 9.

Don't believe?
Take 88 for example
8 + 8 = 16
88 - 16 = 72!

Still not convinced?
Take 64 for example
6+4 = 10
64-10 = 54!

Amusing.. ain't it?

PS: Look carefully at the pictures-- all the pictures for multiples of 9 are the same!!
Kah Keong

The Importance of the EXPONENTIAL Function!

Ok. My mum stumbled upon this video while trying to kill time. Since its "The Most IMPORTANT Video You'll Ever See", I thought it would be worth sharing.

This 8 part series talks about the real life implications of the exponential function. May be a bit boring at first - not to worry.. Sit back and let the sheer power of the exponential sweep you away.



Ok fine.. I've only watched the first one (as of this post..).

Takeaways from this video:

1) Doubling time: 70 (aka ln2 x 100%) / percent growth per unit time (e.g. year)

2) Hence for something to double in 10 years, growth per year is around 7%.

3) If *something* increases at a constant % per unit time, by the next doubling time, total quantity of *something* would have more than doubled the sum of *something* before the previous doubling time.

Ok! Watch the video for yourself! (and you would probably have a better understanding compared to the random blabbering above)

Chao Xu

Alright, so math is a boring subject...but we can't deny the fact that it can be widely applied in many aspects of life. today, I'll introduce a simple magic trick that demonstrates how math can be applied.

The Binary Card Trick O_O

A 2 3 4 5 6 7 8 9 10 J Q K jOkEr

Effect:
Ask anyone to call a number between 1 to 15, miraculously, you can pull out a card combination of such a number!

Math behind it:
Every number between 1 and 15 has a unique representation as a sum of some collection of the numbers 1, 2, 4, and 8. (To see which collection, just take the given number and successively subtract the largest number of 1, 2, 4, and 8 that is less than the given number. That number is part of your collection. The subtraction yields a new number; now repeat the process with this number, over and over, until you get 0.) The collection of numbers you obtain reveals the binary decomposition of the given number into sums of powers of two (in contrast to the usual representation of a number into sums of powers of ten).

Procedure:
Before the trick starts, pick an Ace, 2, 4, and 8 and put them on top of the deck, and then put the deck in your pocket.

Then when a number between 1 and 15 is called out, take the binary decomposition of the number, and use that to determine which of the first four cards you will pull out.

A technical trick with supernatural effects.
Ciao

Troy

Easy Multiplication

Do you believe you can multiply things faster than a calculator?
This video will teach you how!!



Works only for numbers below 100 though

Kah Keong

Roman Numerals

Today's post shall be on Roman numbers.

Roman numerals is the numeral system of Ancient Rome. It is based on the letters of the alphabet which are combined to signify the sum of their values.

For example, the first ten numbers in Roman numerals would be:

Roman: I, II, III, IV, V, VI, VII, VIII, IX, X
Numerical: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10

From here we can see that I means 1, V means 5, and X means 10. Placing an I in front of another letter means deducting 1 from the value of the 2nd letter, like how IV is 5-1=4 and IX is 10-1=9. Placing 1 or more Is behind another letter means adding that number of '1's to the value of the other letter, like VI is 5+1=6, VII is 5+2(1)=7.

There is no zero in Roman numerals.

The Roman numerals is the "cousin" of the Etruscan numerals. The letters used to represent the different values actually originate from non-alphabetical symbols, with which over time, the Romans eventually identified the symbols with letters of their Latin alphabet. No doubt, despite this numbering system being that of ancient times, it is still used in our lives today; they are most commonly seen in numbered list, clock faces, pages preceding the main body of the book etc.

Other than I, V and X, there are also other letters used to represent the different values:

L - 50
C - 100
D - 500
M - 1000

However, the system we used today is not what this numeral system originated as. Initially, the Romans only used capital letters, I II III etc. However, in the Middle Ages, the system was modified to eventually produce the system that we used today, which includes minuscule(lower case) letters. It was then that these minuscule letters were developed, e.g.: i, ii, iii etc.

It is interesting to note that people substituted the last i of a numeral with j, making 8 viij, etc.. This is done so as to prevent tampering with numbers after they have been written, for example in medical prescriptions, etc.

Also, for large numbers(in the thousands), a bar can be placed above the base numeral, or parentheses placed around it. This indicates the multiplication of 1000.
As such:
_
V or (V) represents 5000, etc..

Deeper into its roots:

Roman numerals originally intended as independent symbols, derived from notches on tally sticks.

'I' was meant to be a notch scored across the stick, with every fifth notch being a double cut, i.e. Λ, V and a few other variations, while every tenth was a cross cut, X. 50 was written as V with an extra stroke, with its variations being N, И, K, Ψ, ⋔, etc.. However, it was most often written as ᗐ, which was later 'flattened' and eventually becoming a symbol similar to 'L'. Similarly, 100 was intended as an addition of a stroke to X, Ж, which evolved to ƆIC, finally was abbreviated to C. 500 was intended as a Ɔ superposed on a ⊢, producing D, 1000 was a circled X, Ⓧ becoming M after the Middle Ages.

So the numbers was written as:
IIIIΛIIIIXIIIIΛIIIIX...

The above produced a positional system, like how 13, being the 3rd notch after the first ten, which could be abbreviated as X, became XIII and thus the positioning of this unique system.

Fractions:

Fractions in Roman numerals were based on 12, due to its divisibility (12=3x2x2), making it easier to handle the common fractions of 1/3 and 1/4. A dot '.' indicated a "twelfth", and 6 of these makes a half, denoted by S. As such, the Roman representation of fractions are as follows:

1/12 -> .
2/12 = 1/6 -> :
3/12 = 1/4 -> ∴
4/12 = 1/3 -> ∴
5/12 -> :•:
6/12 = 1/2 -> S
12/12 = 1 -> I
From from 7/12 onwards, it is just the addition of the dots behind S, like 10/12 = 5/6 is represented by S::


Ok, that's all for Roman numerals..

Cheers,
Kah Keong