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

This page contains a few puzzles that are a little more challenging than those in the previous pages and also a number of nonlinear puzzles.

Xpress-Mosel models of the linear puzzles and AMPL models of the nonlinear puzzles are included with the solutions.

1. On the Road

On my way to Philadelphia, I pass five mileposts that indicate their respective distances to Philadelphia. The mileposts are at fixed intervals. What's curious is that each milepost has a two-digit number, and together the five mileposts use all the digits from 0 to 9 once. What is the smallest distance that the closest milepost can be from Philadelphia? Mileposts don't begin with 0. (Poniachek)    Solution

2.The Riddle of the Pilgrims

The Abbott of Riddlewell announced that a messenger had that morning brought news that a number of pilgrims were on the road and would require their hospitality.

"You will put them," he said, "in the square dormitory that has two floors with eight rooms on each floor. There must be at least eleven persons sleeping on each side of the building, and twice as many on the upper floor as the lower floor. Of course every room must be occupied, and you know my rule that not more than three persons may occupy the same room."

I give a plan of the two floors, from which it will be seen that the sixteen rooms are approached by a well staircase in the centre.

After the monks had solved this little problem of accomodation, the pilgrims arrived, when it was found that they were three more in number than was at first stated. This necessitated a reconsideration of the question, but the wily monks succeeded in getting over the new difficulty without breaking the Abbott's rules.

The curious point of this puzzle is to discover the total number of pilgrims. (Dudeney 1949)    Solution

3. A Logical Labyrinth

A prisoner is faced with a decision where he must open one of nine doors. The rooms behind each door may be empty or contain either a lady or a tiger.

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. The prisoner would prefer to be married than either be eaten alive or to face emptiness. Each door has a sign bearing a statement which may be either true or false.

The statements on the nine doors are:
1. The lady is an odd-numbered room
2. This room is empty
3. Either sign 5 is right or sign 7 is wrong
4. Sign 1 is wrong
5. Either sign 2 or sign 4 is right
6. Sign 3 is wrong
7. The lady is not in room 1
8. This room contains a tiger and room 9 is empty
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 contain a tiger or are 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 prisoner is told whether or not room eight is empty and this knowledge helps him find a unique solution.(Smullyan)    Solution

4. The Gentle Art of Stamp-licking

If you have a card divided into sixteen spaces (4 x 4), and are provided with plenty of stamps of the values 1d., 2d., 3d., 4d., and 5d., what is the greatest value that you can stick on the card if the Chancellor of the Exchequer forbids that you place any stamp in a straight line (that is, horizontally, vertically, or diagonally) with another stamp of similar value? Of course, only one stamp can be affixed in a space. (Dudeney 1917)    Solution

5. The Crowded Chessboard

You are given a chessboard together with 8 queens, 8 rooks, 14 bishops, and 21 knights. The puzzle is to arrange the 51 pieces on the chessboard so that no queen shall attack another queen, no rook attack another rook, no bishop attack another bishop, and no knight attack another knight. No notice is to be taken of the intervention of pieces of another type from that under consideration - that is, two queens will be considered to attack one another although there may be, say, a rook, a bishop, and a knight between them. It is not difficult to dispose of each type of piece seperately; the difficulty comes in when you have to find room for all the arrangements on the board simultaneously. (Dudeney 1917)    Solution

6. The Non-Dominating Queens

Place N queens on an order N chessboard to leave a maximum number of unattacked vacant squares. (Velucchi)    Solution

7. Enigma

Assign all-different values to the letters in these words to make the equality true in English.

ONE + ONE + TWO + TWO + THREE + ELEVEN = TWENTY

(Unknown - Herald Tribune)    Solution

8. Price Change Conundrum

Three dealers in adjacent stalls at a market were selling apples of identical quality, so they had to keep their prices equal. At the end of the day Mr Pappas had sold 10 apples, Mr Gatta 25, and Mrs Murphy 30, yet all had taken in the same total. How much did they charge and how much did they take in?

Note: The problem is possible only if the price was changed during the course of the day. Assume just one price change. (Kraitchik)    Solution

9. The Book Buyers

Four men, Peter and Paul and their sons Tom and Dick, buy books. When their purchases are completed it turns out that each man has paid for each of his books a number of dollars equal to the number of books he has bought. Each family (father and son) has spent $65. Peter has bought one more book than Tom, and Dick has bought only one book. Who is Dick's father? (Kraitchik)    Solution

10. The Shoppers

Three men - Arthur, Bernard, and Charles - with their wives - Ann, Barbara, and Cynthia - make some purchases. When their shopping is finished each finds that the average cost in dollars of the articles he or she has purchased is equal to the number of his or her purchases. Arthur has bought 23 articles more than Barbara, and Bernard has bought 11 more than Ann. Each husband has spent $63 more than his wife. Who is the husband of whom? (Kraitchik)    Solution

11. Nice Discounts

A bookstore has a nice discount policy. If you buy a $20 book today, you get a 2% discount on your next purchase. If you buy a $15 book, you get a 1.5% discount on your next purchase. That is, for each $10 you spend you get 1% discount on your next purchase. If you have to buy three books that cost $10, $20 and $30, you could buy the $30 book today, the $10 book tomorrow (on which you'll get a 3% discount), and the $20 book the following day (on which you'll get a 1% discount). Or you could buy the $30 book and the $20 book today, and the $10 book tomorrow (with a 5% discount). What is the cheapest way to buy five books priced at $10, $20, $30, $40 and $50? (Poniachek)    Solution

12. The 7-11

A customer at a 7-11 store selected four items to buy, and was told that the cost was $7.11. He was curious that the cost was the same as the store name, so he inquired as to how the figure was derived. The clerk said that he had simply multiplied the prices of the four individual items. The customer protested that the four prices should have been added, not multiplied. The clerk said that that was OK with him, but, the result was still the same, exactly $7.11. What were the prices of the four items? (Tamara)    Solution

Dudeney, H.E., (1917), Amusements in Mathematics, Thomas Nelson and Sons.
Dudeney, H.E., (1949), The Canterbury Puzzles, 7th ed., Thomas Nelson and Sons.
Kraitchik, M., (1942), Mathematical Recreations, W.W. Norton and Company.
Poniachik, J. & L., (1998), Hard-to-Solve Brainteasers, Sterling.
Smullyan, R., (1991), The Lady or The Tiger, Oxford University Press
Tamara, (2000), alt.math.recreational
Unknown, (circa November 1979), Herald Tribune, International Edition, Courtesy of Dr. Tito A. Ciriani
Velucchi, M., (1995), Non-Dominating Queens Problem, http://anduin.eldar.org/~problemi/papers.html

f