IP Modeling and the Logical Puzzles of Raymond Smullyan

Martin J. Chlond, Cath M.Toase
Lancashire Business School
University of Central Lancashire
Preston, PR1 2HE, UK

Abstract

The ability to include logical conditions within Integer Programming (IP) models has many applications in OR/MS. Although the modeling of logical conditions in IP is simple in principle, in actual practice the exercise can be quite painstaking and prone to error. To become adept therefore it is necessary for practitioners to be well drilled. This paper presents the puzzles of Raymond Smullyan as a rich source of examples for the instructor that offer all the pedagogical features of more conventional text book examples but with added flavors of whimsy and caprice.

1. Introduction

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.

2. The Puzzles

2.1 Knights, knaves and werewolves

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.

Werewolves II

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.

Werewolves IV

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?

2.2 Ladies or Tigers?

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 gdoors. 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 an open a door into and empty room.

Each of the doors has a sign bearing a statement that may be either true or false.

The Second Trial

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.

A Logical Labyrinth

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.

3. Modeling tools

3.1 Indicator variables

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 = [ x₁, x₂, .., x_c], Fx is a linear function of x and U and L are upper and lower bounds respectively on Fx.

d=1 if Fx ³ n, 0 otherwise

Fx - (U - n+1)d £ n - 1 (1)

Fx - (n - L)d ³ L (2)

d=1 if Fx £ n, 0 otherwise

Fx+ (n+1 - L)d ³ n+1 (3)

Fx+ (U - L)d £ n+U - L (4)

d=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) d₁=1 if Fx ³ n, 0 otherwise

Fx - (U - n+1)d₁ £ n - 1 (5)

Fx - (n - L)d₁ ³ L (6)

(ii) d₂=1 if Fx £ n, 0 otherwise

Fx + (n+1 - L)d₂ ³ n+1 (7)

Fx + (U - L)d₂ £ n+U - L (8)

(iii) d=1 if Fx £ n Ù Fx ³ n, 0 otherwise

An equivalent statement is d=1 if d₁+d₂= 2, 0 otherwise. Note that at least one of conditions (i) and (ii) must hold, therefore d₁+d₂³ 1. Hence, the single constraint

d = d₁+ d₂ - 1 (9)

is sufficient.

d=1 if Fx ¹ n, 0 otherwise

Constraints (5) to (8) may be applied and constraint (9) is replaced by

d = 2 - d₁- d₂ (10)

3.2 Logical constraints

The use of indicator variables in conjunction with propositions as shown above may be extended to enforce relationships between propositions.

We define indicator variables d_i such that d_i = 1 if proposition X_i is true and 0 if X_i is false. The following equivalencies taken from Williams (1999) will prove useful.

X₁ Ù X₂ is equivalent to d₁+ d₂ = 2

X₁ Ú X₂ is equivalent to d₁+ d₂ ³ 1

~X₁ is equivalent to d₁ = 0

X₁ ® X₂ is equivalent to d₁£ d₂

X₁ « X₂ is equivalent to d₁= d₂

X₁ « ~X₂ is equivalent to d₁= 1-d₂

3.3 Objective functions

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.

4. Models

4.1 Werewolves II

Define variables x_i = 1 if person i is a knight and 0 if a knave and y_i = 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 x₁

Subject to the stated conditions modeled as follows.

Only one person is a werewolf

y₁+ y₂+ y₃ = 1

If the statement made by A is true then A is a knight. More formally

y₁ = 1« x₁= 1

and this is modeled quite simply by

y₁ = x₁

Similarly, if the statement made by B is true then B is a knight is represented by

y₂ = x₂

If the statement made by C is true then C is a knight or

x₁+ x₂+ x₃ £ 1 « x₃= 1

and this may be modeled using constraints (3) and (4) and substituting Fx = x₁+x₂+x₃, d = x₃, n = 1, U = 3 and L = 0 as follows

x₁+ x₂+ 3x₃ ³ 2

x₁+ x₂+ 4x₃ £ 4

An Excel spreadsheet to solve the puzzle is here and an Xpress-MP model is here.

4.2 Werewolves IV

If the statement by A is true then A is a knight. More formally,

x₁+ x₂+ x₃ £ 2 « x₁= 1

and this may be modeled using constraints (3) and (4) and substituting Fx = x₁+x₂+x₃, d = x₁, n = 2, U = 3 and L = 0 as follows

4x₁+ x₂+ x₃ ³ 3

4x₁+ x₂+ x₃ £ 5

If the statement by B is true then B is a knight, or

x₃ = 1 « x₂= 1

which is modeled by

x₃ = x₂

Only one person is a werewolf

y₁+ y₂+ y₃ = 1

The werewolf is a knight

x_i ³ y_i for i = 1..3

