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); (coauthored with Jason Wang and Bruce Shapiro) Pattern Discovery in Biomolecular Data: Tools, Techniques, and Applications Oxford University Press, 1999); 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 [email protected].
The woman introduced herself as Astrid Svensen. On the most crowded street, she would stand out — a shock of bright red hair moving swiftly above playful blue eyes, and a face alive with freckles.
She spoke with a melodious Swedish lilt, even as she got right to the point.
"Dr. Ecco, I'm a math teacher and I would like your help in making childhood math more fun. Children have learned multiplication and memorized multiplication tables throughout the ages, mostly with little joy. My spiritual sister Pippi Longstocking called the subject 'plutification' and she never found any use for it. How can we make multiplication mroe fun in the 21st century? I've decided to create a game.
"Here is how it goes. You are given a multiplication table of all multiples of the numbers between 1 and 9:
1 2 3 4 5 6 7 8 9
2 4 6 8 10 12 14 16 18
3 6 9 12 15 18 21 24 27
4 8 12 16 20 24 28 32 36
5 10 15 20 25 30 35 40 45
6 12 18 24 30 36 42 48 54
7 14 21 28 35 42 49 56 63
8 16 24 32 40 48 56 64 72
9 18 27 36 45 54 63 72 81
"A turn entails cycling between the following two constraints:
- 1. odd or divisible by 3
- 2. even
"The turn starts by placing a chip on any product cell that satisfies the first constraint (1, 3, 5, 6, 7, 9, 12,...). The turn continues if the player can find a second cell that contains an even product (including 2) and is adjacent (either vertically, horizontally, or diagonally) to the first cell.
"In that case, the player places a chip on that cell. The turn continues yet further if the player can find a third cell that satisfies the first constraint (odd or divisible by 3), is adjacent to the second cell, and has no chip on it. The fourth cell must satisfy the second constraint, must be adjacent to the third cell, and must have no chip on it. And so on."
"Could we try an example?" Liane asked as she stuffed a letter to her summer camp friend in an envelope.
"Let's take a limited part of the multiplication table consisting of just the products of 5, 6, and 7," she suggested.
"This gives the subtable:
25 30 35
30 36 42
35 42 49
As it happens, every cell satisfies the first constraint, so we get the following sequence of moves that comprise a single turn: 49 (odd), 42 (even), 35 (odd), 30 (even), 25 (odd), 36 (even), 35 (odd), 30 (even), 42 (divisible by 3). That was too easy. Maybe it can always be done."
She thought awhile and then went on.
"On the other hand, consider the products of 6, 7, 8:
36 42 48
42 49 56
48 56 64
In this case, it is not possible because 64 is surrounded by evens, with the exception of 49, so a chip placed on 64 must follow a chip placed on 49 (because the play starts on a cell that is odd or divisible by 3). In that case, there is no cell to place a chip on after placing one on 64."
"Nicely done, girl," said Astrid. "Someone should write a novel about you some day. The Pippi of Math."
Remarkably, 13-year-old Liane smiled without irony.
Astrid continued.
"In any case, the challenge is to create a turn that hits as many cells of the full multiplication table as possible and includes all possible products. Can you do it?"
Reader: Liane was able to design a single turn covering 80 out of the 81 cells. Can you cover all of them or prove that it can't be done?
Astrid seemed pleased with the result and left. Ecco turned to Liane with a smile.
"Nicely done indeed Liane," he said. "I particularly liked your showing that certain cases are hard. Of course, that doesn't prove that your 80-cell solution is the best possible. I need to think about that. In any case, I have a related challenge for you.
"Consider the following possible constraints: odd, even, single digit, > 30, divisible by 3, divisible by 5, contains a 3, contains a 2. You are free to choose any subset of those constraints and to put them in any order. You can have your player start on any cell and proceed as you direct. Given all of this, can you choose a subset, then design a turn that will hit every cell of the multiplication table, obeying the adjacency rules above? If not, can your turn at least cover every possible value (perhaps missing some duplicates)? If not, how close can you get in one turn? What is the smallest number of turns you can use to hit the entire board?"
I left while Liane was still studying the question.
Reader: Would you like to give it a try?
Last Month's Solution
1. The general is in unit 3. The commander of unit 3 sends orders to the commanders of units 12 and 7. The commander of unit 12 sends orders to 9, 10, 4, and 11. The commander of unit 7 sends orders to 1 and 5. The commander of unit 5 sends orders to 2, 6, and 8.
2. When the mistress is involved, the general is associated with unit 8, the mistress with unit 6. The general sends orders to the commanders of 5 and 6. The commander of 5 sends orders to the commanders of 2, 12, 9, and 1. The commander of 6 (Silky) sends orders to 3, 4, 7, 10, and 11. She disobeys the general three times.
Reader Notes
Readers showed that in the "Beams" problem (DDJ, July 2001) Natasha gave way too few constraints. James Walby, for example, found over 85,000 solutions in 10 hours of computing time. I would like to salute those who gave me the best answers: Dennis Yelle, Rodney Meyer, Carl Smotricz, Steve Kietzman, Jerry Olsen, John A. Trono, Jean-François Halleux, Frank Radencich, Andrew Palfreyman, Michael Birken, Steve Altus, Tomas G. Rockicki, Alexander Fedorov, and Adekunle Bello.
Several readers took the further initiative of finding the minimum and maximum variance. The minimum variance is probably the most interesting since the Greeks loved symmetry.
Thomas Rockicki showed that under the original guidelines, where each beam is at least four units long and there is at least one beam over 11 units, the variance can be as low as 1.9447 for the arrangement where there are two beams of length 7.3, three of length 7.4, and one of length 11.1.
I challenged some readers to ignore the guidelines and to go for the minimum variance solution. Of those, Michael Birken produced the best analysis: In fact, he proved that the minimum variance is 51/10800=0.004722222222222...I quote his proof:
The length of the assembled temple is 47.9 cubits (i.e., the sum of lengths of the fragments exclusively from the front or from the back). Since there are 6 beams in the assembled temple, the mean length of any beam is 47.9/6=7.9833333333333... Since the fragment lengths are all rounded to the nearest tenth of a cubit, the minimum beam length that does not exceed this mean is 7.9 cubits. By the same token, the maximum beam length that does not exceed this mean is 8.0 cubits. Ideally, we would like a solution containing lengths of [7.9, 8.0, 8.0, 8.0, 8.0, 8.0] since 7.9+8.0+8.0+8.0+8.0+8.0= 47.9. Such a solution, if it existed, would have the minimum variance possible because any shuffling of a tenth of cubit would either result in a solution with the same variance or a solution that had beam lengths that deviated even more from the mean of 47.9/6. Unfortunately, such a solution does not exist. One of the fragments from the back of the assembled temple is 6.8 cubits long. If it originated from a beam of length 8.0, then we must be able to assemble some of the remaining back fragments into a length of 8.0-6.8=1.2 cubits. Since the two shortest fragments from the back are 1.0 and 1.3 cubits, there is no way to assemble a beam of length 8.0 using the 6.8 cubit fragment. Similarly, there is no way to assemble a beam of length 7.9 using the 6.8 cubit fragment since 7.9- 6.8=1.1 cubits. Since the minimum length we can shuffle is a tenth of a cubit and the borrowed tenth of a fragment cannot be donated to the 7.9 cubit beam because that would result in a solution of the same form, the next possible solution with minimum variance is either of the form [7.8, 8.0, 8.0, 8.0, 8.0, 8.1] or of the form [7.9, 7.9, 8.0, 8.0, 8.0, 8.1]. The former has a variance of approximately 0.008056 and the latter has a variance of approximately 0.004722. So, if the latter solution exists, then it must have the minimum variance possible. And, we know that a plethora of such solutions exists...[see Example 1].
DDJ
