Charadas de Smullyan
Desde o final dos anos 1970 ao final de 1990, Raymond Smullyan, um professor de Matemática e Filosofia de Nova York, publicou vários livros contendo uma mistura eclética de enigmas, quebra-cabeças de lógica e quebra-cabeças para atrair adultos e crianças. Os puzzles são ao mesmo tempo singulares e desafiadores e muitos são incorporados em cenários tirados da literatura popular e do folclore, como Alice no País das Maravilhas (Alice in the Pluzze-Land), Os Cavaleiros da Arábia (The Chess Mysteries of the Arabian Knights) e Sherlock Holmes (The Chess Mysteries of Sherlock Holmes).
Além de sua respeitada carreira acadêmica, Smuyllan foi músico, escritor humorista, e até mágico para crianças. O carisma e charme de sua escrita introduziu muitos recém-chegados ao prazer de quebra-cabeças mental.
Quebras-Cabeças[editar | editar código-fonte]
Cavaleiros, escudeiros e lobisomens[editar | editar código-fonte]
Os dois primeiros puzzles são tirados Qual é o nome deste livro? (What Is the Name of This Book?). Suponha que você está visitando uma floresta em que cada habitante seja um cavaleiro ou um escudeiro. Cavaleiros sempre dizem a verdade e os escudeiros sempre mentem. Além disso, alguns dos habitantes são lobisomens e tem o irritante hábito de às vezes se transformarem em lobos e devorarem pessoas. Um lobisomem pode ser um cavaleiro ou de um patife.
Lobisomens II[editar | editar código-fonte]
Você está entrevistando três habitantes, A, B e C, e sabe-se que exatamente um deles é um lobisomem. Eles fazem as seguintes declarações:
A: Eu sou um lobisomem.
B: Eu sou um lobisomem.
C: No máximo um de nós é um cavaleiro.
Dê uma classificação completa de A, B e C.
Lobisomens IV[editar | editar código-fonte]
Desta vez, temos as seguintes declarações:
A: Pelo menos um dos três de nós é um escudeiro.
B: C é um cavaleiro.
Dado que há exatamente um lobisomem e que ele é um cavaleiro, que é o lobisomem?
Senhoras ou tigres?[editar | editar código-fonte]
Os próximos dois puzzles são tomadas a partir de A Dama ou o Tigre (The Lady or the Tiger?). O capítulo em questão, senhoras ou tigres, contém 12 puzzles de dificuldade crescente. Em cada quebra-cabeça de um prisioneiro é confrontado com uma decisão onde ele deve abrir uma das várias portas. Nos primeiros exemplos de cada quarto contém tanto uma senhora ou um tigre e nos quartos mais difíceis, podem estar vazios. A seguir temos um exemplo simpels e um difícil.
Se o prisioneiro abre uma porta para encontrar uma senhora que ele vai se casar com ela e se ele abre uma porta para encontrar um tigre que ele vai ser comido vivo. Assumimos que o prisioneiro prefere se casar do que vivo comido. Supõe-se também que a senhora é, de alguma forma especial para o prisioneiro e ele preferiria encontrar e se casar com ela ao invés de um abrir uma porta para dentro e sala vazia.
Cada uma das portas tem uma placa com uma declaração que pode ser verdadeira ou falsa.
O segundo julgamento[editar | editar código-fonte]
Este quebra-cabeça envolve dois quartos.
A declaração na porta de um diz: "Pelo menos um destes quartos contém uma dama." A declaração na porta de dois diz: "Um tigre está no outro quarto." As declarações são ou ambas verdadeiras ou ambas falsas.
Um labirinto lógico[editar | editar código-fonte]
O enigma final do livro envolve nove quartos. As declarações sobre as nove portas são:
Porta 1: A senhora está em uma sala ímpar.
Porta 2: Esta sala está vazia.
Porta 3: Ou a placa de 5 é certo ou a placa da 7 está errada.
Porta 4: A placa de 1 está errada.
Porta 5: Ou a placa de 2 ou a de 4 está certa.
Porta 6: A placa de 3 está errada.
Porta 7: A senhora não está na sala 1.
Porta 8: Esta sala contém um tigre e sala 9 está vazia.
Porta 9: Esta sala contém um tigre e assinar seis está errado.
Além disso, o prisioneiro é informado de que apenas um quarto contém uma senhora; cada um dos outros ou contém um tigre ou está vazio. A placa na porta da sala contendo a senhora é verdade, os sinais em todas as portas contendo tigres são falsas, e os sinais nas portas de salas vazias pode ser verdadeira ou falsa.
O quebra-cabeça como indicado não tem uma solução única, até o prisioneiro é dito ou não sala oito é vazia e esse conhecimento permite-lhe encontrar uma solução única.
Ferramentas de modelagem[editar | editar código-fonte]
Variáveis de Indicador[editar | editar código-fonte]
É útil para desenvolver restrições lineares para forçar uma variável indicadora para 1 se e somente se uma proposição particular é verdadeira. Quatro exemplos são apresentados a seguir.
Em cada caso, , é uma função linear de x e U e L são os limites superior e inferior, respectivamente, .
- d = 1 se F x ³ n, 0 caso contrário
- F x - (U - n +1) d R n - 1 (1)
- F x - (n - L) d L ³ (2)
- d = 1 se F x £ n, 0 caso contrário
- F x + (n +1 - L) d ³ n +1 (3)
- F x + (U - L) d R n + U - L (4)
- d = 1 se F x = n, 0 caso contrário
Nos dois casos especiais, onde n = n = L ou U, é equivalente e mais simples para modelar as expressões F x £ n ou F x ³ n, respectivamente, ao invés de F x = n. Se nenhum desses for o caso, podemos fazer valer a condição de em três etapas como segue:
- (I) d1 = 1 se F x ³ n, 0 caso contrário
- F x - (U - n +1) d 1 R n - 1 (5)
- F x - (n - L) d 1 L ³ (6)
- (Ii) d2 = 1 se F x R n, 0 caso contrário
- F x + (n +1 - L) d 2 ³ n +1 (7)
- F x + (U - L) d 2 R n + U - L (8)
- (Iii) d = 1 se F x R n Ù F x ³ n, 0 caso contrário
Uma declaração equivalente é d = 1 se d 1 + d 2 = 2, 0 caso contrário. Note-se que pelo menos uma das condições (i) e (ii) deve manter, portanto, d 1 + d 2 ³ 1. Assim, a única restrição d = D 1 + d 2-1 (9) é suficiente.
- d = 1 se F x ¹ n, 0 caso contrário
Restrições (5) a (8) pode ser aplicada e restrição (9) passa a ter
- d = 2 - d1 - d2 (10)
Constrangimentos lógicos[editar | editar código-fonte]
O uso de variáveis indicadoras em conjunto com proposições como mostrado acima pode ser estendido para as relações entre proposições.
Nós definimos variáveis indicadoras d i tais que d i = 1 se i proposição X é verdadeiro e 0 se X i é falsa. As equivalências a seguir retirado Williams (1999) vai ser útil.
- Ù X 1 X 2 é equivalente a d 1 + d 2 = 2
- X 1 X 2 Ú é equivalente a d 1 + d 2 ³ 1
- ~ X 1 é equivalente a d 1 = 0
- ® X 1 X 2 é equivalente a d £ 1 d 2
- X 1 «X 2 é equivalente a d 1 = d 2
- X 1 " ~ X 2 é equivalente a d 1 = 1 - d 2
Funções Objetivas[editar | editar código-fonte]
O objetivo do quebra-cabeças é encontrar uma solução em que todas as declarações são consistentes. Na maioria dos casos, portanto, podemos escolher qualquer função objetivo.
Modelos[editar | editar código-fonte]
Lobisomens II[editar | editar código-fonte]
Definir variáveis x i = 1 i se a pessoa é um cavaleiro e um valete 0 se e y i = 1 i se a pessoa é um lobisomem e 0 caso contrário para i = 1 .. 3.
Como afirmado acima, escolha uma função objetivo arbitrária, por exemplo
Maximizar x 1
Sujeita às condições estabelecidas modelado como segue.
Apenas uma pessoa é um lobisomem
- y 1 + y 2 + y 3 = 1
Se a declaração feita por A é verdade então A é um cavaleiro. Mais formalmente
- y 1 = 1 " x 1 = 1
e esta é modelada simplesmente pela
- y 1 = x 1
Da mesma forma, se a declaração feita por B é verdadeiro então B é um cavaleiro é representado por
- y 2 = x 2
Se a declaração feita pelo C for verdade, então C é um cavaleiro ou
- x 1 + x 2 + x 3 R 1 « x 3 = 1
e isso pode ser modelado usando restrições (3) e (4) e substituindo F x = x 1 + x 2 + x 3, d = x 3, n = 1, U = 3 e L = 0 da seguinte forma
- x 1 + x 2 + 3 3x ³ 2
- x 1 + x 2 + 4x 3 £ 4
Lobisomens IV[editar | editar código-fonte]
Se a declaração por A é verdade então A é um cavaleiro. Mais formalmente,
- x 1 + x 2 + x 3 R 2 « x 1 = 1
e isso pode ser modelado usando restrições (3) e (4) e substituindo F x = x 1 + x 2 + x 3, d = x 1, n = 2, U = 3 e L = 0 da seguinte forma
- 4x 1 + x 2 + x 3 ³ 3
- 4x 1 + x 2 + x 3 £ 5
Se a declaração do B é verdadeiro então B é um cavaleiro, ou
- x 3 = 1 « x 2 = 1
que é modelada por
- x 3 = x 2
Apenas uma pessoa é um lobisomem
- 1 + y 2 + y 3 = 1
O lobisomem é um cavaleiro
- x ³ i y i para i = 1 .. 3
O segundo julgamento[editar | editar código-fonte]
Definir índices i = 1 .. 2 para portas e j = 1 .. 2 a prêmios (1 - dama, 2 - tigre) e as variáveis da seguinte forma:
x i, j = 1 se i porta esconde prêmio j, 0 caso contrário t i = 1 if i na porta é verdade, 0 caso contrário Qualquer função objetivo
- Max x 1,1
Cada porta esconde um prêmio
A condição lógica que queremos um modelo para a porta é
- t 1 = 1 "x 1,1 + 2,1 x ³ 1
e as restrições para impor essa condição são
- x 1,1 + x 2,1 - 2t £ 1 0
- x 1,1 + x 2,1 - t 1 ³ 0
A condição implícita na declaração na porta 2 é
- t 2 = 1 "x 1,2 = 1
e a restrição é necessária
- t = 2 x 1,2
Além disso, devemos restringir que as duas afirmações são ou ambos verdadeiros ou ambos falsos como se segue.
- t 1 = t 2
Um Labirinto Lógico[editar | editar código-fonte]
Vamos agora aplicar as estruturas de modelagem acima para o bem mais quebra-cabeça difícil Labyrinth Lógico da Seção 2.2.2.
Definir índices i = 1 .. 9 e j = 1 .. 3 (1 - dama, 2 - tigre, 3 - vazio) e como variáveis acima são
x i, j = 1 se i porta esconde prêmio j, 0 caso contrário
t i = 1 if i na porta é verdade, 0 caso contrário
Vamos começar usando a função seguinte objetivo arbitrária
- Max x 1,1
Temos agora a lista de depoimentos de nove portas e estadual a relação entre a verdade ou falsidade de cada afirmação e as t apropriado i variável. Restrições lineares são desenvolvidos em cada caso, para reforçar essas relações.
Porta 1 - a senhora está em uma sala de ímpares.
- t 1 = 1 "x 1,1 + 3,1 x + x + 5,1 x 7,1 x 9,1 + = 1
Isto pode ser reforçado pela
- t 1 = x 1,1 + 3,1 x + x + 5,1 x 7,1 x 9,1 +
Porta 2 - Esta sala está vazia.
- t 2 = 1 "x 2,3 = 1
imposta pelo
- t = 2 x 2,3
Porta 3 - Ou sinal de 5 é certo ou é errado sinal 7.
- 3 = 1 t «t 5 + x 1,1 ³ 1
imposta pelo
- t + 5 x 1,1 - 2t 3 £ 0
- t + 5 x 1,1 - t 3 ³ 0
4 portas - Registe-1 é errado.
- 4 = 1 t «t 1 = 0
imposta pelo
- t 4 = 1 - t 1
5 portas - Ou sinal de 2 ou 4 é sinal certo.
- 5 = 1 t «t 2 + t 4 ³ 1
imposta pelo
- t 2 + t 4 - 2t 5 £ 0
- t 2 + t 4 - t 5 ³ 0
Porta 6 - Registe-3 é errado.
- 6 = 1 t «t 3 = 0
- t 6 = 1 - t 3
Porta 7 - A senhora não está na sala 1.
- t 7 = 1 "x 1,1 = 0
imposta pelo
- t 7 = 1 - t 11
Porta 8 - Esta sala contém um tigre e sala 9 está vazia.
- t 8 = 1 "x 8,2 x 9,3 + 2 ³
imposta pelo
- x 8,2 x 9,3 + - 8 £ 2t 1
- x 8,2 x 9,3 + - 8 2t ³ 0
Porta 9 - Esta sala contém um tigre e sala 9 está vazia
- t 9 = 1 "x 9,2 t ³ + 3 2
imposta pelo
- x 9,2 + t 3 - 2t 9 £ 1
- x 9,2 + t 3 - 2t ³ 9 0
Outras condições do quebra-cabeça são modelados como se segue.
Cada porta esconde um prêmio
Apenas uma sala contém uma senhora.
O sinal na porta da senhora é verdade.
- t i ³ x i, 1 para i = 1 .. 9
O sinal nas portas dos tigres são falsas.
- t i £ 1 - x i, 2 para i = 1 .. 9
Experimentação com o modelo revela que se o preso tinha sido dito que o quarto estava vazio oito ele não poderia ter identificado a localização, a senhora. Ou seja, se x 8,3 é forçado a uma não existe uma solução única viável. Ele deve, portanto, foram informados de que oito sala não estava vazia. Este recurso adicional requer a restrição
x 8,3 = 0
e o modelo de revista identifica o paradeiro da senhora.
Referências[editar | editar código-fonte]
http://www.chlond.demon.co.uk/academic/papers/Smullyan.htm (Tradução)