An Excel spreadsheet to solve the puzzle is here and an Xpress-MP model is here.

4.3 The Second Trial

Define subscripts i = 1..2 for doors and j=1..2 for prizes (1 – lady, 2 – tiger) and variables as follows:

x_i,j = 1 if door i hides prize j, 0 otherwise

t_i = 1 if statement on door i is true, 0 otherwise

Any objective function

Max x_1,1

Each door hides one prize

The logical condition we wish to model for door 1 is

t₁ = 1 « x_1,1 + x_2,1 ³ 1

and the constraints to enforce this condition are

x_1,1+ x_2,1 - 2t₁ £ 0

x_1,1 + x_2,1 - t₁ ³ 0

The condition implied by the statement on door 2 is

t₂ = 1 « x _1,2 = 1

and the necessary constraint is

t₂ = x _1,2

In addition, we must constrain that the two statements are either both true or both false as follows.

t₁ = t₂

An Excel spreadsheet to solve the puzzle is here and an Xpress-MP model together with a brief explanation of output is here.

4.4 A Logical Labyrinth

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

x_i,j = 1 if door i hides prize j, 0 otherwise

t_i = 1 if statement on door i is true, 0 otherwise

We will commence by using the following arbitrary objective function

Max x_1,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 t_i variable. Linear constraints are developed in each case to enforce these relationships.

Door 1 – the lady is in an odd-numbered room.

t₁ = 1 « x_1,1+ x_3,1+ x_5,1+ x_7,1+ x_9,1=1

This may be enforced by

t₁ = x_1,1+ x_3,1+ x_5,1+ x_7,1+ x_9,1

Door 2 – This room is empty.

t₂ = 1 « x_2,3= 1

enforced by

t₂ = x_2,3

Door 3 – Either sign 5 is right or sign 7 is wrong.

t₃ = 1 « t₅ + x_1,1 ³ 1

enforced by

t₅ + x_1,1 – 2t₃ £ 0

t₅ + x_1,1 – t₃ ³ 0

Door 4 – Sign 1 is wrong.

t₄ = 1 « t₁ = 0

enforced by

t₄ = 1 – t₁

Door 5 – Either sign 2 or sign 4 is right.

t₅ = 1 « t₂ + t₄ ³ 1

enforced by

t₂ + t₄ – 2t₅ £ 0

t₂ + t₄ – t₅ ³ 0

Door 6 – Sign 3 is wrong.

t₆ = 1 « t₃ = 0

t₆ = 1 – t₃

Door 7 – The lady is not in room 1.

t₇ = 1 « x_1,1 = 0

enforced by

t₇ = 1 – t₁₁

Door 8 – This room contains a tiger and room 9 is empty.

t₈ = 1 « x_8,2 + x_9,3 ³ 2

enforced by

x_8,2 + x_9,3 – 2t₈ £ 1

x_8,2 + x_9,3 – 2t₈ ³ 0

Door 9 – This room contains a tiger and room 9 is empty

t₉ = 1 « x_9,2 + t₃ ³ 2

enforced by

x_9,2 + t₃ – 2t₉ £ 1

x_9,2 + t₃ – 2t₉ ³ 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.

t_i ³ x_i,1 for i=1..9

The sign on the tigers’ doors are false.

t_i £ 1 - x_i,2 for i=1..9

An Excel spreadsheet to solve the puzzle is here and an Xpress-MP 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 x_8,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

x_8,3 = 0

and the revised model uniquely identifies the whereabouts of the lady.

6. Conclusion

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.

References

Chlond M. J., and Toase C.M., (2002), IP Modeling of Chessboard Placements and Related Puzzles, INFORMS Transactions on Education, Vol. 2, No. 2,

http://ite.informs.org/Vol2No2/ChlondToase.

Smullyan, R., (1978), What is the Name of this Book?, Prentice-Hall

Smullyan, R., (1979), The Chess Mysteries of Sherlock Homes, Alfred A. Knopf, Inc.

Smullyan, R., (1981),The Chess Mysteries of the Arabian Knights, Alfred A. Knopf, Inc.

Smullyan, R., (1982), The Lady or The Tiger, Alfred A. Knopf, Inc.

Smullyan, R., (1982), Alice in Puzzleland, William Morrow and Company Inc.

Smullyan, R., (1985), To Mock a Mockingbird, Alfred A. Knopf, Inc.

Smullyan, R., (1987), Forever Undecided: A Puzzle Guide to Godel, Alfred A. Knopf, Inc.

Smullyan, R., (1992), Satan, Cantor and Infinity, Alfred A. Knopf, Inc.

Smullyan, R., (1997), The Riddle of Scheherezade, Alfred A. Knopf, Inc.

Williams H.P., (1999), Model Building in Mathematical Programming, 4^th ed., Wiley