Fitting

Dennis, a professor of computer science at New York University, is the author of The Puzzling Adventures of Dr. Ecco (Dover, 1998), Codes, Puzzles, and Conspiracy (W.H. Freeman & Co., 1992), Database Tuning: A Principled Approach (Prentice Hall, 1992), and (coauthored with Cathy Lazere) Out of Their Minds: The Lives and Discoveries of 15 Great Computer Scientists (Springer Verlag, 1998). He can be contacted at DrEcco@ ddj.com.

Distinguished in his Armani tailored suit, Rino Banti showed us his badge: Servizio Speciale, the Italian Secret Service.

"There is a little known secret about art in Italy," he explained. "All people have seen Michelangelo, Da Vinci, Tintoretto, but what you see is a tiny portion of what was produced. Looters from all over Europe have taken the patrimony of Italy for their own enjoyment. Not to mention local thieves. Sometimes the looting is destructive, as in the case of the splendid Arabic-Venetian marble rectangle that is the subject of my visit.

"The work of art we're seeking belonged to one of the great Doges of Venice, Enrico Dandolo, the blind conqueror of Constantinople in 1204. (His role in the conquest may have been exaggerated. The fighters of the fourth crusade conquered the city and turned it over to Venice in payment for the warships Venice had provided.) The artwork is a geometric design in a rare turquoise marble. Dandolo couldn't see the turquoise, but it is said that he relished the touch of the lines carved in the marble.

"This original square measures 16×16, and consists of smaller rectangles and triangles. These smaller pieces have been squirreled away in private collections all over the continent and some even in the United States. Most of the people who have them deny any knowledge of wrong-doing and we cannot, francamente, accuse them of lying. The theft occurred long before the pieces in question fell into the hands of their current owners.

"What's worse is that the owners protest molto about the prospect of giving up their works of art. Sometimes they have paid dearly for them. We think, however, that we can convince the courts that the correct pieces come from the stolen rectangle provided we can prove that those pieces reconstruct the rectangle and no combination of the other turquoise pieces that we have located can possibly reconstruct the rectangle.

"The trouble is that we don't know which are the correct pieces. At least some of the pieces we have located must belong to lesser works of art, because our mathematicians tell us they cannot form a rectangle of the correct size. Our problem is to figure out which pieces can possibly make up the rectangle and how to form the rectangle from them. Then we must show that no other combination of pieces can fit the rectangle."

"Geometry!" Liane exclaimed. "I've been longing for a geometrical puzzle."

"So have I," Ecco said, smiling. "Signore Banti, please tell us the sizes of the pieces available as well as the size of the desired rectangle."

"Grazie molto, Dr. Ecco," Banti replied. "They told me you help only when you find the problem engaging. Please see this figure (see Figure 1) for the sizes..."

Reader: Find a subset of these shapes that form the rectangle. Show how to form the rectangle (please use JPEG and send me the web page if you submit a solution). Also, show that no other combination of shapes can possibly form the rectangle.

Last Month's Solution

The first problem is to find a mapping from dried fruit to page numbers. Here is what Ecco found:

coconut 1

prune 2

date 3

grapefruit 4

raisin 5

fig 6

currant 7

pineapple 8

apricot 9

There were two reversed edges as Simon had feared. They are:

• apricot pineapple, which should have been pineapple apricot;

• raisin coconut, which should have been coconut raisin.

When we lay out the text in order of page number and concatenate, we will get:

"6nlm4bgurmx5mram8nb8vmhwwdddm

3r8a7m9rgm9xu6gllm7rmar6mvxun

6mx6m6rrmlbgvp"

The corresponding cleartext is: "the cargo is on uhaul vxx222 bound for figtree do not light it too early."

With the information I've given you, it is impossible to figure out that 222 is the number. I will report in a future column how close some readers were able to get to this decoding.

Solutions to the Sultan's Problem

Several readers matched or improved upon Liane's solution to the Trains for the Sultan problem (DDJ, March 1999), including Dr. Burghart Hoffichter, James Waldby, Chris Rosenbury, and D.F. Curran.

Several other solutions improved the scheduling by causing trains to wait at certain stations, thus leaving the tracks clearer.

James Waldby found a solution to the first problem (50 people trains) that reduces the time from 105 minutes (Liane's solution) to 90+3e where e is the time to wait. For convenience, let's make e represent one minute. Typical trains do two minute stops.

Start Route

Time Taken

0 AEF, wait one minute, FBCBG

0 BAEFBAE

0 CBD DBCeeCBD

0 DBCBD, wait two minutes, DBC

0 EFBAEFB

1 FBAEFBA

2 GBAE, wait one minute, EFBD

Chris Rosenbury proposed the following when five trains can carry 150 passengers. The goal is to reduce the size of station B to two platforms by staggering train departures.

Start Route

Time Taken

0 EFBD (150 people)

0 AE, wait 15 minutes, then EF (150 people)

0 FBAE (150 people)

0 GBA (50 people)

5 CBG (50 people)

10 CBD (150 people)

10 DBC (150 people)

15 FBC (50 people)

D.F. Curran ([email protected]) proposed a different layout with six tracks instead of seven and two extra platforms in station C. He further proposed switches in the middle of a track to allow trains traveling in the opposite direction to pass one another in the middle of a track. (In Zürich, two-way traffic on one track is accomplished by building a short stretch of two tracks in the middle. Trams moving in the opposite direction are timed so they pass each other at exactly this section of track.) He was then able to show that 60 minutes was enough.

DDJ