Scarecrow’s Nutty Return

Setup

His random journey now ended, Scarecrow is headed back to Dorothy through the Deadly Field of Poppies. In order to understand what happens next we must recollect an earlier interlude, when the companions were making their way through the Dark Forest:

… the Scarecrow found a tree full of nuts and filled Dorothy’s basket with them, so that she would not be hungry for a long time. She thought this was very kind and thoughtful of the Scarecrow, but she laughed heartily at the awkward way in which the poor creature picked up the nuts. His padded hands were so clumsy and the nuts were so small that he dropped almost as many as he put in the basket. But the Scarecrow did not mind how long it took him to fill the basket, for it enabled him to keep away from the fire, as he feared a spark might get into his straw and burn him up. So he kept a good distance away from the flames, and only came near to cover Dorothy with dry leaves when she lay down to sleep. These kept her very snug and warm, and she slept soundly until morning.

– From Chapter VII, “The Journey to the Great Oz”

(Note: The Scarecrow gathered so many nuts that they could not all fit into Dorothy’s basket. Hoping to keep Dorothy well-fed in case her supply should run low, the Scarecrow stored a great many nuts in his capacious pant-pockets.)

The Scarecrow has nearly reached Dorothy. In fact he needs to take only 14 steps—seven in each of the directions that brings him closer to her—to reach the spot where she is sleeping.

At that moment he hears with his sharp ears—ears that were, as you may recall, painted on by the Quadling farmer who made him—the faint sound of a nut hitting the ground. Scarecrow stops in his tracks and looks down: sure enough, there is a nut at his feet.

“Come to think of it,” the Scarecrow mutters, “from the very start of my random journey, I have been hearing that faint thudding sound.” Checking his trousers, the Scarecrow notices a small tear in the left front pocket. He deduces that at every step on his random journey—and during his current return to Dorothy—a nut has fallen out of his pocket.

With his sharp eyes—painted on, you may recall, by the Quadling farmer who made him—Scarecrow scans the territory separating himself from Dorothy. Sure enough, there are small piles of nuts, and the number of nuts in each pile equals the number of visits the Scarecrow had made to that spot during his random walk.. There are only two exceptions to this pattern:

  • At Scarecrow’s current location, the nut that just fell is in addition to any nuts that might have fallen there during the random journey.
  • At Dorothy, the number of nuts is one less than the number of times he was there, because no nut dropped until he took the first step on his random walk.

Recall that Scarecrow’s compulsion about poppy-fields compells him to step one yard at a time, and only in cardinal directions. His desire to get back to Dorothy requires that each step will be in one of the two directions that bring him closer to Dorothy. Hence it impossible for Scarecrow to recover all of the dropped nuts; instead he must select a path back to Dorothy—fourteen steps, seven in each direction—that will maximize the number of nuts he recovers. (Include the just-dropped nut in that count.)

Questions

  1. What is the maximum number of nuts that he could recover? (Include all nuts at the origin and all nuts, including the just-dropped nut, at his current location.)
  2. How many distinct paths back will result in the recovery of that maximum number of nuts?
  3. Recall that Toto is asleep two yards North and two yards East of Dorothy. He could be in the territory where the Scarecrow needs to walk. Scarecrow is so eager to maximize recovered nuts that he is willing to step on Toto. Nonetheless, he wonders: How many of the optimal paths would not cross over Toto?

The Data

The data for this problem is the same as for the problem about the random journey.