{"id":219861,"date":"2024-06-04T18:26:07","date_gmt":"2024-06-04T21:26:07","guid":{"rendered":"http:\/\/clubes.obmep.org.br\/blog\/?page_id=219861"},"modified":"2024-06-06T11:31:11","modified_gmt":"2024-06-06T14:31:11","slug":"a-sala-1-torre-de-hanoi","status":"publish","type":"page","link":"https:\/\/clubes.obmep.org.br\/blog\/a-sala-1-torre-de-hanoi\/","title":{"rendered":"(A) Sala 1 &#8211; Torre de Han\u00f3i"},"content":{"rendered":"<p class=\"ti3\"  style=\"text-align:center;\">Clique no bot\u00e3o abaixo para visualizar a Sala.<\/p>\n<div style=\"text-align:center;margin-top:10px;\">\n<input class=\"bo1 c1 cb13\" style=\"width:150px;\" value=\"Sala\" title=\"Clique aqui\" type=\"button\" onclick=    \"if(this.parentNode.getElementsByTagName('div')[0].style.display != ''){this.parentNode.getElementsByTagName('div')[0].style.display = '';this.value = 'Ocultar';} else{this.parentNode.getElementsByTagName('div')[0].style.display = 'none'; this.value = 'Sala';}\" \/>  <\/p>\n<div style=\"display: none;\">\n<div class=\"cb21\" style=\"color: #040404; padding:20px; font-family: times; line-height: 28px; font-size: 20px; text-align:justify;  padding-bottom:10px;\">\n<div class=\"nome c2\" style=\"font-size: 45px;\"><strong>Torre de Han\u00f3i<\/strong><\/div>\n<hr style=\"height:3px; width:100%;background-color:#4178a1;   margin-top: 8px; margin-bottom: 8px; border: 0 none\"\/>\n<hr style=\"height:3px; width:100%;background-color:#4178a1;   margin-top: 8px; margin-bottom: 30px; border: 0 none\"\/>\n<p class=\"ti1 c2 \" style=\"line-height:30px;margin:30px\">Dentre lendas e pot\u00eancias, a torre se sustenta!<\/p>\n<p style=\"margin:30px 50px 20px 50px;\">\nCriada em 1883 pelo matem\u00e1tico franc\u00eas <em>Edouard Lucas<\/em>, a <strong>Torre de Han\u00f3i<\/strong> \u00e9 um jogo muito popular entre crian\u00e7as e jovens amantes da Matem\u00e1tica de todo o mundo. O racioc\u00ednio por tr\u00e1s \u00e9 bastante interessante, e instigar os jovens a explorarem meios de resolver o problema da torre com \u00eaxito, ainda que realizando mais jogadas do que o m\u00ednimo necess\u00e1rio, \u00e9 fundamental para que eles possam desenvolver suas capacidades de racioc\u00ednio l\u00f3gico e criatividade.<br \/>\nA <strong>Torre de Han\u00f3i<\/strong> consiste em uma plataforma, normalmente de madeira, tradicionalmente com 3 hastes e um n\u00famero determinado de discos de di\u00e2metros diferentes, posicionados de baixo para cima, do maior para o menor.<\/p>\n<p><center><\/p>\n<div  style=\"background-color:#c6d9e8;border:1px solid #4178a1;line-height: 32px; padding:20px;text-align:justify\">\n<p style=\"text-align:center; font-size:15px; line-height:25px;\">\n<span style=\"font-size:20px;\"><strong>Torre de Han\u00f3i: um dos mais conhecidos jogos na Matem\u00e1tica<\/strong> <\/span><br \/>\n<img loading=\"lazy\" decoding=\"async\" src=\"http:\/\/clubes.obmep.org.br\/blog\/wp-content\/uploads\/2024\/02\/TH_01.jpeg\" style=\"border:none\"  alt=\"\" width=\"677\" height=\"298\" class=\"aligncenter size-full wp-image-212874\" srcset=\"https:\/\/clubes.obmep.org.br\/blog\/wp-content\/uploads\/2024\/02\/TH_01.jpeg 677w, https:\/\/clubes.obmep.org.br\/blog\/wp-content\/uploads\/2024\/02\/TH_01-300x132.jpeg 300w\" sizes=\"auto, (max-width: 677px) 100vw, 677px\" \/>Imagem extra\u00edda do site <a href=\"https:\/\/commons.wikimedia.org\/w\/index.php?curid=228623\" target=\"_blank\"><strong>Wikimedia Commons<\/strong><\/a>. (Acesso em 02\/02\/2024.)<\/p>\n<\/div>\n<p><\/center><\/p>\n<hr style=\"height:1px; width:100%;background-color:#4178a1;   margin-top: 30px; margin-bottom: 8px; border: 0 none\"\/>\n<hr style=\"height:5px; width:100%;background-color:#4178a1;  margin-top: 8px; margin-bottom: 8px;  border: 0 none\"\/>\n<hr style=\"height:1px; width:100%;background-color:#4178a1;   margin-top: 8px; margin-bottom: 30px; border: 0 none\"\/>\n<p class=\"ti1 c2 \" style=\"line-height:30px;margin:30px; font-size:21px;\">I &#8211; Salvem-se! O fim do mundo est\u00e1 pr\u00f3ximo!<\/p>\n<p>Segundo uma lenda hindu, na cidade santa de Benares, na \u00cdndia, debaixo da c\u00fapula de um templo, havia uma placa de bronze e, sobre ela, tr\u00eas hastes de diamante fixadas. Numa dessas hastes, o deus <em>Brahma<\/em>, no momento em que criou o mundo, colocou 64 discos de ouro puro, em ordem decrescente de tamanho, de baixo para cima.<br \/>\nOs monges foram ent\u00e3o instru\u00eddos a moverem a torre de discos original de uma haste a outra, utilizando uma terceira como auxiliar, sempre um disco de cada vez e nunca um disco maior sobre um disco menor. Os monges deveriam trabalhar noite e dia e, quando terminassem o trabalho, o templo seria transformado em p\u00f3 e o mundo acabaria.<br \/>\nFicou com medo? N\u00e3o se preocupe!<br \/>\nOs monges precisariam realizar, no m\u00ednimo, 18.446.744.073.709.551.615 movimentos para moverem a pir\u00e2mide de uma haste a outra. Mesmo que fossem capazes de mover um disco por segundo, eles necessitariam de, aproximadamente, 585 bilh\u00f5es de anos para finalmente resolverem o problema.<\/p>\n<p style=\"margin:-5px;\">\n<hr style=\"height:1px; width:100%;background-color:#4178a1; margin-top: 30px; margin-bottom: 10px; border: 0 none\"\/>\n<hr style=\"height:1px; width:100%;background-color:#4178a1; margin-top: 10px; margin-bottom: 30px; border: 0 none\"\/>\n<p class=\"ti1 c2 \" style=\"line-height:30px;margin:30px; font-size:21px;\">II &#8211; Objetivo e Regras<\/p>\n<p>O objetivo do jogo Torre de Han\u00f3i, como j\u00e1 descrito na lenda hindu, \u00e9 mover uma pilha com um n\u00famero determinado de discos de uma haste a outra. As duas \u00fanicas regras para a realiza\u00e7\u00e3o dos movimentos s\u00e3o:<br \/>\n<center><\/p>\n<div  style=\"width:100%;  background-color:#c6d9e8;border:1px solid #4178a1;line-height: 32px; padding-top:10px;text-align:justify\">\n<ul>1. Apenas um disco pode ser transferido de uma haste a outra por vez.<br \/>\n2. Discos maiores n\u00e3o podem ser colocados sobre discos menores.<\/ul>\n<\/div>\n<p><\/center><\/p>\n<hr style=\"height:1px; width:100%;background-color:#4178a1; margin-top: 30px; margin-bottom: 10px; border: 0 none\"\/>\n<hr style=\"height:1px; width:100%;background-color:#4178a1; margin-top: 10px; margin-bottom: 30px; border: 0 none\"\/>\n<p class=\"ti1 c2 \" style=\"line-height:30px;margin:30px; font-size:21px;\">III &#8211; M\u00e3os \u00e0 obra!<\/p>\n<p>Este t\u00f3pico destina-se \u00e0queles que desejam construir uma Torre de Han\u00f3i manualmente para realizarem a atividade. Caso voc\u00ea j\u00e1 possua o brinquedo, tamb\u00e9m pode utiliz\u00e1-lo.<br \/>\n<center><\/p>\n<div  style=\"  background-color:#c6d9e8;border:1px solid #4178a1;line-height: 32px; padding:20px;text-align:justify\">\n<strong>Materiais Necess\u00e1rios <\/strong><br \/>\n\u25cf Compasso;<br \/>\n\u25cf Canetas;<br \/>\n\u25cf R\u00e9gua;<br \/>\n\u25cf Cola-quente;<br \/>\n\u25cf Papel\u00e3o;<br \/>\n\u25cf 1 Placa de isopor;<br \/>\n\u25cf 3 palitos para churrasco ou canudos de pl\u00e1stico.<\/div>\n<p><\/center><\/p>\n<p><strong>Como fazer:<\/strong><br \/>\n1. Vamos utilizar o papel\u00e3o para fazer os discos. Com o compasso, trace duas circunfer\u00eancias de raio 1,5 cm. Repita o procedimento, aumentando em 0,5 cm o raio das circunfer\u00eancias, fazendo sempre duas circunfer\u00eancias para cada medida de raio. Voc\u00ea pode fazer quantas circunfer\u00eancias achar necess\u00e1rio, por\u00e9m, para uma introdu\u00e7\u00e3o ao jogo, aconselhamos come\u00e7ar com 6 (3 tamanhos diferentes).<br \/>\n2. Recorte todos os discos e cole os de mesmo tamanho um sobre o outro, para que fiquem mais firmes.<br \/>\n3. Fa\u00e7a um furo no centro dos discos, de modo que eles possam passar com uma pequena folga pelos palitos ou canudos.<br \/>\n4. Finque os palitos ou canudos na placa de isopor, fixando-os com cola. \u00c9 importante que a dist\u00e2ncia entre eles seja suficiente para que, na transfer\u00eancia das torres, um disco n\u00e3o colida com outro (sugerimos uma dist\u00e2ncia pelo menos igual ao di\u00e2metro do maior disco).<br \/>\n5. Voc\u00ea j\u00e1 pode se divertir com a sua Torre de Han\u00f3i! Se desejar, pode ainda colorir os discos ou a base de isopor.<\/p>\n<hr style=\"height:1px; width:100%;background-color:#4178a1; margin-top: 30px; margin-bottom: 10px; border: 0 none\"\/>\n<hr style=\"height:1px; width:100%;background-color:#4178a1; margin-top: 10px; margin-bottom: 30px; border: 0 none\"\/>\n<p class=\"ti1 c2 \" style=\"line-height:30px;margin:30px; font-size:21px;\">IV &#8211; Um aplicativo interessante<\/p>\n<p>Voc\u00eas tamb\u00e9m podem utilizar o aplicativo abaixo para jogarem  e se divertirem!<br \/>\n<center><\/p>\n<div  style=\"  background-color:#c6d9e8;border:1px solid #4178a1;line-height: 32px; padding:20px;text-align:justify\">\n<strong>Instru\u00e7\u00f5es para usar o aplicativo<\/strong><br \/>\n1) Espere o aplicativo carregar.<br \/>\n2) Selecione a quantidade de discos.<br \/>\n3) Observe a quantidade m\u00ednima de movimentos fornecida pelo aplicativo.<br \/>\n4) Para mover um disco, clique sobre ele e, em seguida, clique na haste para a qual ele ser\u00e1 movido.<br \/>\n5) Se precisar reiniciar o jogo, clique no bot\u00e3o [tex]\\boxed {\\text{Reset}}[\/tex], no canto superior esquerdo do aplicativo.<\/div>\n<p><\/center><\/p>\n<p style=\"text-align:center; line-height:30px;line-height:15px;margin:40px\">\n<iframe loading=\"lazy\" title=\"Torre de Hanoi\" src=\"https:\/\/www.geogebra.org\/material\/iframe\/id\/ebnrujnm\/width\/755\/height\/415\/border\/ffffff\/sfsb\/false\/smb\/false\/stb\/false\/stbh\/false\/ai\/false\/asb\/false\/sri\/false\/rc\/false\/ld\/false\/sdz\/false\/ctl\/false\" width=\"760px\" height=\"420px\" style=\"border: 2px solid #4178a1;\"> <\/iframe><br \/>\n<span style=\"font-size: small\">OBMEP_srdg, criado com o <a href=\"http:\/\/www.geogebra.org\/\" target=\"_blank\" ><strong>GeoGebra<\/strong><\/a><br \/>\nAdaptado de: <a href=\"https:\/\/www.geogebra.org\/m\/s5hd5qum\" target=\"_blank\" ><strong>Patr\u00edcia Coelho Barbosa<\/strong><\/a><\/span> <\/p>\n<p style=\"margin:-5px;\">\n<hr style=\"height:1px; width:100%;background-color:#4178a1; margin-top: 25px; margin-bottom: 10px; border: 0 none\"\/>\n<hr style=\"height:1px; width:100%;background-color:#4178a1; margin-top: 10px; margin-bottom: 31px; border: 0 none\"\/>\n<p class=\"ti1 c2 \" style=\"line-height:30px;margin:30px; font-size:21px;\">V &#8211;  Atividades com a Torre de Han\u00f3i<\/p>\n<div class=\"cb27\" style=\"color: #040404; padding:20px; font-family: times; line-height: 28px; font-size: 20px; text-align:justify;  padding-bottom:10px;\">\n<span style=\"color: #4178a1;\"><span style=\" font-size: 18px;\">&#10148;<\/span><strong> Atividade 1:<\/strong><\/span> Primeiramente, vamos brincar com poucos discos&#8230;<br \/>\nQuantos movimentos s\u00e3o necess\u00e1rios para um jogo de apenas um disco? E para um jogo de dois discos? <\/p>\n<div style=\"text-align:center;\"><input class=\"bo1 c2 cbta8\" style=\"width:150px;\" value=\"Resposta\" title=\"Clique aqui\" type=\"button\" onclick=    \"if(this.parentNode.getElementsByTagName('div')[0].style.display != ''){this.parentNode.getElementsByTagName('div')[0].style.display = '';this.value = 'Ocultar';} else{this.parentNode.getElementsByTagName('div')[0].style.display = 'none'; this.value = 'Resposta';}\" \/>   <\/p>\n<div  style=\"display: none;\">\n<div class=\"gr1 cb28\" style=\"color: #040404; padding:20px; font-family: times; line-height: 28px; font-size: 20px; text-align:justify;  padding-bottom:10px; width:98%;\">\n\u00c9 necess\u00e1rio apenas um movimento para o jogo com um disco; para o jogo com dois discos s\u00e3o necess\u00e1rios 3 movimentos.\n<\/div>\n<\/div>\n<\/div>\n<\/div>\n<p style=\"margin:30px;\">\n<div class=\"cb27\" style=\"color: #040404; padding:20px; font-family: times; line-height: 28px; font-size: 20px; text-align:justify;  padding-bottom:10px;\">\n<span style=\"color: #4178a1;\"><span style=\" font-size: 18px;\">&#10148;<\/span><strong> Atividade 2:<\/strong><\/span> Agora, para 3 discos, de quantas jogadas voc\u00ea necessita? S\u00e3o quantas jogadas a mais do que no jogo com 2 discos? H\u00e1 alguma rela\u00e7\u00e3o entre a sequ\u00eancia de movimentos dos dois jogos?<\/p>\n<div style=\"text-align:center;\"><input class=\"bo1 c2 cbta8\" style=\"width:150px;\" value=\"Resposta\" title=\"Clique aqui\" type=\"button\" onclick=    \"if(this.parentNode.getElementsByTagName('div')[0].style.display != ''){this.parentNode.getElementsByTagName('div')[0].style.display = '';this.value = 'Ocultar';} else{this.parentNode.getElementsByTagName('div')[0].style.display = 'none'; this.value = 'Resposta';}\" \/>   <\/p>\n<div  style=\"display: none;\">\n<div class=\"gr1 cb28\" style=\"color: #040404; padding:20px; font-family: times; line-height: 28px; font-size: 20px; text-align:justify;  padding-bottom:10px; width:98%;\">\nPrecisamos de, no m\u00ednimo, 7 jogadas, 4 a mais do que no jogo anterior. Isso ocorre pois, realizados os movimentos do jogo de 2 discos, devemos mover a pe\u00e7a maior para a haste vazia e realizar novamente o jogo de 2 discos, encaixando as pe\u00e7as menores sobre a pe\u00e7a maior.<br \/>\nConfira o v\u00eddeo para compreender melhor: <\/p>\n<div class=\"gr1\" style=\"margin:30px;line-height:30px; width:95%; margin-left:auto; margin-right:auto; text-align:center; border: solid 2px #4178a1;font-size:16px \">\n<p class=\"ti1\" style=\"line-height:30px;margin:10px; color:#4178a1;\"><em>Torre de Han\u00f3i com 3 discos<\/em><\/p>\n<hr style=\"height:1px; width:100%;background-color:#4178a1; margin-top: 10px; margin-bottom: 20px;border: 0 none\"\/>\nPara assistir, \u00e9 s\u00f3 clicar na setinha.<br \/>\n<iframe loading=\"lazy\" width=\"640\" height=\"360\" src=\"https:\/\/www.youtube.com\/embed\/3QfCWymvdNY?rel=0\" allowfullscreen><\/iframe><br \/>\nV\u00eddeo Autoral &#8211; COM Geomestres Slay.<\/div>\n<\/div>\n<\/div>\n<\/div>\n<\/div>\n<p style=\"margin:30px;\">\n<div class=\"cb27\" style=\"color: #040404; padding:20px; font-family: times; line-height: 28px; font-size: 20px; text-align:justify;  padding-bottom:10px;\">\n<span style=\"color: #4178a1;\"><span style=\" font-size: 18px;\">&#10148;<\/span><strong> Atividade 3:<\/strong><\/span> Qual a rela\u00e7\u00e3o entre o n\u00famero m\u00ednimo de movimentos dos jogos com 2 e 3 discos e a quantidade de discos da torre? A rela\u00e7\u00e3o funciona para jogos com 3 e 4 discos?<\/p>\n<div style=\"text-align:center;\"><input class=\"bo1 c2 cbta8\" style=\"width:150px;\" value=\"Resposta\" title=\"Clique aqui\" type=\"button\" onclick=    \"if(this.parentNode.getElementsByTagName('div')[0].style.display != ''){this.parentNode.getElementsByTagName('div')[0].style.display = '';this.value = 'Ocultar';} else{this.parentNode.getElementsByTagName('div')[0].style.display = 'none'; this.value = 'Resposta';}\" \/>   <\/p>\n<div  style=\"display: none;\">\n<div class=\"gr1 cb28\" style=\"color: #040404; padding:20px; font-family: times; line-height: 28px; font-size: 20px; text-align:justify;  padding-bottom:10px; width:98%;\">\nNo jogo de 3 discos, temos o dobro de movimentos do jogo de 2 discos mais um, ou seja:<\/p>\n<ul>\n<li>o jogo de 2 discos;<\/li>\n<li> mais o movimento da pe\u00e7a maior;<\/li>\n<li>mais o jogo de 2 discos;<\/li>\n<\/ul>\n<p> como explicado na atividade anterior.<br \/>\nE sim, a rela\u00e7\u00e3o funciona para os jogos com 3 e 4 discos e para quaisquer [tex]n-1~[\/tex] e   [tex]~n[\/tex] discos, de modo que temos uma quantidade de movimentos  [tex]m(n)[\/tex] em fun\u00e7\u00e3o do n\u00famero [tex]n[\/tex] de discos, associada \u00e0 quantidade de movimentos da etapa anterior, ou seja, a f\u00f3rmula recursiva [tex]\\boxed{m\\left(n\\right)=2 \\times m(n-1)+1}.[\/tex]\n<\/p><\/div>\n<\/div>\n<\/div>\n<\/div>\n<p style=\"margin:30px;\">\n<div class=\"cb27\" style=\"color: #040404; padding:20px; font-family: times; line-height: 28px; font-size: 20px; text-align:justify;  padding-bottom:10px;\">\n<span style=\"color: #4178a1;\"><span style=\" font-size: 18px;\">&#10148;<\/span><strong> Atividade 4:<\/strong><\/span> Podemos generalizar o n\u00famero m\u00ednimo de movimentos, ou seja, associar cada n\u00famero [tex]n[\/tex] de discos a uma quantidade [tex]m(n)[\/tex] de movimentos, independentemente do n\u00famero de movimentos da quantidade anterior de discos? <\/p>\n<div style=\"text-align:center;\"><input class=\"bo1 c2 cbta8\" style=\"width:150px;\" value=\"Resposta\" title=\"Clique aqui\" type=\"button\" onclick=    \"if(this.parentNode.getElementsByTagName('div')[0].style.display != ''){this.parentNode.getElementsByTagName('div')[0].style.display = '';this.value = 'Ocultar';} else{this.parentNode.getElementsByTagName('div')[0].style.display = 'none'; this.value = 'Resposta';}\" \/>   <\/p>\n<div  style=\"display: none;\">\n<div class=\"gr1 cb28\" style=\"color: #040404; padding:20px; font-family: times; line-height: 28px; font-size: 20px; text-align:justify;  padding-bottom:10px; width:98%;\">\nSim, basta notarmos que a quantidade de movimentos, em fun\u00e7\u00e3o do n\u00famero [tex]n[\/tex] de discos, cresce exponencialmente, de modo que temos uma progress\u00e3o geom\u00e9trica.<br \/>\nA quantidade de movimentos \u00e9 dada pela fun\u00e7\u00e3o [tex]\\boxed{m(n)=2^n-1}[\/tex], e explicaremos as raz\u00f5es para tal fato no item a seguir.\n<\/div>\n<\/div>\n<\/div>\n<\/div>\n<p style=\"margin:-2px;\">\n<hr style=\"height:1px; width:100%;background-color:#4178a1; margin-top: 30px; margin-bottom: 10px; border: 0 none\"\/>\n<hr style=\"height:1px; width:100%;background-color:#4178a1; margin-top: 10px; margin-bottom: 30px; border: 0 none\"\/>\n<p class=\"ti1 c2 \" style=\"line-height:30px;margin:30px; font-size:21px;\">VI &#8211; Formalizando o Racioc\u00ednio<\/p>\n<p>Conforme mencionado na resposta da<strong> Atividade 4<\/strong>, a quantidade m\u00ednima de movimentos necess\u00e1rios para mover uma torre com  discos no jogo Torre de Han\u00f3i \u00e9 dada pela f\u00f3rmula [tex]\\boxed{m(n)=2^n-1}[\/tex], para todo n\u00famero natural n\u00e3o nulo [tex]n.[\/tex]<br \/>\nA demonstra\u00e7\u00e3o dessa f\u00f3rmula pode ser desenvolvida usando uma t\u00e9cnica matem\u00e1tica chamada <strong><em>Princ\u00edpio da Indu\u00e7\u00e3o Finita<\/em><\/strong>.<br \/>\nVejamos.<\/p>\n<ul>\n<li>Para come\u00e7ar, podemos facilmente calcular que, quando [tex]n=1[\/tex], a quantidade m\u00ednima de movimentos necess\u00e1rios \u00e9 [tex]m(n)=1[\/tex], j\u00e1 que s\u00f3 h\u00e1 um disco para mover at\u00e9 a haste de destino.<br \/>\nAplicando [tex]n=1[\/tex] na f\u00f3rmula, chega-se ao resultado esperado: [tex]m(1)=2^1-1=1.[\/tex]<\/li>\n<li>Agora, supondo por hip\u00f3tese que a f\u00f3rmula seja v\u00e1lida para um certo n\u00famero natural n\u00e3o nulo [tex]n[\/tex], ou seja, que [tex]m(n)=2^n-1[\/tex], precisamos mostrar que [tex]m(n+1)=2^{n+1}-1[\/tex]<br \/>\nPara isso, vamos retomar uma f\u00f3rmula j\u00e1 obtida anteriormente na Atividade 3: [tex]m\\left(n\\right)=2 \\times m(n-1)+1.[\/tex]<br \/>\nSubstituindo [tex]n[\/tex] por [tex]n+1[\/tex], obtemos<br \/>\n[tex]\\qquad m\\left(n+1\\right)=2 \\times m((n+1)-1)+1=2 \\times m(n)+1\\qquad \\textcolor{#4178a1}{(i)}[\/tex]<br \/>\ne, como hip\u00f3tese, [tex]\\boxed{m\\left(n\\right)=2^n-1}[\/tex], segue por [tex]\\textcolor{#4178a1}{(i)}[\/tex] que:<br \/>\n[tex]\\qquad  m\\left(n+1\\right)=2 \\times \\textcolor{red}{m(n)}+1\\\\<br \/>\n\\qquad  m\\left(n+1\\right)=2 \\times \\textcolor{red}{\\left(2^n-1\\right)}+1\\\\<br \/>\n\\qquad  m\\left(n+1\\right)=2^{n+1}-2+1\\\\<br \/>\n\\qquad  m\\left(n+1\\right)=2^{n+1}-1. [\/tex]<\/li>\n<\/ul>\n<p>Portanto, provamos que se a f\u00f3rmula \u00e9 verdadeira para [tex]n[\/tex], ent\u00e3o ela \u00e9 tamb\u00e9m verdadeira para [tex]n+1[\/tex]. Como a f\u00f3rmula j\u00e1 foi mostrada ser verdadeira para [tex]n=1[\/tex] no primeiro caso, podemos concluir que ela \u00e9 verdadeira para todos os n\u00fameros naturais n\u00e3o nulos.<\/p>\n<p style=\"margin:10px;\">\n<p><strong>Observa\u00e7\u00e3o:<\/strong> Para quem ficou confuso se, com as duas etapas que provamos, garantimos que a igualdade [tex]m(n)=2^n-1[\/tex] \u00e9 v\u00e1lida para todos os n\u00fameros naturais n\u00e3o nulos [tex]n[\/tex], considere as seguintes afirma\u00e7\u00f5es utilizadas na demonstra\u00e7\u00e3o:<br \/>\n<strong>(1)<\/strong> A igualdade [tex]m(n)=2^n-1[\/tex] \u00e9 v\u00e1lida para [tex]n=1.[\/tex]<br \/>\n<strong>(2)<\/strong> Se a igualdade [tex]m(n)=2^n-1[\/tex] \u00e9 v\u00e1lida para [tex]n[\/tex], ent\u00e3o ela \u00e9 tamb\u00e9m v\u00e1lida para [tex]n+1.[\/tex]<br \/>\ne acompanhe alguns passos de uma sequ\u00eancia pr\u00e1tica que n\u00e3o tem fim:<\/p>\n<ul>\n<li>Por <strong>(1)<\/strong>, a igualdade em quest\u00e3o \u00e9 v\u00e1lida para [tex]n=1.[\/tex]<\/li>\n<li>Como a igualdade em quest\u00e3o \u00e9 v\u00e1lida para [tex]n=1[\/tex], por <strong>(2)<\/strong>, ela tamb\u00e9m \u00e9 v\u00e1lida para [tex]n=1+1=2.[\/tex]  <\/li>\n<li>Como a igualdade em quest\u00e3o \u00e9 v\u00e1lida para [tex]n=2[\/tex], por <strong>(2)<\/strong>, ela tamb\u00e9m \u00e9 v\u00e1lida para [tex]n=2+1=3.[\/tex]  <\/li>\n<li>Como a igualdade em quest\u00e3o \u00e9 v\u00e1lida para [tex]n=3[\/tex], por <strong>(2)<\/strong>, ela tamb\u00e9m \u00e9 v\u00e1lida para [tex]n=3+1=4.[\/tex]  <\/li>\n<li>Como a igualdade em quest\u00e3o \u00e9 v\u00e1lida para [tex]n=4[\/tex], por <strong>(2)<\/strong>, ela tamb\u00e9m \u00e9 v\u00e1lida para [tex]n=4+1=5.[\/tex]  <\/li>\n<li>Como a igualdade em quest\u00e3o \u00e9 v\u00e1lida para [tex]n=5[\/tex], por <strong>(2)<\/strong>, ela tamb\u00e9m \u00e9 v\u00e1lida para [tex]n=5+1=6.[\/tex]  <\/li>\n<li>Como a igualdade em quest\u00e3o \u00e9 v\u00e1lida para [tex]n=6[\/tex], por <strong>(2)<\/strong>, ela tamb\u00e9m \u00e9 v\u00e1lida para [tex]n=6+1=7.[\/tex]  <\/li>\n<li>Como a igualdade em quest\u00e3o \u00e9 v\u00e1lida para [tex]n=7[\/tex], por <strong>(2)<\/strong>, ela tamb\u00e9m \u00e9 v\u00e1lida para [tex]n=7+1=8.[\/tex]  <\/li>\n<li>Como a igualdade em quest\u00e3o \u00e9 v\u00e1lida para [tex]n=8[\/tex], por <strong>(2)<\/strong>, ela tamb\u00e9m \u00e9 v\u00e1lida para [tex]n=8+1=9.[\/tex]  <\/li>\n<li>Como a igualdade em quest\u00e3o \u00e9 v\u00e1lida para [tex]n=9[\/tex], por <strong>(2)<\/strong>, ela tamb\u00e9m \u00e9 v\u00e1lida para [tex]n=9+1=10.[\/tex]  <\/li>\n<li>Como a igualdade em quest\u00e3o \u00e9 v\u00e1lida para [tex]n=10[\/tex], por <strong>(2)<\/strong>, ela tamb\u00e9m \u00e9 v\u00e1lida para [tex]n=10+1=11.[\/tex]  <\/li>\n<li> Etc., etc., etc&#8230;  <\/li>\n<\/ul>\n<p>Deu para perceber que, com as duas afirma\u00e7\u00f5es provadas, de fato, chegamos na validade da igualdade para qualquer n\u00famero natural n\u00e3o nulo?<\/p>\n<p style=\"margin:1px;\">\n<hr style=\"height:1px; width:100%;background-color:#4178a1; margin-top: 30px; margin-bottom: 10px; border: 0 none\"\/>\n<hr style=\"height:1px; width:100%;background-color:#4178a1; margin-top: 10px; margin-bottom: 30px; border: 0 none\"\/>\n<p class=\"ti1 c2 \" style=\"line-height:30px;margin:30px; font-size:21px;\">VII &#8211; Aprendendo um pouco mais<\/p>\n<p>Podemos tamb\u00e9m justificar que a quantidade m\u00ednima de movimentos necess\u00e1rios para mover os [tex]n[\/tex] discos do jogo Torre de Han\u00f3i \u00e9 dada pela f\u00f3rmula [tex]\\boxed{2^n-1}[\/tex] explorando um pouco mais o conceito de <strong>&#8220;rela\u00e7\u00f5es de recorr\u00eancia&#8221;<\/strong>, j\u00e1 citado anteriormente na Atividade 3.<br \/>\nUma rela\u00e7\u00e3o de recorr\u00eancia \u00e9 uma rela\u00e7\u00e3o que determina cada termo de uma dada sequ\u00eancia, a partir de certo termo, em fun\u00e7\u00e3o de termos anteriores; assim, uma recorr\u00eancia  \u00e9 uma express\u00e3o que d\u00e1 o valor de uma fun\u00e7\u00e3o num dado ponto em termos dos valores da mesma fun\u00e7\u00e3o em pontos anteriores.<br \/>\nSe voc\u00ea ficou curioso sobre como resolver recursivamente o jogo da Torre de Han\u00f3i para [tex]n[\/tex] discos, assista o v\u00eddeo abaixo.<br \/>\nAntes de assisti-lo, observe e tente entender o esqueminha geom\u00e9trico a seguir: <strong>ele pode ajudar<\/strong>&#8230;<br \/>\n<img loading=\"lazy\" decoding=\"async\" src=\"http:\/\/clubes.obmep.org.br\/blog\/wp-content\/uploads\/2024\/04\/fig_37_1.png\"  style=\"border:none\"  alt=\"\" width=\"525\" height=\"630\" class=\"aligncenter size-full wp-image-216286\" srcset=\"https:\/\/clubes.obmep.org.br\/blog\/wp-content\/uploads\/2024\/04\/fig_37_1.png 525w, https:\/\/clubes.obmep.org.br\/blog\/wp-content\/uploads\/2024\/04\/fig_37_1-250x300.png 250w\" sizes=\"auto, (max-width: 525px) 100vw, 525px\" \/><\/p>\n<div class=\"gr1\" style=\"margin:20px;line-height:20px; width:95%; margin-left:auto; margin-right:auto; text-align:center; border: solid 2px #4178a1;font-size:16px \">\n<p class=\"ti2\" style=\"color:#4178a1;\"><em>A SURPREENDENTE Matem\u00e1tica da TORRE de HAN\u00d3I (Fractais, Bin\u00e1rios\u2026)<\/em><\/p>\n<hr style=\"height:1px; width:100%;background-color:#4178a1; margin-top: 10px; margin-bottom: 20px;border: 0 none\"\/>\n<p style=\"text-align:justify;\"> Encontre recorr\u00eancias e mais Matem\u00e1tica escondida na Torre de Han\u00f3i!<\/p>\n<p>\u00c9 s\u00f3 clicar na setinha.<br \/>\n<iframe loading=\"lazy\" width=\"640\" height=\"360\" src=\"https:\/\/www.youtube.com\/embed\/CLouA-TA6nc?rel=0\" allowfullscreen><\/iframe><br \/>\nV\u00eddeo do canal \u201cTem Ci\u00eancia\u201d, de Daniel Nunes.<\/div>\n<p style=\"margin:30px;\">\n<hr style=\"height:2px; width:100%;background-color:#4178a1;   margin-top: 10px; margin-bottom: 10px; border: 0 none\"\/>\n<hr style=\"height:2px; width:100%;background-color:#4178a1;   margin-top: 10px; margin-bottom: 10px; border: 0 none\"\/>\n<p style=\"text-align: right;\"><span style=\"color: #4178a1; font-size: 21px;\"><strong>COM Geomestres Slay <\/strong> <span style=\"font-size:19px;\">(Col\u00e9gio Militar de Porto Alegre, RS)<\/span><br \/>\n<strong>Equipe COM &#8211; OBMEP<\/strong><\/span><\/p>\n<\/div>\n<p class=\"fim\"><a title=\"Voltar.\" href=\"http:\/\/clubes.obmep.org.br\/blog\/?p=219858\" target=\"_blank\"><span class=\"c2\"><strong>Voltar para a Sala Inicial<\/strong><\/span><\/a><br \/>\n<a title=\"Voltar.\" href=\"http:\/\/clubes.obmep.org.br\/blog\/?p=219862\" target=\"_blank\"><span class=\"c2\"><strong>Ir para a Sala 2<\/strong><\/span><\/a><\/p>\n<\/div>\n<\/div>\n","protected":false},"excerpt":{"rendered":"<p>Clique no bot\u00e3o abaixo para visualizar a Sala. Torre de Han\u00f3i Dentre lendas e pot\u00eancias, a torre se sustenta! Criada em 1883 pelo matem\u00e1tico franc\u00eas Edouard Lucas, a Torre de Han\u00f3i \u00e9 um jogo muito popular entre crian\u00e7as e jovens amantes da Matem\u00e1tica de todo o mundo. O racioc\u00ednio por tr\u00e1s \u00e9 bastante interessante, e &hellip; <\/p>\n<p><a class=\"more-link btn\" href=\"https:\/\/clubes.obmep.org.br\/blog\/a-sala-1-torre-de-hanoi\/\">Continue lendo<\/a><\/p>\n","protected":false},"author":2,"featured_media":0,"parent":0,"menu_order":0,"comment_status":"closed","ping_status":"closed","template":"template-onecolumn.php","meta":{"footnotes":""},"class_list":["post-219861","page","type-page","status-publish","hentry","nodate","item-wrap"],"_links":{"self":[{"href":"https:\/\/clubes.obmep.org.br\/blog\/wp-json\/wp\/v2\/pages\/219861","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/clubes.obmep.org.br\/blog\/wp-json\/wp\/v2\/pages"}],"about":[{"href":"https:\/\/clubes.obmep.org.br\/blog\/wp-json\/wp\/v2\/types\/page"}],"author":[{"embeddable":true,"href":"https:\/\/clubes.obmep.org.br\/blog\/wp-json\/wp\/v2\/users\/2"}],"replies":[{"embeddable":true,"href":"https:\/\/clubes.obmep.org.br\/blog\/wp-json\/wp\/v2\/comments?post=219861"}],"version-history":[{"count":4,"href":"https:\/\/clubes.obmep.org.br\/blog\/wp-json\/wp\/v2\/pages\/219861\/revisions"}],"predecessor-version":[{"id":219931,"href":"https:\/\/clubes.obmep.org.br\/blog\/wp-json\/wp\/v2\/pages\/219861\/revisions\/219931"}],"wp:attachment":[{"href":"https:\/\/clubes.obmep.org.br\/blog\/wp-json\/wp\/v2\/media?parent=219861"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}