Hoje, tenho dois problemas meio relacionados. O primeiro, Lemmings, vem do site do William Wu, é meu velho conhecido, e possui uma das soluções mais bonitas e surpreendentes que já vi. De fato, quando alguém me pede um exemplo das “epifanias” que experimentamos ao resolver problemas como os deste site, é no Lemmings que penso primeiro. Aqui vai.
Boiando num lago de Problemópolis há uma tábua estreita de 100m de comprimento. Sobre esta tábua estão 20 lemmings parados (em pontos aleatórios), cada um virado (aleatoriamente) para uma das extremidades da tábua. Num dado momento, todos os 20 começam a caminhar na direção em que estão virados, e dali em diante a ação ocorre assim:
- todos os lemmings andam a 1 m/s;
- se um lemming chega ao fim da tábua, ele cai no lago;
- se dois lemmings se batem, vindo de direções opostas, cada um dá meia-volta e continua andando na direção contrária à que veio.
As perguntas são: todos os lemmings eventualmente caem na água? Em caso afirmativo, existe um tempo máximo, após o qual todos os lemmings terão caído no lago, independente da configuração inicial? Em caso afirmativo, qual o menor tempo em que isso pode ser garantido?
O segundo problema, que vi esta semana e motivou este post, é o seguinte.
Suponha que 20 lemmings estão dispostos aleatoriamente num círculo de 100m de circunferência, cada um virado numa direção aleatória (horário ou anti-horário, cada um com probabilidade 1/2). Num dado momento, todos os lemmings começam a andar (ao longo do círculo) na direção em que estão virados, e a dinâmica é exatamente a mesma de antes (exceto que ninguém “sai” do círculo). Qual a probabilidade que um lemming em particular (o Zezé), transcorridos 100 segundos, se veja no exato mesmo ponto de onde saiu?
A solução do primeiro problema é tão elegante que eu o julgava irretocável; mas a do segundo usa-a em conjunção com uma idéia ainda mais bonita.
Um conselho: no segundo problema, experimentação com casos pequenos ajuda a eliminar conjecturas tentadoras mas falsas.
aaronalb
abgrilo
André
javendo
Luís Guilherme Fernandes Pereira
mariogen
Pietro
ynotx
Problemópolis 
Exatamente 100 segundos depois no mesmo lugar ou ter passado pelo mesmo ponto em algum momento dos 100 segundos?
O primeiro problema é muito fácil mesmo 😉 Uma versão semelhante dele pode ser encontrada aqui: http://acm.uva.es/problemset/v108/10881.html (igualmente sem resposta, mas com um sistema de submissão)
Hum, esse eu não conhecia! Já consegui sacar a do primeiro, e é bacana mesmo. Meu insight foi perceber que, num certo sentido, um “idclip” não ia mudar muita coisa na situação… ;c)
O segundo exige mais elaboração, vou tentar pensar nele!
Luís: a segunda pergunta é sobre a probabilidade de um lemming se ver no exato mesmo lugar após *exatamente* 100 segundos.
Assim como tentei explicitar no primeiro problema, há várias questões a serem respondidas pra garantir que o problema está “well-posed”. Por exemplo: a probabilidade é tomada apenas sobre as 2^20 opções de {horário,anti-horário} para os 20 lemmings, ou também envolve a probabilidade contínua da colocação dos lemmings no círculo? Depende do lemming particular escolhido? Etc.
Podemos chamar os 20 lemmings de L(1), …, L(20), começando pelo Zezé, ou L(1), e seguindo no sentido horário. Denominemos ainda a posição A(i) e como a posição inicial do lemming L(i). Adicionalmente, chamaremos de B(i) a posição final (após exatos 100 segundos) do lemming L(i). A pergunta, pode então ser descrita como: A(1)=B(1)?
Perguntas que podem ajudar: qual a probabilidade de termos algum lemming na posição em que o Zezé começou (P[B(i) = A(1) para algum i])? Se tomarmos o Zezé como referência, quais as possibilidades de ordenação relativa ao cabo dos 100 segundos? Qual a probabilidade de L(2) vir logo após o Zezé no sentido horário?
Cheguei a duas conclusões que respondem a essas perguntas… Já reduzi bastante as possibilidades de disposição final dos lemmings com elas, mas ainda não consegui matar o problema…
Usando a notação do André.
Para todo i, existe um j tal que A(i) = B(j). Depois de 100 segundos, o sistema estará idêntico à posição inicial, com um ou mais lemmings na posição inicial dos lemmings anteriores. Essa é a idéia do primeiro problema que usamos no segundo.
A segunda idéia elegante ainda não apareceu na minha cabeça 😛
(Eu acho que a resposta não é 5% :P)
Seja n o número de lemmings.
Para n = 1, a probabilidade p dele estar no mesmo lugar depois de 100 segundos é 1.
Para n = 2, p também é 1. Se os dois lemmings começam na mesma direção, é óbvio que eles não se encontrarão jamais e, portanto, estarão no mesmo ponto depois de 100s. Se estão em direções opostas, distantes de L metros, andarão L/2 até se encontrarem, depois andarão (100-L)/2 e se encontrarão de novo. Ou seja, cada um só anda em uma determinada metade
Sim, para n=1 e n=2 a probabilidade é 1. Uma conjectura excessivamente otimista é p=1 para todo n. Testar alguns casos com n=3 e n=4 é muito elucidador.