O Gandalf tem de ir ajudar alguns Hobbits mas a tarefa não parece ter fim... Dás-lhe uma ajudinha?

a picture of the Shire

Neste artigo encontras mais um problema e uma proposta de solução. Se encontrares algum erro ou se tiveres uma solução diferente, faz-me saber na secção de comentários em baixo!

Enunciado

O Shire é um sítio muito aprazível onde \(N\) Hobbits vivem em perfeita harmonia. Ou viviam, até que um Hobbit decidiu tornar-se decorador de exteriores e convenceu alguns dos seus amigos a pintar as suas portas num tom de roxo muito na moda (as portas eram todas amarelas até à data).

Da noite para o dia a harmonia em que os Hobbits viviam desapareceu e a discórdia entre Hobbits com portas de cores diferentes instalou-se.

Preocupado, o sábio Gandalf apressou-se a chegar ao Shire para tentar ajudar os Hobbits. Isto foi o que ele decidiu fazer: ele vai visitar cada Hobbit, por ordem alfabética. Ao visitar um Hobbit, o Gandalf vai mudar a cor da porta dele se houver mais Hobbits zangados com ele do que Hobbits que estão bem com ele. Depois de visitar todos os Hobbits uma vez, o Gandalf vai voltar a visitá-los a todos pela mesma ordem, e depois outra vez, e outra vez, ..., repetindo este processo até que uma ronda inteira de visitas já não faça diferença.

Será que a tarefa do Gandalf tem sempre um fio, independentemente de \(N\) e da trapalhada de cores que os Hobbits criem? Ou será que há valores de \(N\) e maneiras de pintar as portas do Shire de modo a que o Gandalf entre num ciclo infinito de remodelações exteriores?

Pensa um pouco... Pega numa folha de papel e simula algumas configurações!

Se precisares de clarificar alguma coisa, não hesites em perguntar na secção de comentários em baixo.

Pista: a tarefa do Gandalf nunca é infinita.

Pista: tenta encontrar um semi-invariante; uma quantidade que só se altera num certo sentido, e que permita concluir que o Gandalf há de descansar eventualmente.

Solução

Podes encontrar a minha proposta de solução aqui, para confirmares a tua resposta.

Artigo anterior Próximo artigo

Blog Comments powered by Disqus.