A third collection of puzzles to be solved using Integer Programming.

Xpress-Mosel models are available by clicking on Solution.

1. The Abbott's Puzzle

The first English puzzlist whose name has come down to us was a Yorkshireman - no other than Alcuin, Abbot of Canterbury (A.D. 735-804). Here is a little puzzle from his works, which is at least interesting on account of it's antiquity.

"If 100 bushels of corn were distributed among 100 people in such a manner that each man received three bushels, each woman two, and each child half a bushel, how many men, women, and children were there?"

Now, there are six different answers, if we exclude a case where there would be no women. But let us just say that there were just five times as many women as men, then what is the correct solution? (Dudeney)    Solution

2. The Abbott's Window

Once upon a time the Lord Abbott of St. Edmondsbury, in consequence of "devotions too strong for his head," fell sick and was unable to leave his bed. As he lay awake, tossing his head restlessly from side to side, the attentive monks noticed that something was disturbing his mind; but nobody dared ask what it might be, for the Abbott was of a stern disposition, and never would brook inquisitiveness. Suddenly he called for Father John, and that venerable monk was soon at the bedside.

"Father John," said the Abbott, "dost thou know that I came into this wicked world on a Christmas Even?"

The monk nodded assent.

"And have I not often told thee that, having been born on Christmas Even, I have no love for the things that are odd? Look there!"

The Abbott pointed to the large dormitory window, of which I give a sketch. The monk looked and was perplexed.



"Dost thou not see that the sixty-four lights add up to an even number vertically and horizontally, but that all the diagonal lines, except fourteen are of a number that is odd? Why is this?"

"Of a truth, my Lord Abbott, it is of the very nature of things, and cannot be changed."

"Nay, but it shall be changed. I command thee that certain of the lights be closed this day, so that every line shall have an even number of lights. See thou that this be done without delay, lest the cellars be locked for a month and other grievous troubles befall thee."

Father John was at his wits' end, but after consultation with one who was learned in strange mysteries (integer programming), a way was found to satisfy the whim of the Lord Abbott. Which lights were blocked up, so that those which remained added up to an even number in every line horizontally, vertically, and diagonally, while the least possible obstruction of light was caused?

Father John held that the four corners should be darkened, but the sage explained that it was desired to obstruct no more light than was absolutely necessary, and he said, anticipating Lord Dundreary, "A single pane can no more be in line with itself than one bird can go into a corner and flock in solitude. The Abbott's condition was that no diagonal lines should contain an odd number of lights." (Dudeney)    Solution

The following six puzzles are taken from Raymond Smullyan's "The Lady or the Tiger". In each puzzle a prisoner is faced with a decision where he must open one of two doors. Behind each door is either a lady or a tiger. They may be both tigers, both ladies or one of each.

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. Of course, the prisoner would prefer to be married than eaten alive.

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

3. The First Trial

The statement on door one says, "In this room there is a lady, and in the other room there is a tiger."

The statement on door two says, "In one of these rooms there is a lady, and in one of these rooms there is a tiger."

The prisoner is informed that one of the statements is true and one is false.    Solution

4. The Second Trial

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 true or both false.    Solution

5. The Third Trial

The statement on door one says, "Either a tiger is in this room or a lady is in the other room."

The statement on door two says, "A lady is in the other room."

The statements are either both true true or both false.    Solution

6. The Fourth Trial

The statement on door one says, "Both rooms contain ladies."

The statement on door two says, "Both rooms contain ladies."

If a lady is in room one then the statement on that door is true, otherwise it is false. If a lady is in room two then the statement on that door is false, otherwise it is true.    Solution

7. The Fifth Trial

The statement on door one says, "At least on room contains a lady."

The statement on door two says, "The other room contains a lady."

If a lady is in room one then the statement on that door is true, otherwise it is false. If a lady is in room two then the statement on that door is false, otherwise it is true.    Solution

8. The Sixth Trial

The statement on door one says, "It makes no difference which room you pick."

The statement on door two says, "There is a lady in the other room."

If a lady is in room one then the statement on that door is true, otherwise it is false. If a lady is in room two then the statement on that door is false, otherwise it is true.    Solution

The following two logic puzzles are taken from Smullyan's "What is the Name of this Book?"

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.

9. 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   Solution

10. 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?    Solution

11. The Earthlings

August 2002.

The spaceship landed.

"Earth!" they shouted.

They knew that earthlings are divided into three groups: those who always tell the truth, those who always lie, and those who do both, alternating between true and false statements, starting with either.

"Let's go!" said the captain.

The aliens approached three earthlings, who each were from a different group, and asked, "Who won the last World Cup? Who came in second? Who came in third?"

One of them responded, "Zaire first. Uruguay second. Spain third."

Another one said, "Zaire first. Spain second. Uruguay third."

The third one said, "Uruguay first. Spain second. Zaire third."

The aliens returned to their spaceship and flew back to where they came from.

Do you know which response was the true ranking in the World Cup? (Poniachek)    Solution

12. Equal Vision

Each watchman looks in all directions (horizontal, vertical and diagonal). On the board below, each watchman has five vacant cells under his gaze. A watchman can see beyond another watchman.

What is the maximum number of watchmen that can be placed so that each sees six empty cells?

What if each watchman must see seven empty cells? (Poniachek)



   Solution

Dudeney, H.E., (1917), Amusements in Mathematics, Thomas Nelson and Sons.
Poniachik, J. & L., (1998), Hard-to-Solve Brainteasers, Sterling.
Smullyan, R., (1991), The Lady or The Tiger, Oxford University Press
Smullyan, R., (1978), What is the Name of this Book?, Prentice-Hall

f