Alguns tipos
de quebra-cabeças podem ser resolvidos através da aplicação do princípio da
indução. Na maior parte dos casos, o quebra-cabeça envolve vários participantes
com uma capacidade de raciocínio e a solução do quebra-cabeça é baseada na
identificação de um caso óbvio (caso base), e a solução do problema é obtida a
partir da solução de casos menores (passo de indução) aplicando um raciocínio dos participantes.
O assunto de
indução é um assunto bastante recorrente nesse blog:
A seguir,
vamos mostrar alguns exemplos de utilização mais criativa da indução para
resolver quebra-cabeças:
Exemplo1:
Um número
ímpar de pessoas está em um campo com distâncias distintas entre eles. Ao mesmo
tempo, cada pessoa joga uma torta em seu vizinho mais próximo, acertando essa
pessoa. Use a indução matemática para mostrar que há pelo menos um
sobrevivente, ou seja, pelo menos uma pessoa que não é acertada por uma torta. Este problema foi introduzido por Carmony [Ca79]. Retirado do livro Matemática Discreta e suas aplicações [Ken09].
Considere P(n)
como a proposição de que há um sobrevivente sempre que 2n+1 pessoas estiverem
paradas em um campo com distâncias diferentes entre elas e cada pessoa joga uma
torta em seu vizinho mais próximo. Para demonstrar esse resultado, mostraremos
que P(n) é verdadeira para todos os números inteiros positivos. Note que uma
pessoa não pode ser atingida em uma guerra
de tortas porque não há ninguém mais para jogar a torta.
CASO BASE: Quando n=1, há 2n+1 =
3 pessoas na guerra de tortas. Dessas três pessoas, suponha que o par mais
próximo seja A e B, e C seja a terceira
pessoa. Como a distância entre os pares de pessoas é diferentes, dist(A,C) !=
dist(B,C) != dist(A,B) e dist(A,C) !=
dist(B,C) > dist(A,B). Temos que A joga a torta em B e B joga a torta em A, enquanto C joga a torta
em A ou B. Assim, C não é atingido por nenhuma torta. Isso mostra que pelo
menos uma das três pessoas não é atingida por uma torta, completando o passo
base.
PASSO DE INDUÇÃO: Para este
passo, assuma que P(k) seja verdadeiro. Devemos mostrar que se a hipótese
indutiva P(k) é verdadeira, então P(k+1) também é verdadeira.
Suponha que
tenhamos 2(k+1)+1 = 2k+3 pessoas em um campo com distâncias diferentes entre os
pares de pessoas. Considere A e B como o par mais próximo de pessoas nesse
grupo de 2k+3 pessoas. Cada uma delas joga uma torta na pessoa mais próxima, A
e B jogam as tortas entre si.
CASO I:
Se mais alguém jogar uma torta em
A ou B, então pelo menos três tortas serão jogadas em A ou B e no máximo (2k+3)
- 3 = 2k são jogadas nas 2k+1 pessoas restantes. Isso garante que pelo menos
uma pessoa será sobrevivente, pois se cada uma dessas 2k+1 pessoas foram
atingidas por pelos menos uma torta, um total de pelo menos 2k+1 tortas foram
jogadas nelas. (Princípio da casas dos pombos)
CASO II:
Se ninguém mais jogar uma torta
em A ou B. Além de A e B, existem 2k+1 pessoas. Como a distância entre os pares
dessas pessoas são todas diferentes, podemos usar a hipótese indutiva para concluir
que há pelo menos um sobrevivente S quando essas 2k+1 pessoas jogam as tortas
em seus respectivos vizinhos mais próximos. Além disso, S também não é atingido
por qualquer uma das tortas jogadas por essas 2k+3 pessoas.
Exemplo 2:
Em uma reunião
de N sábios lógicos, N >= 3, são distribuídos aleatoriamente chapéus que
podem ser branco ou preto, sobre as seguintes circunstâncias:
a) Cada sábio
pode ver os chapéus de todos os outros participantes da reunião, mas não pode
ver seu próprio chapéu;
b) Os participantes
da reunião não podem se comunicar.
c) Existe pelo
menos um sábio lógico com um chapéu preto.
Se existir
apenas um chapéu preto, exatamente depois da primeira hora, somente o sábio
lógico com o chapéu preto deve levantar a mão. Se existirem n sábios lógicos
com chapéus pretos, exatamente depois da n-ésima hora, somente os n sábios
lógicos com chapéus pretos devem levantar as mãos.
Considere P(n)
como a proposição de que se existirem n chapéus pretos na reunião dos sábios
lógicos então os n sábios lógicos com chapéus pretos vão levantar as mãos
exatamente na n-ésima hora. Observe que o problema garante que existe pelo
menos um sábio lógico com um chapéu preto.
CASO BASE: Suponha uma festa com
apenas um chapéu preto. Podemos separar os sábios em dois casos:
Caso 1: O sábio lógico que está
com o único chapéu preto pode ver o chapéu dos outros participantes da festa.
Este sábio vê apenas sábios com chapéus brancos, então ele deduz que está com o
chapéu preto. Na primeira hora, este sábio levanta a mão.
Caso 2: O sábio lógico, que não
está com o único chapéu preto, pode ver o chapéu de todos os outros
participantes da festa. Este sábio vê outro sábio com chapéu preto e não faz
nada na primeira hora. Depois da primeira hora, ele descobre que a cor do seu
chapéu é branca porque o sábio que levantou a mão viu a cor do seu chapéu.
PASSO DE INDUÇÃO: Para este
passo, assuma que P(k) seja verdadeiro. Devemos mostrar que se a hipótese
indutiva P(k) é verdadeira, então P(k+1) também é verdadeira.
Suponha uma reunião dos sábios
com n+1 chapéus pretos. Por hipótese de indução, ninguém levantou a mão na
n-ésima hora. Podemos separar os sábios em dois casos:
Caso 1: Os sábios que estão vendo
n chapéus pretos. Por hipótese de indução, ninguém levantou a mão na n-ésima
hora porque temos n+1 chapéus pretos. Então cada sábio que viu n chapéus pretos
deduz que está com chapéu preto também. Observe que teremos n+1 sábios satisfazendo
essa afirmação. Na (n+1)-ésima hora, todos esses sábios vão levantar a mão.
Caso 2: Os sábio que estão vendo
n+1 chapéus pretos. Por hipótese de indução, ninguém levantou a mão na n-ésima
hora porque temos n+1 chapéus pretos. Este sábio não faz nada na (n+1)-ésima hora.
Depois da (n+1)-ésima hora, ele descobre que a cor do seu chapéu é branca
porque os outros sábios que levantaram a mão viram a cor do seu chapéu.
O quebra-cabeça dos chapéus é um problema de lógica que remonta desde 1961 [Gar61]. Uma variação deste problema foi apresentada por Todd Ebert em 1998 [Ebe88] na sua tese de doutorado. Na sua variação, os jogadores podem colaborar em times e decidir uma estratégia antes do jogo começar. Contudo, os jogadores tem somente uma chance de decidir a cor do seu chapéu. Este problema tem uma conexão interessante com teoria da informação e a teoria de jogos cooperativos.
Outros referências:
An Introduction to Infinite Hat ProblemsPrisoners and hats puzzle
A Dozen Hat Problems
The Hat Problem
The Hat Problem And Some Variations
[Ca79]L. Carmony, "Odd Pie Fights", Mathematics Teacher 72 (January 79) 61-64
[Ken09] Matemática Discreta e suas Aplicações
, Kenneth H. Rosen
, Mc-Graw Hill, Tradução da 6a. edição em inglês, 2009, ISBN
978-85-77260-36-2.
[Gar61] Martin Gardner. The 2nd Scientific American Book of Mathematical Puzzles & Diversions. Simon and Schuster, New York,1961
[Ebe88] Todd Ebert. Applications of recursive operators to randomness
and complexity. PhD thesis, University of California at Santa
Barbara, 1988.
Nenhum comentário:
Postar um comentário