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 > ========================================================================= > -- /**************************************/ 神が祝福 Torres -- 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 =========================================================================
