Então compartilhe a solução ! Enviado via iPhone
> Em 28/02/2014, às 23:08, "Benedito" <bened...@ufrnet.br> escreveu: > > 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: owner-ob...@mat.puc-rio.br [mailto:owner-ob...@mat.puc-rio.br] Em nome de > terence thirteen > Enviada em: segunda-feira, 24 de fevereiro de 2014 13:12 > Para: obm-l@mat.puc-rio.br > 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<bened...@ufrnet.br> escreveu: >> OK Bernado. >> Vou dar uma olhada. >> Obrigado. >> Benedito >> >> -----Mensagem original----- >> De: owner-ob...@mat.puc-rio.br [mailto:owner-ob...@mat.puc-rio.br] 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 <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 >> ====================================================================== >> === >> >> >> --- >> 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 > ========================================================================= -- 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 =========================================================================
