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

Cavaleiros, escudeiros e lobisomens

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

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

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?

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

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

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

Variáveis de Indicador

É ú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, $x=[x1,x2,..,xc]$, $Fx$ é uma função linear de x e U e L são os limites superior e inferior, respectivamente, $Fx$.

• 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

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

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

Lobisomens II

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

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

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

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

http://www.chlond.demon.co.uk/academic/papers/Smullyan.htm (Tradução)