[math-fun] Review 0976.91008
I agree with the comments of Professor Richard Guy, and would like to add three further remarks. 1. Professor Guy wrote, "...But as soon as there are two or more N-positions we cannot decide the outcome. We need the simple but powerful theorem...". We could still sidestep that powerful theorem and do everything by means of the P,N,D-positions only: but on the *game-graph* of the game rather than on the input graph. The game-graph has exponential size in the input graph size, so this computation isn't practical. In other words, the Sprague-Grundy theory and its infinite extension enable us to recover a polynomial strategy. 2. In Fig.~2 of the paper a sample problem of a graph with 5 tokens is displayed, which demonstrates that the generalized S-G function can solve the sample game. The simple P,N,D-labeling cannot do this on the graph depicted in Fig.~2, as Professor Guy wrote. Did the reviewer not notice this example, occupying 3 pages? 3. Zentralblatt should publish a corrected review. Mit besten Gr"usse, Aviezri Fraenkel.
participants (1)
-
Aviezri Fraenkel