Dennis is a professor of computer science at New York University and can be contacted at [email protected].
Benjamin Baskerhound had come for a visit. Our erstwhile kidnapper started with a muse: "In the surprising tale of espionage called El Jardin de Senderos que se Bifurcan (I like bifurcating so much more than forking), Borges develops a theory of time in which many universes exist as shadows of one another. There is the universe in which Napoleon won at Waterloo and French became the interlingua of earth. There is a universe in which certain galaxies were born and displaced the Milky Way. And so on.
"It's a troubling notion, neither provable nor falsifiable, neither moral nor evil, advocated neither by science nor religion, but condemned by neither as well. You are practical, Ecco, I know, so I wouldn't disturb you with such notions except that my employers (whose identities I cannot reveal), have described to me a kind of tree of bifurcating paths. Each path has an outcome that you might interpret as the value of the path. They are playing a kind of game against an enemy, they say. My employers make all the moves except two and the enemies can choose when to make each of their two moves."
Baskerhound started to sketch out a tree of possibilities.
"Let me get this straight," 14-year-old Liane interrupted. "You start at the root. You can go left or right each move. Before making a move, you first must ask your adversary whether he wants to choose (unless he's already chosen twice). If he doesn't, you can choose. Please stop your drawing and let's try a warm-up."
Liane then drew a tree in indented form:
A B C 6 177 D 380 302 E F 213 -129 G 618 17
"Here's how it goes," she explained. "You start at A, ask your adversary whether he wants to go to B or E. If he doesn't choose, then you get to choose. Suppose you choose E. Then you ask your adversary whether he wants F or G. Suppose he chooses F. Then at F, you ask your adversary whether he wants 213 or -129. Since your adversary wants you to get as little as possible, he chooses -129. This shows that E was a bad choice for you to make. In fact, you can guarantee a win of at least 6 if you start by choosing B. If the adversary chooses E, you will do even better, since your adversary can then choose only one more move. In fact, you can then guarantee at least 17."
"You grow smarter even as you grow more beautiful," Baskerhound said. "Which is the cause of which?"
Liane appeared to ignore both the comment and the question. "Tell us the real problem, Dr. Baskerhound." she demanded.
"Maybe it's the directness," he said. "Okay, here it is — a binary tree with 63 nodes. As you can see, there are some bad negative numbers in this six-level tree."
A B D H P 1055 775 Q 3011 3791 I R -4077 -3092 S 4894 -465 E J T 2149 1776 U -2408 3046 K V 18 -1043 W -3266 2523 C F L X 396 452 Y 2189 483 M Z 5219 -627 a 2055 3247 G N b 115 -3841 c 509 187 O d 4125 667 e 2338 -6
Liane was able to show that she could win a value of 396 for Baskerhound's employers.
Reader: Can you do as well or better?
"What would you like for your next birthday?" he asked Liane.
"Better digital editing software," Liane answered without a pause.
After Baskerhound left, Ecco turned to Liane. "Nice work," he said. "Do you think you would still get a positive score if your adversary had no freedom to change the numbers, but could rearrange the values of the subtree below the current node once. For example, if the current node were G, he could swap -3841 under b with 667 under d, but he would not be permitted to swap either number with -4077 under R. How well could you guarantee to do if he could perform this rearrangement only once in addition to choosing two moves?"
I never heard the answer to this question.
Reader: Would you like to give this a try?
Last Month's Solution
Table 1 shows Liane's 30-experiment approach for each value of carbon. The X represents a "don't care" — any value can be chosen.
Reader Notes
Chris Sterritt, Shawn B. Nematbakhsh, Todor Mitev, Tomas G. Rokicki, Olivier Reubens, Philip Hamer, Alexander Fedorov, Rodney Meyer, Tomasz Hajdasz, and Toby Everett all submitted excellent solutions to the "Protocol of Small Numbers" puzzle (DDJ, June 2002).
As Reubens observed, brute force takes too long. "The brute force approach would, for each n, try all kinds of combinations of operations to find the shortest possible formula. This will take large amounts of time to solve each n."
There are various dynamic programming solutions that build on previous solutions. Liane observed that, for example, optimal solutions for 13 and 19 can be used for 33 by putting a + sign between the two solutions. Reubens's dynamic programming approach started from the raw materials and saw where that led; "A better approach would start with a list of known values (initially only k [the generator] would be known). And then combine each known value with each other known value using each of the operators. The table would be initialized at k. And in the first generation, you'd try to add k+k, k-k, k/k, and k*k to the table."
As to the question of the maximum value achieved in an exponential function of the number of instances of the generator in the expression, Tomas Rokicki observes, "The function is clearly exponential. A simple decomposition by digit position leads to a representation, for any base, that is logarithmic in size; that gives a lower bound. For the upper bound, the pigeonhole principle combined with the count of strings of a certain length with a finite alphabet shows that the average must be at least exponential."
Rokicki and Hajdasz observed that improvements to Liane's solution (still using only the operations allowed) could be achieved by using nonintegral fractions as in: (5+5)*(5-(5+5/5)/5), which is 10*3.8. You need intermediate fractional values (in this case, 6/5) in order to represent this value.
Table 2, produced by Rokicki, relates cost to the maximum number achieved (average cost means cost up to and including that number).
Reubens observed that the combination 22, 31, and 36 gave a total of n=70491, with an average cost of 7. Hajdasz showed that using 9, 8, and 5 as generators could obtain all numbers up to 80,304 with a cost of 8.
DDJ
