August 22, 2020

A Familiar Place

89. Back to Home Base

A Familiar Place

"Awesome," says Bill as you show him and Anita the Fibonacci sequence you found in Pascal's triangle (see "Back to Home Base"). Just as you come to the line that adds up to 8, the voice from your radio returns.

"EIGHT!" it blares. A regular octagon appears on the screen, and the loud motor roars as you feel the spacecraft taking off.


Soon, the screen is filled with three-dimensional shapes: cubes, tetrahedrons, octahedrons, dodecahedronsicosahedrons, and a buckyball. You click on the buckyball, and it grows into a bright, multicolored soccer ball. Admiring its glistening surface of pentagons and hexagons, you click on one of the hexagons. Suddenly the screen fills up with a checkerboard pattern.


The loud motor sounds return, and you feel your stomach rising. Then suddenly it's quiet.

You stand up, walk over to the window, and recognize Checkerboard City (see "Planet of the Shapes").

"It's the Planet of the Shapes! We're back!" you exclaim.

You exit the spacecraft with Anita and Bill, and start taking steps in random directions (see "Walking on a Grid").

"I'm getting tired, and it seems like we could go forever, walking from square to square," says Anita.

Can you get to the edge of Checkerboard City by moving randomly?

TRY IT!
Take a random walk on a checkerboard to see if you can get to the edge.

You will need:
  • checkerboard
  • die (You can use a regular six-sided die, but a tetrahedral die is even better, because you need only four sides.)
  • checker pieces (or coins or other markers)
What to do:
  1. Find the four center squares on your checkerboard and place a checker piece on one of these squares.
  2. Roll the die and take a "step" by placing a second checker piece on the appropriate square: if you roll a 1, place it on the square above; if you roll a 2, place it on the square to the right; 3, on the square below; 4, on the square to the left. If you roll a 5 or a 6, ignore it and roll again.
  3. Keep on rolling and placing a checker piece on the appropriate square.
  4. How many rolls does it take you to reach the edge of the checkerboard?
  5. What kind of pattern do your checker pieces form?
  6. Now take a "self-avoiding" random walk (see "Walking on a Grid"). Clear the checkerboard, and place a checker piece on one of the four center squares. Roll the die and place a second checker piece on the appropriate square.
  7. Roll again and place a checker piece on the appropriate square bordering the square you just covered. You may not retrace your "steps," so if the square is already occupied, ignore that roll, and roll again.
  8. See if you can reach the edge of the checkerboard before you run out of pieces or get trapped. You will be trapped and unable to move if you end up on a square surrounded by four squares that are already covered.
  9. Which route gets you to the edge of the checkerboard first, the regular random walk (steps 2, 3), or the self-avoiding random walk (steps 6, 7)?
Answers:
In the regular checkerboard random walk, you will probably reach the edge of the checkerboard in fewer than fifteen rolls. Your checker pieces will form a ragged pattern that resembles a three-dimensional map of a mountain; the highest piles of checker pieces will be toward the center.

In the self-avoiding random walk, you will probably get to the edge in even fewer steps. You will never reach the edge, however, if you happen to get trapped on a square that is surrounded by checker pieces, which prevent you from moving in any direction.

No comments: