There follows a collection of puzzles each of which may be formulated and solved using Integer Programming.

The puzzles are intended to give practice to students in the formulation of IP models, to stimulate interest and to demonstrate the rich variety of structures that may be effectively modelled using Integer Programming.

Xpress-Mosel models are available by clicking on Solution.

1. Twelve draught pieces are arranged in a square frame with four on each side. Try placing them so there are 5 on each side. (Kordemsky)

Maybe this problem is not described very well but I wanted to stick with the original text from Kordemsky. The problem may be stated in terms of guards on the wall of a square fort. If a guard stands on a side wall then he may only watch that particular wall whereas a guard at a corner may watch two walls. If twelve guards are positioned such that there are two on each side wall and one at each corner then there are four guards watching each wall. How can they be rearranged such that there are five watching each wall?    Solution

2. Supposing that eleven coins with round holes are worth 15 bits, while eleven square ones are worth 16 bits, and eleven of triangular shape are worth 17 bits, tell how many round, square or triangular pieces of cash would be required to purchase an item worth eleven bits. (Loyd)    Solution

3. A woman was carrying a basket of eggs to market when a passer-by bumped her. She dropped the basket and all the eggs broke. The passer-by, wishing to pay for her loss, asked, 'How many eggs were in your basket?'

'I don't remember exactly,' the woman replied, 'but I do recall that whether I divided the eggs by 2,3,4,5 or 6 there was always one egg left over. When I took the eggs out in groups of seven, I emptied the basket.'

What is the least number of eggs that broke? (Kordemsky)    Solution

4. Take 16 coins and put them in four rows of four each. Remove 6 leaving an even number of coins in each row and each column.(Kordemsky)    Solution

5. A side show at Coney Island is described as follows: "There were ten little dummies which you were to knock over with baseballs. The man said: 'Take as many throws as you like at a cent apiece and stand as close as you please. Add up the numbers on all the men that you knock down and when the sum amounts to exactly fifty, neither more nor less you get a genuine 25 cent Maggie Cline cigar with a gold band around it.'"

The numbers on the ten dummies were 15, 9, 30, 21, 19, 3, 12, 6, 25, 27. (Loyd)    Solution

6. Once upon a time there was an aged merchant of Baghdad who was much respected by all who knew him. He had three sons, and it was a rule of his life to treat them all exactly alike. Whenever one received a present, the other two were each given one of equal value. One day this worthy man fell sick and died, bequeathing all his possessions to his three sons in equal shares.

The only difficulty that arose was over the stock of honey. There were exactly twenty-one barrels. The old man had left instructions that not only should every son receive an equal quantity of honey, but should receive exactly the same number of barrels, and that no honey should be transferred from barrel to barrel on account of the waste involved. Now, as seven of these barrels were full of honey, seven were half full, and seven were empty, this was found to be quite a puzzle, especially as each brother objected to taking more than four barrels of the same description - full, half full, or empty.

Can you show how they succeeded in making a correct division of the property? (Dudeney)    Solution

7. A farmer leaves 45 casks of wine, of which 9 each are full, three-quarters full, half full, one quarter full and empty. His five nephews want to divide the wine and the casks without changing wine from cask to cask in such a way that each receives the same amount of wine and the same number of casks, and further so that each receives at least one of each kind of cask, and no two of them receive the same number of every kind of cask. (Kraitchik)    Solution

8. Place as few knights as possible on a chessboard in such a way that each square is controlled by at least one Knight, including the squares on which there is a Knight. How would the formulation differ if occupied squares were not to be under attack? (Schuh)    Solution

9. Three men who had a monkey bought a pile of mangoes. At night one of the men came to the pile of mangoes while the others slept and, finding that there was just one more mango than could be exactly divided by three, tossed the extra mango to the monkey and took away one third of the remainder. Then he went back to sleep.

Presently another of them awoke and went to the pile of mangoes. He also found just one too many to be divided by three so he tossed the extra one to the monkey, took one third of the remainder, and returned to sleep.

After a while the third rose also, and he too gave one mango to the monkey and took away the whole number of mangoes which represented precisely one third of the rest.

Next morning the men got up and went to the pile. Again they found just one too many, so they gave one to the monkey and divided the rest evenly. What is the least number of mangoes with which this can be done? (Kraitchik)    Solution

10. Is there a number which when divided by 3 gives a remainder of 1; when divided by 4, gives a remainder of 2; when divided by 5, gives a remainder of 3; and when divided by 6, gives a remainder of 4? (Kordemsky)    Solution

11. Five by five puzzle. Java enabled browser required.    Solution

12. Lights on puzzle. Java enabled browser required.    Solution

Dudeney, H.E., (1917), Amusements in Mathematics, Thomas Nelson and Sons.
Kordemsky, B.A., (1972), The Moscow Puzzles, Charles Scribner's Sons.
Kraitchik, M., (1942), Mathematical Recreations, W.W. Norton and Company.
Loyd, S., (1914), Cyclopedia of Puzzles, Samuel Loyd, Jr.
Schuh, F., (1943), Wonderlijke Problemen; Leerzam Tijdverdrijf Door Puzzle en Speel, W.J. Thieme & Cie, Zutphen.

f