Desafio: bolas brancas e pretas

Os primeiros posts têm de ser um pouco mais genéricos para dar alguma base para o futuro.
Para quebrar um pouco esta rotina inicial, sugiro um desafio inspirado num problema do SPOJ e que pode ser feito a qualquer pessoa.

Desafio: bolas brancas e pretas

Imaginem que têm uma caixa de mágico com um certo número de bolas brancas e pretas.
Enquanto a caixa contém mais do que uma bola, retiram aleatoriamente 2 bolas da caixa:

• Se as 2 bolas retiradas têm a mesma cor, então colocam uma bola branca na caixa 
• Se as 2 bolas tiverem cores diferentes, então colocam uma bola preta

Em ambos os casos, as 2 bolas retiradas não voltam para a caixa. Assim, dado o número inicial de bolas brancas e bolas pretas, qual é a cor da bola que resta na caixa?

Exemplos:

• 1 bola branca e 1 bola preta. As 2 bolas retiradas têm cores diferentes, é colocada uma bola preta. Só sobra 1 bola preta.
• 2 brancas e 0 pretas. Retiram-se 2 bolas brancas e coloca-se 1 bola branca na caixa.
• 2 brancas e 1 preta. Se retirarmos primeiro as 2 bolas brancas, ficamos com 1 bola branca e 1 preta na caixa. Como vimos acima, o resultado é uma bola preta. Se começarmos por retirar 1 branca e 1 preta, adiciona-se 1 preta e voltamos a ter 1 branca e 1 preta. Em qualquer caso, o resultado é ficarmos com 1 bola preta.

E se fossem 5555555 bolas brancas e 5555555 pretas? Ou 10000000 brancas e 10000000 pretas?
Conseguem descobrir o truque para responder a qualquer caso? :-)





Solução

Em cada passo, são retiradas 2 bolas à caixa e é adicionada 1 bola, por isso, o processo termina sempre. Uma boa abordagem inicial é resolver alguns casos com poucas bolas como é dado nos exemplos. Tal como é visto no 3º exemplo, a ordem pela qual escolhemos as bolas não tem influência no resultado final. A cor da última bola é sempre a mesma.

Quer tenhamos 0, 1, 2, ..10 ou 10000000 bolas brancas, estas pouco importam. Vamos retirando 2 bolas brancas e adicionando 1, por isso, podemos ignorar o facto de termos 10000000 e considerar que temos apenas 1.
Do mesmo modo, se tivermos 10000000 bolas pretas, vamos retirando 2 bolas pretas e adicionando 1 bola branca. Assim, só é relevante saber se o número de bolas pretas é par ou ímpar. Se for par, todas as bolas pretas são transformadas em bolas brancas. Se for ímpar, sobra uma bola preta, enquanto que as outras bolas pretas são transformadas em bolas brancas.

Como vimos acima, o número de bolas pretas que é transformado em bolas brancas pouco importa, porque as N bolas brancas são reduzidas a 1. Por conseguinte, ficamos sempre com 0 ou 1 bolas brancas e 0 ou 1 bolas pretas. Se o número de bolas pretas for par, a cor da última bola será branca. Se for ímpar, a cor da última bola é preta (tal como no 1º exemplo, 1 bola branca e 1 preta dá bola preta).

Agora desafiem os vossos amigos :-)