Ring Game

The Ring Game

THE RING GAME

Can you move all the rings from Peg A to Peg C?
Drag a ring to another peg. See what happens.
You can only move one ring at a time,
and you cannot place a bigger ring on a smaller ring.
How many moves will it take?
Can you solve the puzzle in as few moves as possible?
How many moves will it take if you start with 10 rings?
How many moves will it take if you start with 100 rings?

To answer these questions, it may help to make a table
that shows how many moves it takes to solve the puzzle
with any number of rings.
Play with 2 rings first.
Then enter into the table the minimum moves required to move 2 rings.
Play with 3 rings next.
Then enter the minimum moves required for 3 rings.
Continue till you see the pattern.
Fill in the column below under MOVES.
Look for a pattern that tells you how many moves 10 rings require.
Perhaps you can find a formula that will do the counting for you?
After you have correctly filled in the table, enter your formula on the f(n) row.

HOW TO USE THE APPLET
When you move a ring to another peg, without breaking a rule,
the Number of Moves counter will increase.
You may choose any number of rings to play with from 1 to 10.
Enter the number in the Number of Rings box, and press the ENTER key.
If you press the DUOTONE button, the ring colors will change
from rainbow to chocolate and butterscotch. Try it!

Play Toy

ASSIGNMENT

For 9 points, complete the list of terms in the table above .
For 3 points, enter in the f(n) box your formula for the nth term.
For 2 points,
enter in the add(n) box what you add to each term to find the next term.
This addition may be a constant or determined by n.
If determined by n, write the add(n) as an expression using n.
For 2 points, enter in the f(n+1) box your formula for term n+1.
This formula should look the same as the formula in the f(n) box
with +1 added to each n. Use ( ) where necessary.
For 3 points, use a little algebra to show that f(n) + add(n) = f(n+1).
Add the contents of the add(n) box to the contents of the f(n) box.
Do they equal the contents of the f(n+1) box?
Use your mouse to write your proof on the doodle board below.
For 1 point, show on the doodle board what f(100), the 100th term, equals.
Screencopy your ring game with 5 rings moved to another peg in the minimum number of moves and email it to your instructor.
Screencopy your completed table and email it to your instructor.
Screencopy your doodled proof plus the 100th term and email it to your instructor.

HOW TO PROVE YOUR INDUCTION
How do you know your formula works for any number of rings? Can you prove it?
Can you show that your formula is true for any whole number n?
Does it always output the minimum number of moves for any number of rings?
Here's how to prove it:

Show that your formula works when n = 1. (See how quick that was!)
Now ask yourself, what do you do to find the next number on the list?
Do you add or multiply the number of moves to find the next number of moves?
Is the number you add or multiply a constant or does it vary with n?
Write down your rule in English.
Translate your rule into an expression that uses your formula f(n).
For example,
if you always add 3 to find the next number of moves,
add 3 to your formula like this, f(n) + 3 .
This new formula computes the Next Term. Then f(n) + 3 = Next Term.
Now go through your original formula f(n) and replace each n with n+1.
Call this formula f(n+1).
Does f(n) + 3 equal f(n+1)?
If so, congratulations!
You have proven your formula works for all positive whole numbers!

Now can you find the 100th term?

ORDER OF OPERATIONS

SYMBOL	MEANING	EXAMPLE	RESULT
+	ADD	2+(2+1)	= 2+3 = 5
-	SUBTRACT	5-(3+1)	= 5-4 = 1
*	MULTIPLY	4*(7+3)	= 4*10 = 40
/	DIVIDE	6/3-2	= 2-2 = 0
^	EXPONENT	3^4	= 333*3 = 81
( )	PARENTHESES	2*(5-3)	= 2*2 = 4

When you enter your formula, remember the order of operations.

AN EXAMPLE

Notice that each row in the TERM column increases by 3.
After completing the list and scratching your head for a while,
you see that f(n) = TERM = 3*n - 2.
Enter this formula into the f(n) formula box.
It will turn blue and the comment will show approval.
Now prove that this formula works for any INDEX n:

When the INDEX n = 1, the TERM = 3*1 - 2 = 1.
So the formula works when n = 1.
Question: How do you do find the next number on the TERM list?
Answer: You add 3 to any TERM number to find the next TERM.
The number 3 stays constant.
Write down your rule: "Always add 3 to find the next TERM."
Now enter 3 in the add(n) box. The 3 will turn blue for true.
Your f(n) formula is TERM = 3*n - 2, so the NEXT TERM = (3*n - 2) + 3.
Now replace each n in your TERM formula with n+1
like so: TERM(n+1) = 3*(n+1) - 2. This is your f(n+1) formula.
Enter your f(n+1) formula in the f(n+1) box.
Does (3*n - 2) + 3 equal 3*(n+1) - 2 ? Prove it:
f(n) + 3 = (3*n - 2) + 3 = 3*n - 2 + 3 = 3*n + 1 is the Next Term.
f(n+1) = 3*(n+1) - 2 = 3*n + 3 - 2 = 3*n + 1 is TERM(n+1).
Yes! They are the same! Next Term = TERM(n) + 3 = TERM(n+1)

ANOTHER EXAMPLE

After we recognize this table as a list of squares,
the function formula is easy enough: Y = x^2.
It certainly works for x=1 because 1^2 = 1*1 = 1.
But how do we prove our formula is true for all positive integers?
In this table, Y is the name of the set of terms, which can also be written as f(x).
We need to find what we add to each Y to see the next Y?
So what is the next Y term?
In this example, the added term is not constant, but depends upon x.
Let's find the differences between each Y by subtracting each term from the next term.
Surprise! Doing this gives us the sequence of odd integers starting with 3 ...
3, 5, 7, 9, 11, 13, 15, 17, 19, ... .
This sequence of odd integers also has a pattern.
That pattern is also dependent on the indexes of X.
In this list, that pattern is written as 2*x+1, where x is the corresponding index.
Therefore, we know to add 2*x+1 to each Y term to find the next Y term.
Thus, our next term formula is Next Y = f(x) + add(x) = (x^2) + (2*x+1).
Next we write f(x+1) by adding 1 to each x in our original formula:
f(x+1) = Y(x+1) = (x+1)^2.
Does the Next Y = Y(x+1) ?
Let's see:
(x^2) + (2*x+1) = x^2+2*x+1 = (x+1)*(x+1) = (x+1)^2.
Yes, it does!
So, we have proven with a little algebra that our formula works for all positive integers.
Or symbolically, as mathematical inductionists would say,
we have proven that if f(x) is true then f(x+1) is also true,
where X is our set of indexes and Y is the set of terms dependent on X.

f(x) Þ f(x+1) is true for all x.
Voilà!

Comments:

From wHolt - 5/9/07 8:44 AM

When you enter your formula,
remember the order of operations.

SYMBOL	MEANING	EXAMPLE	RESULT
+	ADD	2+(2+1)	= 2+3 = 5
-	SUBTRACT	5-(3+1)	= 5-4 = 1
*	MULTIPLY	4*(7+3)	= 4*10 = 40
/	DIVIDE	6/3-2	= 2-2 = 0
^	EXPONENT	3^4	= 333*3 = 81
( )	PARENTHESES	2*(5-3)	= 2*2 = 4