Re: Mais Problemas

["The Buddha's Sun" <obuddha@xxxxxxxxxx>]

>3) Uma caixa contém 300 bolas de gude. Dois amigos participam de um
desafio,
>removendo, alternadamente, bolas da caixa. Na sua vez de jogar, cada um
pode
>remover qualquer quantidade de bolas que não seja maior que a metade das
>bolas existentes na caixa. Aquele que não puder remover perde. Imaginando
>que os dois jogam corretamente, que vencerá: o primeiro ou o segundo a
>jogar? Qual a estratégia para vencer?


Este problema deve ser de alguma olimpíada regional. É o mesmo que o único
problema que caiu em todos os níveis na segunda fase da OBM-98, com a
diferença que, neste último, era 20 ao invés de 300, e eram balas ao invés
de bolas de gude (estes caras me matam!)

Tipo, a estratégia vencedora (geral) é deixar o adversário com
2^k - 1 bolas de gude (para qualquer k natural). Este removerá de 1 a
2^(k-1) - 1 bolas, deixando
na caixa um número de bolas que fica entre 2^(k-1) e 2^k - 2.
O primeiro jogador poderá sempre remover algumas bolas de modo a deixar o
outro com 2^(k-1) - 1 balas. E assim continua-se até o adversário ser
reduzido a 2^1 - 1 = 1 bola.

Acho que é isso. Abraço,

Lucas