Thread Rating:
  • 0 Vote(s) - 0 Average
  • 1
  • 2
  • 3
  • 4
  • 5
Mathematical Proof Megathread
Okay, this just might be the geekiest thread on the entire forum (for now :lol: ). As the title suggests, it's a place to post and discuss mathematical proofs of things. 

I'll start off with one related to the "Tower of Hanoi" puzzle, which I'm sure you've seen before. The object is simply to move the tower from the left-hand peg to the right-hand peg, by moving one disc at a time, without ever putting any disc on top of another disc that's smaller than it: 

[Image: hhurRz2.jpg]
(Source: Evanherk; View licence terms)

How many moves does it take to do? Well, the answer to that is as follows:

If you have N discs, then the minimum number of moves needed to solve the puzzle is 2N-1. (For example, the tower in the picture has 8 discs, so the puzzle can be solved in a minimum of 28-1 = 255 moves)

To prove this, I'm going to use mathematical induction. What this means is, I will: 
  1. Prove that the statement is true for N=1, and then; 

  2. Prove that, whenever it's true for one integer (say, N=K), then it's also true for the next integer (i.e. N=K+1). 

Basically, think of this "mathematical induction" technique like a line of dominoes: your finger causes the first domino to fall, and then each domino causes the next domino to fall - so, all of the dominoes must fall at some point.   

So, here's the proof, which I'm cross-posting from (where I originally posted it): 
Proof Wrote:Base case (N=1): Obviously, the 1-disc Tower of Hanoi can be solved in one move: just move the lone disc from the left-hand peg to the right-hand peg :P . Thus, the minimum number of moves is 1 (which is equal to 21-1).

Inductive hypothesis: Assume that the statement is true for some arbitrary integer N=K. Now, we want to show that it is also true for N=K+1.

Now, in order to solve the K+1-disc Tower of Hanoi, we need to do it in three stages:
  • Move the top K discs from the left peg to the middle peg;
  • Move the bottom disc from the left peg to the right peg;
  • Move the top K discs from the middle peg to the right peg.
The first stage requires 2K-1 moves (by the inductive hypothesis). The second stage requires one move (obviously). The third stage requires 2K-1 moves (again, by the inductive hypothesis). So, the total number of stages is:

(2K-1) + 1 + (2K-1) = 2*2K - 1 = 2K+1-1

Hence, if the statement is true for some arbitrary integer N=K, then it is also true for N=K+1. Since the statement is true for N=1, it is true for all positive integers by mathematical induction.          

So, does anyone have any questions related to this proof, or any way they can expand upon it? Or does anyone have any other mathematical proofs of anything, that they want to share?
[Image: CJ_userbar.png]

Board Information and Policies
Affiliation | Coffee Credits | Member Ranks | Awards | Name Changes | Account Deletion | Personal Data Protection

(Thanks to ObsessedwithBirds for the avatar and sig!)
Pyrite Wrote:"It's called the Island of Sodor, not Hodor."

(In response to me misreading "Game of Thrones" as "Game of Thomas")
My Awards
x1 x1 x2 x2 x5 x3 x1 x3 x6
My Items

Forum Jump:

Users browsing this thread: 1 Guest(s)