2014-02-18 14:30 GMT-03:00 Benedito <bened...@ufrnet.br>: > > É infinito nos quatro quadrantes, que é para permitir muitos movimentos. > > De: owner-ob...@mat.puc-rio.br [mailto:owner-ob...@mat.puc-rio.br] 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 =========================================================================
