Encontrei uma solução bonita e elementar para este problema no artigo: "Counting the Number of Squares Reaachable in k Knight's Moves, por Amanda M Miller e David L. Farnsworth, Open Journal of Discrete Mathematics, 2013, 3, 151-154. Valeu a pena estudar o problema. Benedito.
-----Mensagem original----- De: [email protected] [mailto:[email protected]] Em nome de terence thirteen Enviada em: segunda-feira, 24 de fevereiro de 2014 13:12 Para: [email protected] Assunto: 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 > ====================================================================== > === > -- /**************************************/ 神が祝福 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 ========================================================================= --- 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 =========================================================================
