You, and the members of your team, have walked into a vortex and find yourselves transported into another dimension.
It is not a dimension of sight and sound, but one of fantasy. Whoa doggies! What is going on! This don't look like Kansas!
You begin to whimper about how good you've been and how you don't deserve to be away from family and friends when suddenly a dazzling figure appears in front of you. Oh my gosh! Baroooom! (thunder and lighting) A voice speaks that seems to come from all directions at once.
"Bow down you whimpering slobs, I am the God of the Towers!"
You immediately fall to the ground awaiting what will surely
be a painful death.
However, the God speaks once more.
"You have been chosen to go on a quest.
If you succeed at that quest you, and the rest of the world, will be allowed to continue its miserable existence.
However, if you fail, a painful death is waiting for you and those of your kind".
In order to save the yourselves and the world you must complete the following four-part quest:
1 Find a relationship in the Towers of Hanoi puzzle that will predict the minimum number of moves for a set of rings, based on the minimum number of moves for one ring less (this is called a recursive relationship).
2 Find a relationship in the Towers of Hanoi puzzle that will predict the minimum number of moves for a set of rings, based solely upon the number of rings.
3 Sharpen your skills in mathematical induction.
4 Finally, save the world by using the recursive relationship in #1 to prove your conjecture in #2 by mathematical induction.
Part #1.
First of all you must choose a name for your team (e.g., Ninja Turtles, Artichokes…).
Now that you have a team name, go to the Tower of Hanoi puzzle. Each of you spend some time playing with the Towers of Hanoi puzzle while the others create a table with number of rings 'n' as one column, and number of moves 'm' as the other column. Do this for each set of rings up to 7 (press the '+' sign for more rings). Be sure that 'm' to is the minimum number of moves!
Once you have gathered your data, note that the table defines a function, say M, which assigns for each value n a value m (how do you know that it is a function?).
Now you must define M in a recursive manner. That is, define M(n) in terms of M(n-1). To do that you must recognize a relationship between the number of moves for n rings and the number of moves for n - 1 rings.
Once you have that relationship, check your answer with the instructor.
So what kind of a function is this? (answer).
You now must find a new relationship between the number of rings and the minimum number of moves. Let's call that G(n).
Instead of G(n) depending on G(n – 1), you want to find a relationship where G(n) is a function of just 'n'.
For example G(3) = 7 = 2*3 + 1, so we might try G(n) = 2n + 1. But that function only works for 3 rings! Darn! Try again – it has to work any number of 'n' rings.
Once you have that relationship, check your answer with the instructor.
Part #3
Mathematical Induction Review. This part of the exercise may be optional depending on the knowledge you have on tap. You can find good information on mathematical induction by visiting http://www.cut-the-knot.org/induction.shtml. If you are rusty, you might want to try one of the examples of an induction proof on that web page where an answer is provided - you will need to be able use induction in Part 4.
Part #4
Take your conjectures from Part #1 and #3 and write out the functions your have. Now, using mathematical induction prove that the second conjecture is true (i.e., G(n) where you can predict the minimum number of moves based directly on the number of rings). You will need to use the results of recursive function, M(n) to prove the non-recursive function G(n).
Using your calculators and the function you came up with, how many moves is required to move 12 rings? Check your answer using the Tower of Hanoi puzzle (make sure you set the solution speed to its maximum!).
As homework you are to write a 200 word minimum reflection on what you learned in this exercise. Include any observations you may have made on how to move the rings using a minimum number of moves (e.g., how did you decide where to move the first ring?). Also include what you learned about recursion and mathematical induction. Be sure to mention how we know (or don't know) that using mathematical induction can be used to 'prove' something.
Email your reflection to me.