|
From the late 1970’s to the late 1990’s, Raymond
Smullyan, a professor of Mathematics and Philosophy
from New York, published several books containing
an eclectic mix of riddles, logic puzzles and
brain teasers to appeal to adults and children
alike (Smullyan, 1978,
1979, 1981
, 1982, 1982,
1985, 1987,
1992 , 1997).
The puzzles are at once quaint and challenging and
many are embedded in scenarios taken from popular
literature and folklore such as Alice in Wonderland
(Smullyan, 1982),
The Arabian Knights (Smullyan, 1981)
and Sherlock Holmes (Smullyan, 1979).
Aside from his respected academic work Smuyllan’s
career spans that of musician, writer, humorist
and even children’s magician. The charisma and charm
of his writing has introduced many newcomers to
the pleasure of mental puzzles. In this paper
we select a range of Smullyan’s logic puzzles
and demonstrate how modeling logical conditions
using IP can be applied to produce solutions.
The puzzles we have chosen include some that are
solvable with a moment’s reflection to one where
it seems impossible to know where to start (‘Logical
labyrinth’ Section 2.2).
The importance of making learning fun was emphasized
in a previous paper where we demonstrated the
applicability of IP as a means of solving chessboard
placement puzzles (Chlond, and Toase, 2002).
As we continue to look for ways to encourage those
students with little confidence in concepts they
perceive to be mathematical we found the discovery
of the applicability of IP to a whole new problem
type to be exciting. Certainly, in our teaching
experience so far, student response has been very
positive.
The first two puzzles are taken from What
is the Name of this Book? (Smullyan, 1978).
Suppose you are visiting a forest in which every
inhabitant is either a knight or a knave. Knights
always tell the truth and knaves always lie. In
addition some of the inhabitants are werewolves
and have the annoying habit of sometimes turning
into wolves at knight and devouring people. A
werewolf can be either a knight or a knave.
|
You are interviewing three inhabitants, A, B,
and C, and it is known that exactly one of them is a werewolf.
They make the following statements:
| |
A: I am a werewolf. |
| |
B: I am a werewolf. |
| |
C: At most one of
us is a knight. |
Give a complete classification
of A, B and C.
|
|
This time we get the following statements:
| |
A: At least one of
the three of us is a knave. |
| |
B: C is a knight. |
Given that there is exactly one
werewolf and that he is a knight, who is the werewolf?
|
The next two puzzles are taken from The Lady
or the Tiger (Smullyan, 1982).
The relevant chapter, Ladies or Tigers, contains
12 puzzles of increasing difficulty. In each puzzle a prisoner
is faced with a decision where he must open one of several
doors. In the first few examples each room contains either
a lady or a tiger and in the more difficult examples rooms
may also be empty. We have chosen to include one of the simplest
and the most difficult.
If the prisoner opens a door to find a lady he
will marry her and if he opens a door to find a tiger he will
be eaten alive. We assume that the prisoner would prefer to
be married than eaten alive. It is also assumed that the lady is in some way special to the prisoner and
he would prefer to find and marry her rather than open a door into an empty
room. Each of the doors has a sign bearing a statement that may be either true or false.
|
This puzzle involves two rooms.
The statement on door one says, "At least one of these
rooms contains a lady." The statement on door two says,
"A tiger is in the other room." The statements are either
both true or both false.
|
|
The final puzzle in this section
of the book involves nine rooms. The statements on the
nine doors are:
| |
Door 1 |
|
The lady is in an odd-numbered
room |
| |
Door 2 |
|
This room is empty |
| |
Door 3 |
|
Either sign 5 is right or sign
7 is wrong |
| |
Door 4 |
|
Sign 1 is wrong |
| |
Door 5 |
|
Either sign 2 or sign 4 is right |
| |
Door 6 |
|
Sign 3 is wrong |
| |
Door 7 |
|
The lady is not in room 1 |
| |
Door 8 |
|
This room contains a tiger and
room 9 is empty |
| |
Door 9 |
|
This room contains a tiger and
sign 6 is wrong |
In addition, the prisoner is informed
that only one room contains a lady; each of the others
either contains a tiger or is empty. The sign on the
door of the room containing the lady is true, the signs
on all the doors containing tigers are false, and the
signs on the doors of empty rooms can be either true
or false.
The puzzle as stated does not
have a unique solution until the prisoner is told whether
or not room eight is empty and this knowledge enables
him to find a unique solution.
|
It is useful to develop linear constraints to
force an indicator variable to 1 if and only if a particular
proposition is true. Four examples are presented as follows.
In each case x = [ x1, x2,
.., xc ], Fx is a linear function
of x and U
and L are upper and lower bounds respectively on Fx.
δ = 1 if Fx ≥ n, 0 otherwise
| Fx - ( U - n + 1 ) δ ≤ n - 1 |
(1) |
|
δ= 1 if Fx ≤ n, 0 otherwise
| Fx + ( n + 1 - L ) δ ≥ n + 1 |
(3) |
|
| Fx + (U - L) δ ≤ n + U - L |
(4) |
|
δ = 1 if Fx = n, 0 otherwise
In the two special cases where n = L or n = U , it is equivalent and simpler to model the expressions Fx ≤ n or Fx ≥ n respectively, rather than Fx = n. If neither of these is the case then we may enforce the condition in three steps as follows:
(i) δ1 = 1 if Fx ≥ n, 0 otherwise
| Fx - ( U - n + 1 ) δ1 ≤ n - 1 |
(5) |
|
| Fx - ( n - L ) δ1 ≥ L |
(6) |
|
(ii) δ2 = 1 if Fx ≤ n, 0 otherwise
| Fx + ( n + 1 - L ) δ2 ≥ n+1 |
(7) |
|
| Fx + ( U - L ) δ2 ≤ n + U - L |
(8) |
|
(iii) δ = 1 if Fx ≤ n Λ Fx ≥ n, 0 otherwise
An equivalent statement is δ = 1 if δ1 + δ2 = 2, 0 otherwise. Note that at least one of conditions (i) and (ii) must hold, therefore δ1 + δ2 ≥ 1. Hence, the single constraint
is sufficient.
δ = 1 if Fx ≠ n, 0 otherwise
Constraints (5) to (8) may be applied and constraint (9) is replaced by
The use of indicator variables in conjunction with propositions as shown above may be extended to enforce relationships between propositions.
We define indicator variables δi such that δi = 1 if proposition Xi is true and 0
if Xi is false. The following equivalencies taken from Williams
(1999) will prove useful.
X1 Λ X2 is equivalent to δ1 + δ2 = 2
X1 V X2 is equivalent to δ1 + δ2 ≥ 1
~X1 is equivalent to δ1 = 0
X1 → X2 is equivalent to δ1 ≤ δ2
X1 ↔ X2 is equivalent to δ1 = δ2
X1 ↔ ~X2 is equivalent to δ1 = 1 - δ2
The aim of the puzzles is to find a solution where all the statements are consistent. In most cases we may therefore choose any objective function.
Define variables xi = 1 if person i is a knight
and 0 if a knave and yi = 1 if person i
is a werewolf and 0 otherwise for i = 1,...,3.
As stated above we choose an arbitrary objective
function, for example
Maximize x1
Subject to the stated conditions modeled as follows.
Only one person is a werewolf
y1 + y2 +
y3 = 1
If the statement made by A is true then A is
a knight. More formally
y1 = 1 ↔ x1 = 1
and this is modeled quite simply by
y1 = x1
Similarly, if the statement made by B is true
then B is a knight is represented by
y2 = x2
If the statement made by C is true then C is
a knight or
x1 + x2 + x3 ≤ 1 ↔ x3 = 1
and this may be modeled using constraints (3) and (4) and substituting Fx = x1 + x2 + x3, δ = x3, n = 1, U = 3 and L = 0 as follows
x1 + x2 + 3x3 ≥ 2
x1 + x2 + 4x3 ≤ 4
An Excel spreadsheet to solve the puzzle is here 
and an Xpress-Mosel model is here  .
If the statement by A is true then A is a knight.
More formally,
x1 + x2 + x3 ≤ 2 ↔ x1 = 1
and this may be modeled using constraints (3) and (4) and substituting Fx = x1+ x2+ x3, δ = x1, n = 2, U = 3 and L = 0 as follows
4x1 + x2 + x3 ≥ 3
4x1 + x2 + x3 ≤ 5
If the statement by B is true then B is a knight, or
x3 = 1 ↔ x2 = 1
which is modeled by
x3 = x2
Only one person is a werewolf
y1 + y2 + y3 = 1
The werewolf is a knight
xi ≥ yi for i = 1,..,3.
An Excel spreadsheet to solve the puzzle is here
and an Xpress-Mosel model is here .
Define subscripts i = 1,..,2 for doors and j =1,..,2 for prizes (1 – lady, 2 – tiger)
and variables as follows:
xi,j = 1 if door i hides
prize j, 0 otherwise
ti = 1 if statement on door
i is true, 0 otherwise
Any objective function would work. For example
Max x1,1
Each door hides one prize
The logical condition we wish to model for door
1 is
t1 = 1 ↔ x1,1 + x2,1 ≥ 1
and the constraints to enforce this condition are
x1,1 + x2,1 - 2t1 ≤ 0
x1,1 + x2,1 - t1 ≥ 0
The condition implied by the statement on door 2 is
t2 = 1 ↔ x1,2 = 1
and the necessary constraint is
t2 = x1,2
In addition, we must constrain that the two statements are either both true or both false as follows.
t1 = t2
An Excel spreadsheet to solve the puzzle is here
and an Xpress-Mosel model together with a brief explanation
of output is here .
We will now apply the above modeling structures
to the rather more difficult Logical Labyrinth puzzle from
Section 2.2.2.
Define subscripts i = 1,..,9 and j = 1,..,3 (1 – lady, 2 – tiger, 3
– empty) and as above variables are
xi,j = 1 if door i hides
prize j, 0 otherwise
ti = 1 if statement on door
i is true, 0 otherwise
We will commence by using the following arbitrary
objective function
Max x1,1
We now list the statements from the nine doors
and state the relationship between the truth or falsity of
each statement and the appropriate ti variable.
Linear constraints are developed in each case to enforce these
relationships.
Door 1 – the lady is in an odd-numbered room.
t1 = 1 ↔ x1,1 + x3,1 + x5,1 + x7,1+ x9,1= 1
This may be enforced by
t1 = x1,1 + x3,1 + x5,1 + x7,1 + x9,1
Door 2 – This room is empty.
t2 = 1 ↔ x2,3 = 1
enforced by
t2 = x2,3
Door 3 – Either sign 5 is right or sign 7 is wrong.
t3 = 1 ↔ t5 + x1,1 ≥ 1
enforced by
t5 + x1,1 – 2t3 ≤ 0
t5 + x1,1 – t3 ≥ 0
Door 4 – Sign 1 is wrong.
t4 = 1 ↔ t1 = 0
enforced by
t4 = 1 – t1
Door 5 – Either sign 2 or sign 4 is right.
t5 = 1 ↔ t2 + t4 ≥ 1
enforced by
t2 + t4 – 2t5 ≤ 0
t2 + t4 – t5 ≥ 0
Door 6 – Sign 3 is wrong.
t6 = 1 ↔ t3 = 0
t6 = 1 – t3
Door 7 – The lady is not in room 1.
t7 = 1 ↔ x1,1 = 0
enforced by
t7 = 1 – t11
Door 8 – This room contains a tiger and room 9 is empty.
t8 = 1 ↔ x8,2 + x9,3 ≥ 2
enforced by
x8,2 + x9,3 – 2t8 ≤ 1
x8,2 + x9,3 – 2t8 ≥ 0
Door 9 – This room contains a tiger and room 9 is empty
t9 = 1 ↔ x9,2 + t3 ≥ 2
enforced by
x9,2 + t3 – 2t9 ≤ 1
x9,2 + t3 – 2t9 ≥ 0
Further conditions of the puzzle are modeled as follows.
Each door hides one prize
Only one room contains a lady.
The sign on the lady’s door is true.
ti ≥ xi,1 for i = 1,...,9
The sign on the tigers’ doors are false.
ti ≤ 1 - xi,2 for i = 1,...,9
An Excel spreadsheet to solve the puzzle is here
and an Xpress-Mosel model is here .
Experimentation with
the model reveals that if the prisoner had been told that
room eight was empty he could not have identified the location
of the lady. That is, if x8,3 is forced
to 1 there is no single feasible solution. He must therefore
have been informed that room eight was not empty. This additional
feature requires the constraint
x8,3 = 0
and the revised model uniquely identifies the
whereabouts of the lady.
Our experience indicates that the challenge to
solve increasingly difficult puzzles provides students with
sufficient motivation to master the logical modeling techniques
and the drudgery normally associated with drill exercises
is scarcely noticed.
Finally, an added educational value in drawing
parallels between diverse problem situations is that it may
lead the students to infer the need for thinking laterally
in the search for solutions to the myriad of complex real
world business problems.
Chlond M. J. and
C.M. Toase (2002), "IP Modeling of Chessboard Placements and
Related Puzzles," INFORMS Transactions on Education,
Vol. 2, No. 2,
Smullyan, R. (1978),
What is the Name of this Book?, Prentice-Hall, NJ.
Smullyan, R. (1979),
The Chess Mysteries of Sherlock Homes, Alfred A.
Knopf, Inc., New York, NY.
Smullyan, R. (1981),
The Chess Mysteries of the Arabian Knights, Alfred
A. Knopf, Inc., New York, NY.
Smullyan, R. (1982),
The Lady or The Tiger, Alfred A. Knopf, Inc., New
York, NY.
Smullyan, R. (1982),
Alice in Puzzleland, William Morrow and Company Inc.,
New York, NY.
Smullyan, R. (1985),
To Mock a Mockingbird, Alfred A. Knopf, Inc., New
York, NY.
Smullyan, R. (1987),
Forever Undecided: A Puzzle Guide to Godel, Alfred
A. Knopf, Inc., New York, NY.
Smullyan, R. (1992),
Satan, Cantor and Infinity, Alfred A. Knopf, Inc.,
New York, NY.
Smullyan, R. (1997),
The Riddle of Scheherezade, Alfred A. Knopf, Inc.,
New York, NY.
Williams H.P. (1999),
Model Building in Mathematical Programming, John
Wiley & Sons, New York, NY.
 |
To download a printable version (pdf) of this paper, click here. To download the Adobe Acrobat reader for viewing and printing pdf files, click here. |
 |
To
reference this paper, please use:
Chlond, M.J. and C.M. Toase (2003), "IP Modeling and the Logical Puzzles of Raymond Smullyan," INFORMS Transactions on Education, Vol. 3, No 3,
http://ite.pubs.informs.org/Vol3No3/ChlondToase/
|
|
Volume 3, Number 3, May 2003
