> `b_5@ "bjbj22 ":XX
<
:2
eeeH:J:J:J:J:J:J:$;RM>n:CC"eCCn::C
H:CH:B1nT89
:+
M.\9 H::0:9D>{j>@99>9te=Seeen:n:
HYPERLINK "file:///C:\\PEER3.NSF\\Templates.forms\\index.html" TAMU NSF GK12 HOME
Towers of Hanoi
Lesson Summary:
This enrichment activity is meant to be used by a math club or math camp, or similar. In this activity, students solve the puzzle of the Towers of Hanoi by trying to find the least number of moves needed to get disks from one tower to another, without ever putting a smaller disk under a larger disk. Students will find the least number of moves when dealing with 1 disk, 2 disks, 3 disks, and four disks, and then will guess the equation relating number of disks to minimum number of moves.Subject:
Math: Numbers and Operations, Algebra, Reasoning and Proof
Grade Level:
Target Grade: 7
Upper Bound: 8
Lower Bound: 6
Time Required: 30 minutes Authors: Graduate Fellow Name: Candace DiBiano Teacher Mentor Name: Stacey Webb Date Submitted: 5/27/06Date Last Edited: 5/27/06Lesson Introduction / Motivation:
Give the students the HYPERLINK "Towers%20of%20Hanoi%20Worksheet.doc" Towers of Hanoi Worksheet, and read the italics section of the worksheet that coins the myth out loud. This should get students interested in the puzzle.Lesson Plan:
Preparation: To prepare for this lesson, print out enough HYPERLINK "Towers%20of%20Hanoi%20Bases.doc" Tower of Hanoi Bases so that there will be one set of three circles per group of students in the class. Cut the Tower of Hanoi Bases sheet into horizontal strips, so you have slips of paper that look just like this:
SHAPE \* MERGEFORMAT
Next you need to gather a mediumsized collection of pennies, nickels, dimes, and quarters, to use as the disks youre moving from tower to tower.
Finally, you need to have a firm understanding of how to solve the Tower of Hanoi puzzle yourself quickly. After youve finished reading this entire lesson plan, go to HYPERLINK "http://mazeworks.com/hanoi/" http://mazeworks.com/hanoi/. Put the Speed indicator on this webpage down to a low setting, and then click on the Solution button. The computer will then show you how to solve the Towers of Hanoi Puzzle with three disks. You can then change the number of disks to see the solution to the puzzle for 1, 2, and 4 disks. Once you are comfortable with the computer version of each solution, try to solve each yourself without the computers aid. Once you can do that, you are ready to teach your students about the Towers of Hanoi!
After the Lesson Introduction/Motivation, go over with the students the rules of the puzzle. Students will be given a number of different sized disks (coins), which they must put inside the leftmost of their three circles, with the disks stacked on top of each other, largest on bottom to the smallest on top. The goal of the game is to get all the disks stacked in the rightmost of the three circles, again with the largest on the bottom to the smallest on top. However, there are two catches. You can only move one disk at a time, and you cannot place a disk on top of another disk that is smaller than it. Thus you can only place a disk on top of a second disk if the second disk is larger.
Have the students start by just using one disk, which will be a single quarter coin. Ask them how many moves it takes to move the quarter from the leftmost tower to the rightmost tower. The answer should be, just one move. Have the students will this out on their HYPERLINK "Towers%20of%20Hanoi%20Worksheet.doc" Towers of Hanoi Worksheet.
Now give the students a nickel. Tell them to place the quarter in the leftmost circle, and to put the nickel on top of it. Ask students how many moves it will take to make the tower on the rightmost circle. The answer should be three moves. Have them fill this out on their worksheet as well.
Now give the students a penny. Set them loose to figure out the minimum number of moves they can make to move a tower of a quarter, a nickel, and a penny from the leftmost circle to the rightmost circle. When the students get it in 7 moves, have them demonstrate their method to you. If their method follows the rules, give them a dime, and tell them to solve the puzzle using four disks now.
With four disks, the minimum number of moves to move the tower from the leftmost circle to the rightmost circle is 15. Once all students have solved the puzzle for four disks and filled out their worksheet, stop the class and go up to the board.
Make a table on the board that has Number of Disks on the right, and Minimum Number of Moves on the left. Tell the students that they need to guess a formula for Minimum Number of Moves based on Number of Disks.
Help the students guess this formula as needed. The formula is:
Let n = the number of disks, then:
Minimum Number of Moves = 2n  1
Lesson Extension:
After this lesson, you can inform the students that there is no known formula for the minimum number of moves to get disks from one side to the other when using four towers instead of three. You could have the students research this further.
Activities used in this Lesson:
HYPERLINK "Towers%20of%20Hanoi%20Worksheet.doc" Towers of Hanoi Worksheet This is a worksheet the groups will read the Towers of Hanoi myth on, and then the groups will use this worksheet to fill in the minimum number of moves needed for differing numbers of disks.
HYPERLINK "Towers%20of%20Hanoi%20Bases.doc" Towers of Hanoi Bases This is a printable sheet you will use to make the bases for each students Towers of Hanoi each student should have a strip of paper with three circles on it, so cut this sheet into horizontal sections.
Materials:
Pennies, nickels, dimes, and quarters
References:
HYPERLINK "http://mazeworks.com/hanoi/" http://mazeworks.com/hanoi/
HYPERLINK "http://www.kernelthread.com/hanoi/definition.html" http://www.kernelthread.com/hanoi/definition.html
Please email us your comments on this lesson: Email to HYPERLINK "mailto:ljohnson@cvm.tamu.edu" ljohnson@cvm.tamu.eduPlease include the title of the lesson, whether you are a teacher, resident scientist or college faculty and what grade you used it for.
Teacher's Comments:
Keywords:
math
formula
equation
tower
Hanoi
Texas State Standards
7.2 (F) Select and use appropriate operations to solve problems
7.2 (G) Determine the reasonableness of a solution to a problem
7.4 (C) Describe the relationship between terms in a sequence and their positions
7.13 (A) Identify and apply mathematics to everyday experiences
7.13 (C) Select or develop an appropriate problemsolving strategy
7.15 (B) Validate conclusions using mathematical properties and relationships
ABUVYhijl{}&
+
m
o
w
.=T_qxǼ뭩랗랗돗jh<Uh<B*phh<h<h<hehE\{h=Nhhe5B*\phh5B*\ph$jhh5B*U\phhB*phhe0J5\heB*phjheB*Uph3Yikl~y
M]
&F
gd<
&Fdd[$\$gde
&Fdd[$\$gde$a$gd$a$gdgde"
,

K
LMvʿʷʗ}mʏeeXejhB*UphhB*phjh<h<B*Uph#jh<B*UmHnHphuh<B*phjh<B*UphjhUh<h<5h<B*phhe5B*\phheB*phh<heh<h<h<h<0Jjh<UjhUh<"vwxEKMXY]Tǿǲǥǥǝmd\ThB*phhB*phhT<hu40J$jhT<hT<B*UphhT<B*phjhT<B*Uphhu4B*phhz&B*phhXGhXG6B*phhXGhXG5B*phh<B*phhXGB*phhB*phhh0JjhB*Uph$jhhB*Uph]T1r9F
&Fdd[$\$gdK/
&Fdd[$\$gde
&Fdd[$\$gde
&Fdd[$\$gdegde^gd#V
&F
gd<T01CHkp,/4cǹحxe\UNhhhhehh0J$jthhB*UphhB*phjhB*UphheB*phhe5B*\phhE\{hE\{5B*phhX,.B*CJaJphhX,.B*CJH*aJph hX,.h#VB*CJH*aJphhX,.h#VB*CJaJphhB*phhE\{B*phh#VB*phc457xy89DFGpqrݹլwlYw$jhJhK/B*UphhJhK/B*phjhJhK/B*Uphhhehe5B*\phh5B*\phheB*phj$heB*Uphhh0J$jPhhB*UphhB*phjhB*UphhheB*phhhhE\{r?@Shjkl
ʽʗumbmOuFu9j heB*Uphh{h0J$jBh{hB*UphhhB*phhB*phjhB*UphheB*phjheB*UphhJhK/0J6B*]ph*jihJhK/6B*U]ph:::hJhK/0JB*ph:::"jhJhK/0JB*Uph:::hJhK/B*phjhJhK/B*UphhJhK/0J
) + 6 ; C L R X n o A!!!""!!!!1$H$gdbd
&Fdd[$\$gdegdegdedd[$\$gdK/ " ) * + 4 6 : ; B C K L Q R W X m n o !""ºhbdhbdhbdhJhJhW35hJhJ5hihihihehihJj heB*Uphhe5B*\phheB*ph 1h/ =!"#$%Dd^k`
C<A$MCj04063700000[1]2qR+%JIwXX4IriH,@r>>+ՀH"[
Bm5ϴHx>0x{vI]S$&vL98JރF2呼06g/+9zhPZ^dZ#9}= q$gcv7k6 Xo`7Z/'3mV;k%ΛvRG<[RϋmEug_WOkROz}0Bd:_nRةn륶=PTt$B@w}a7&pPZ(MX1vI=bPMwHUnRQ7O}ۥaq~yɓ[4gAOCr;}x!lK5HX3c ƴu/1fM:5FetZ@0WR5YH{"]3mvR^TĔ݈1{zzv%LqA&k[yu.jB찐UfF{Wy~վ2qgw?ѝq[v!+}L?x^\I;/5\ɷ>v` ۉn@3bv>SW%Ԛ_CNju9FAk#'wD\կz"wĹDGtΑt\ra$s{
}D܉b{BFNWFΗzDW#sbqzYI?=F6 vWyOsim7¶ hntW6~}\g9NtMq;FlG(orƉؙ#&
i[XЮo;ߦ Y3m
ڋm[zӅ37=yXﲃ}Fv(LX뇵X^'v&F;Nsx,䳌P<{z{"M9<}clk_Ե+8=Opx}5:zNbEFNQj%3!g%7UzVhd5͂D$7K>`f[9̏5f,8Ln165V9f<7*n?</o1,`0~,K뢀?<+5Z=:NiG}>v7q$>#qL}>VkY
U!RJ\ǧäkAmQjDi#YjPtD^"5SÑJMt2Rsur1hp1j()W~^,fY^"=Xk3"6Xdt>5~DRv;+>D;01tgHTBm}VpE!ZSCFx/U[61_(3xJ>cEW>9f]#OcX&@3GwEp<#=Q0t:ehyX͕bJ9Uh!\KtM:0/
{mOsmF6Xkm=AcahOyl1ZIHxFIO7Fң$,MXElnd&6OSLD%m=$˃w.$JZ$ơ
юQH'S¸Cffffgovj;M[?[Iy煳GvI:TfU;ҙFz.m<ќOPMxىn<ba/J;\tlNcZ4vSv lFFP3BN0Qx2*3!ZqB~ ~]v!rjSV<'NPP3 X4x&ᄠ.\%p"pgݴPqRύc{3'2'B~u>V+Ovyxn");deo@k{tsXM{2
[
F=HEk<ړ`*_^~eC$`;?<95RG&c=_R!D?)ղvc!Cv~@HZ?Зݿ"l,
}
_ol2nЏJ_Y=zyoFQJuEZGT>UXO>pW~O>џdSlKO=7`Z,\k?^OPwl[WZ~
:
8uP?);yVX̹̽HCZGs.9/k=GĨ
@;Gi?vc_p^۹QR`)ܐ6b,L*ϙX_quCb*&HԑKqsAsPo01G3ۗba)Ov辀c3=0{ݗf~ɀKgC!=(qa/g'3f=&Q"#x֒_k".Ĺ;GS9Q+E)C2`qm{o_$`*iAvFsfIejh5PtMzVK}yl\_ S!Z'ϭ&Hr륾<ͶVv*v7iOa }eqWT V&]EllbXzj#̾A]d}b}&qmѶ;J'TkFO9Mj{9Fk֤[S5D!}žeD[N4
rBI4l瓟O<\fT
Y7'SO!;B[^rq\ss$s8wcu{+j;l&nb=>?&_ͥ=V B"nyCQ˕#KkmXnuM7q{lEnVtȧH%E*n{pK)\*7Tyt3KzͭԤ:Uq7^۹ε$5B~dH6aXx;
on&/Yx;o_yxx7ogx;o32 t+b7
'Kz4e/P74d۴Pohe{VjYVa!6Vf6[{><#iOݤkQ^[7bw]luxMjV"ˤ~ٯs?D{%\羖v"w?NDyKF`C:\Documents and Settings\Candace\Application Data\Microsoft\Word\Towers of Hanoi Worksheet.docDyKF\C:\Documents and Settings\Candace\Application Data\Microsoft\Word\Towers of Hanoi Bases.docDdD
3@@"?DyKyK8http://mazeworks.com/hanoi/DyKFTowers of Hanoi Worksheet.docDyKF
TOWERS~1.DOC@:Towers of Hanoi Worksheet.docDyKF
TOWERS~3.DOC82Towers of Hanoi Bases.docDd<P
33"((DyKyK8http://mazeworks.com/hanoi/=DyK2http://www.kernelthread.com/hanoi/definition.htmlyKdhttp://www.kernelthread.com/hanoi/definition.htmlDd<P
33"((DyKljohnson@cvm.tamu.eduyK:mailto:ljohnson@cvm.tamu.eduDd!<P
33"((Dd!<P
33"((@@@NormalCJ_HaJmH sH tH N@"Ne Heading 2dd@&[$\$5CJ$\aJ$DA@DDefault Paragraph FontRiRTable Normal4
l4a(k(No List4U@4e Hyperlink >*ph.X@.K/Emphasis6]:Yikl~y M
]T1r9F
)+6;CLRXnoA000Y0Y0Y0 0Y0Y 0Y 0Y 0Y0Y0Y0Y
0Y0Y
0Y
0Y
0Y
0Y
0Y
0Yp
0Y
0Y
0 Yp0Y0Y0Y0Y0Y0Y0Y0Y 0 00Y0Y 0Y0Y 0Y 0Y0Yp0Yp0Y0Y0Y0Y 0Y 0Yp 0Yp 0Yp 000p0p@000p000pYiy9F
)+6;CLRX000 00 0 0 0O9000ϞO900O900 000@ 0@00 00000000 0 0 0 0 0
0vTcr "]""AU,
LwX
,4Fq?kXXX_XXXXXXX8@J(
C!
3 s"*?`
c$X99? C!42
42
~42
@ B
S ?t9O9"9L"9$!9%!9\%!:%!:%!:&!:\&!:&!:&!:'!:\'!:'!ccqRRXX^
hhxWW]cc
9*urn:schemasmicrosoftcom:office:smarttagsplace8*urn:schemasmicrosoftcom:office:smarttagsCity8
*urn:schemasmicrosoftcom:office:smarttagsdate=
*urn:schemasmicrosoftcom:office:smarttags PlaceType= *urn:schemasmicrosoftcom:office:smarttags PlaceName2006275DayMonthYear
y333EF)+RWnW. R. KlemmCandace DiBiano
5rE3(XzL&+VԶ@n1& lgY^*
c
^\V
?`_>CgV8=.(kN>wm~dsFr]Iy1z^`CJOJQJo(^`CJOJQJo(opp^p`CJOJQJo(@@^@`CJOJQJo(^`CJOJQJo(^`CJOJQJo(^`CJOJQJo(^`CJOJQJo(PP^P`CJOJQJo(^`CJOJQJo(^`CJOJQJo(opp^p`CJOJQJo(@@^@`CJOJQJo(^`CJOJQJo(^`CJOJQJo(^`CJOJQJo(^`CJOJQJo(PP^P`CJOJQJo(h^`OJQJo(hHh^`OJQJ^Jo(hHohpp^p`OJQJo(hHh@@^@`OJQJo(hHh^`OJQJ^Jo(hHoh^`OJQJo(hHh^`OJQJo(hHh^`OJQJ^Jo(hHohPP^P`OJQJo(hH^`CJOJQJo(^`CJOJQJo(opp^p`CJOJQJo(@@^@`CJOJQJo(^`CJOJQJo(^`CJOJQJo(^`CJOJQJo(^`CJOJQJo(PP^P`CJOJQJo(^`CJOJQJo(^`CJOJQJo(opp^p`CJOJQJo(@@^@`CJOJQJo(^`CJOJQJo(^`CJOJQJo(^`CJOJQJo(^`CJOJQJo(PP^P`CJOJQJo(^`CJOJQJo(^`CJOJQJo(opp^p`CJOJQJo(@@^@`CJOJQJo(^`CJOJQJo(^`CJOJQJo(^`CJOJQJo(^`CJOJQJo(PP^P`CJOJQJo(^`CJOJQJo(^`CJOJQJo(opp^p`CJOJQJo(@@^@`CJOJQJo(^`CJOJQJo(^`CJOJQJo(^`CJOJQJo(^`CJOJQJo(PP^P`CJOJQJo(^`CJOJQJo(^`CJOJQJo(opp^p`CJOJQJo(@@^@`CJOJQJo(^`CJOJQJo(^`CJOJQJo(^`CJOJQJo(^`CJOJQJo(PP^P`CJOJQJo(^`CJOJQJo(^`CJOJQJo(opp^p`CJOJQJo(@@^@`CJOJQJo(^`CJOJQJo(^`CJOJQJo(^`CJOJQJo(^`CJOJQJo(PP^P`CJOJQJo(^`CJOJQJo(^`CJOJQJo(opp^p`CJOJQJo(@@^@`CJOJQJo(^`CJOJQJo(^`CJOJQJo(^`CJOJQJo(^`CJOJQJo(PP^P`CJOJQJo(^`CJOJQJo(^`CJOJQJo(opp^p`CJOJQJo(@@^@`CJOJQJo(^`CJOJQJo(^`CJOJQJo(^`CJOJQJo(^`CJOJQJo(PP^P`CJOJQJo(^`CJOJQJo(^`CJOJQJo(opp^p`CJOJQJo(@@^@`CJOJQJo(^`CJOJQJo(^`CJOJQJo(^`CJOJQJo(^`CJOJQJo(PP^P`CJOJQJo(^`CJOJQJo(^`CJOJQJo(opp^p`CJOJQJo(@@^@`CJOJQJo(^`CJOJQJo(^`CJOJQJo(^`CJOJQJo(^`CJOJQJo(PP^P`CJOJQJo(
.(kn1g5?`_>wmYc
^3(Iy1zds+
JEiz&#V.IX,.T<XGx~G=NbdE\{e<W3JK/u4@~mtmm@@UnknownGz Times New Roman5Symbol3&z Arial?5 z Courier New;Wingdings"h;{"1
/1
/!24
3QH)?x~GTAMU NSF GK12 HOME W. R. KlemmCandace DiBiano@
Oh+'0 $
@L
XdltTAMU NSF GK12 HOME 1AMUW. R. Klemm. R. RNormallCandace DiBiano17dMicrosoft Word 10.0@L@;@+1՜.+,D՜.+,Hhp
CVMVAPHN/
A
TAMU NSF GK12 HOME Title 8@_PID_HLINKSA<mailto:ljohnson@cvm.tamu.edu2http://www.kernelthread.com/hanoi/definition.htmli+http://mazeworks.com/hanoi/^]Towers of Hanoi Bases.doc[PTowers of Hanoi Worksheet.doc[PTowers of Hanoi Worksheet.doci+http://mazeworks.com/hanoi/
\C:\Documents and Settings\Candace\Application Data\Microsoft\Word\Towers of Hanoi Bases.doc`C:\Documents and Settings\Candace\Application Data\Microsoft\Word\Towers of Hanoi Worksheet.docq(C:\PEER3.NSF\Templates.forms\index.html
!"#$%&'()*+,.0123456789:;<=>?@ABCDEFGHIJKLMNPQRSTUVXYZ[\]^aRoot Entry F`:+cData
U!1Table/?WordDocument":SummaryInformation(ODocumentSummaryInformation8WCompObjj
FMicrosoft Word Document
MSWordDocWord.Document.89q