No primeiro passo, existem 8 possibilidades para o cavalo atingir. -- Open WebMail Project (http://openwebmail.org)
---------- Original Message ----------- From: terence thirteen <[email protected]> To: [email protected] Sent: Mon, 24 Feb 2014 13:12:27 -0300 Subject: Re: [obm-l] Problema do Cavalo > Uma pergunta além: você quer saber quantas casas foram atingidas ao > final do percurso, certo? No seguinte sentido: > > No primeiro passo, ele pode atingir até 4 casas. Na segunda, estas 4 > casas não contam mais, mas apenas os lugares a partir do qual elas > chegam. > > Em 19/02/14, Benedito<[email protected]> escreveu: > > OK Bernado. > > Vou dar uma olhada. > > Obrigado. > > Benedito > > > > -----Mensagem original----- > > De: [email protected] [mailto:[email protected]] Em nome > > de Bernardo Freitas Paulo da Costa > > Enviada em: terça-feira, 18 de fevereiro de 2014 18:00 > > Para: Lista de E-mails da OBM > > Assunto: Re: [obm-l] Problema do Cavalo > > > > 2014-02-18 14:30 GMT-03:00 Benedito <[email protected]>: > >> > >> É infinito nos quatro quadrantes, que é para permitir muitos movimentos. > >> > >> De: [email protected] [mailto:[email protected]] Em > >> nome de terence thirteen Enviada em: segunda-feira, 17 de fevereiro de > >> 2014 08:16 > >> Para: obm-l > >> Assunto: Re: [obm-l] Problema do Cavalo > >> > >> Ele é infinito nos quatro quadrantes? > >> > >> Eu tentaria algo como construir um grafo infinito, mas vou pensar > >> antes... > > > > Eu tenho uma idéia de solução no braço. Supondo que a questão seja: > > "Qual é o número de casas diferentes em que um cavalo pode terminar uma > > seqüência de N movimentos". Assim, para n = 1, temos 8 casas (brancas), e > > para n = 2 temos 33 casas (pretas, incluindo a casa preta original!). > > > > Para n maior, a seqüência fica assim (feito num computador, na marra): > > > > 8; 33; 76; 129; 196; 277; 372; 481; 604; 741; 892; 1057; 1236; 1429; ... > > > > Agora, vem o chute principal (que é o que vai ajudar a gente a fazer > > indução): Calcule as diferenças sucessivas dos elementos! Isso dá: > > > > 25; 43; 53; 67; 81; 95; 109; 123; 137; 151; 165; 179; 193; ... > > > > Ainda não parece bom ? Não tem problema... Mais uma vez, faça as > > diferenças: > > > > 18; 10; 14; 14; 14; 14; 14; 14; 14; 14; 14; 14; ... > > > > Ahhhhhhhhhhhhh ! Parece que é uma PA de segunda ordem, a partir de um certo > > ponto... > > > > Vamos entender essa idéia. No "longo prazo", o cavalo vai se afastando do > > centro, e portanto ele pode cobrir uma área no máximo proporcional a N^2. > > Isso por si só já justifica tentar achar uma PA de segunda ordem. O que é > > interessante é que a parte perto do centro (depois do início, onde ainda há > > um monte de buracos meio aleatórios) estará completamente coberta depois de > > um certo tempo, e o que interessa é o que acontece nas "coroas". Agora, tem > > que justificar que as coroas têm uma espessura constante depois de passada > > a > > parte "transiente" > > inicial. > > > > Como eu usei um computador, e posso calcular mais do que n = 10 (por > > exemplo > > n = 100) e os 14 continuam até esse ponto. Para mim, isso é mais do que > > suficiente para eu ter certeza que a resposta é essa, mas admito que falta > > um argumento garantindo que "basta observar um número finito de passos" > > para > > acertar a recorrência. Eu diria que, como um cavalo "completa" a vizinhança > > do ponto inicial (o 3x3 em volta da > > origem) em uma quantidade finita de passos (basta chegar na profundidade 3 > > do grafo do Torres) a recorrência não pode ser de ordem muito maior do que > > isso. Para melhorar, veja que a partir de 3 passos, o que temos é um > > octógono, TODO preenchido, dos quadrados brancos (que são os únicos em que > > o > > cavalo pode estar!). Daí pra frente, não é difícil ver que a cada etapa > > teremos um octógono com lado aumentando de 1 a cada vez. Veja também que a > > partir do 3o termo da segunda diferença, só tem 14. Não é coincidência. > > > > Agora, eu deixo a indução para você completar! > > > > Abraços, > > -- > > Bernardo Freitas Paulo da Costa > > > > -- > > Esta mensagem foi verificada pelo sistema de antivírus e acredita-se estar > > livre de perigo. > > > > > > ========================================================================= > > Instruções para entrar na lista, sair da lista e usar a lista em > > http://www.mat.puc-rio.br/~obmlistas/obm-l.html > > ========================================================================= > > > > > > --- > > Este email está limpo de vírus e malwares porque a proteção do avast! > > Antivírus está ativa. > > http://www.avast.com > > > > > > -- > > Esta mensagem foi verificada pelo sistema de antivírus e > > acredita-se estar livre de perigo. > > > > > > ========================================================================= > > Instruções para entrar na lista, sair da lista e usar a lista em > > http://www.mat.puc-rio.br/~obmlistas/obm-l.html > > ========================================================================= > > > > -- > /**************************************/ > [UTF-8?]ç¥ãç¥ç¦ > > Torres > > -- > Esta mensagem foi verificada pelo sistema de [UTF-8?]antivírus e > acredita-se estar livre de perigo. > > ========================================================================= > [UTF-8?]Instruções para entrar na lista, sair da lista e usar a lista em > http://www.mat.puc-rio.br/~obmlistas/obm-l.html > ========================================================================= ------- End of Original Message ------- -- Esta mensagem foi verificada pelo sistema de antivírus e acredita-se estar livre de perigo.
