August | 2014 | Possibly Wrong

Every fall for the last several years, my wife and I have walked through a corn maze with our nephews. It’s a lot of fun; the kids get a paper copy of the maze to help them navigate, and there are a series of numbered checkpoints to find, each with a themed quiz question to answer. (I thought this was a pretty good idea, giving a clear sense of continuing progress, rather than just wandering through a maze of twisty little passages, all alike.)

But what if you don’t have a map of the maze? There are many algorithms for “solving” a maze, with various requirements on the structure of the maze and the assumed ability of the solver to “record” information about parts of the maze already explored. Some only work on a grid, while others, such as wall-following, are only guaranteed to work if the maze is simply connected– or in graph-theoretic terms, the graph representing the rooms (vertices) and passages (edges) of the maze must not contain any cycles.

Suppose instead that you find yourself in a maze of rooms and connecting passages like the one shown below, whose corresponding graph is neither a grid, nor acyclic.

A maze with 20 rooms and 30 connecting passages.

In fact, the maze need not even be planar (think catacombs with passages running over/under each other), and it may contain loops (passages that lead you back to the room you just left) or multiple passages between the same pair of rooms. The only requirement is that each passage has two ends– imagine a door at each end leading into a room… although as in the case of a loop, both doors may lead into the same room.

Now imagine exploring the maze by following these rules:

If you are in a room with an unmarked door (as you will be at the start), pick one, mark an X on it, and traverse the corresponding passage.
When first entering a room with all doors unmarked, mark a Y on the door of entry.
If you are in a room with all doors marked, exit via the door marked Y if there is one, otherwise stop.

This algorithm, due to Tarry (see reference below), will visit every room in the (connected) maze, traversing every passage exactly twice, once in each direction… ending in the same room where you started! Proving this is a nice problem involving induction. And the doors marked with a Y have the nice property of essentially marking a path from any room back to the starting point. (As an interesting side effect, suppose that we modify rule 3 slightly, so that before exiting a door marked Y, we remove or erase all of the marks on the doors in that room. The result is that, at the end, we have still visited every room in the maze, but erased any trace that we were there!)

Tarry’s algorithm has a lot in common with Trémaux’s algorithm, although I think this version is more explicitly “local,” in the sense that I can imagine actually executing Tarry’s algorithm in, say, a corn maze, with appropriate markings on the “doors” at intersections, as opposed to needing to mark the passages between intersections.

References:

1. Tarry G., Le problème des labyrinthes. Nouv. Ann. Math., 14 (1895), 187-190

This post captures my notes on the following problem from the last post:

Problem: Suppose that you are standing on the outer bank of a moat surrounding a castle, and you wish to secretly deliver a message, attached to a large rock, to your spy inside the castle. A wall h=11 meters high surrounds the castle, which is in turn surrounded by the moat which is d=19 meters wide. At what angle should you throw the rock in order to have the best chance of clearing the wall?

Solution: A projectile thrown from the origin with initial speed $v$ at an angle $\theta$ has a trajectory described by

$x(t) = v t \cos \theta$

$y(t) = v t \sin \theta - \frac{1}{2} g t^2$

Setting $x(t)=d$ and $y(t)=h$ and solving for $v$ and $t$ , we find the following expression for the required initial speed as a function of the throwing angle:

$v(\theta)^2 = \frac{g d^2}{2 \cos^2 \theta (d \tan \theta - h)}$

We can minimize this required initial speed by maximizing the denominator. Differentiating and setting equal to zero yields

$\tan 2\theta = -\frac{d}{h}$

Keeping in mind that the throwing angle is between 0 and 90 degrees, we can rewrite this expression as

$\theta = \frac{\phi + \pi/2}{2}$

where $\phi$ is the angle of the line of sight to the top of the wall. The geometric interpretation of this result is: to have the best chance of clearing the wall, throw at an angle halfway between the line of sight to the top of the wall and the vertical. In the original problem, this optimal throwing angle is about 60.03 degrees.

Recall, however, that this analysis assumes negligible effects of air resistance. This is a safe assumption for a relatively heavy rock at human-throwable speeds, but not for a baseball. If we apply this same analysis to Jackie Bradley, Jr.’s throw from home plate over the center field wall, 420 feet away and 17 feet high, we get an optimal throwing angle of about 46.2 degrees, with a minimum initial speed of only about 80.9 miles per hour, which is not terribly difficult to achieve.

To more accurately model the trajectory of a thrown (or batted) baseball, we must incorporate the effects of not only drag, which slows the ball down, but also the Magnus force, which “lifts” the ball causing it to “rise” and/or curve. The references below describe several interesting experiments tracking thrown and hit baseballs, including some useful approximation formulas for accurately modeling these trajectories, yielding my estimate from the last post that Bradley must have thrown the ball at over 105 miles per hour, with an optimal throwing angle of just a little over 30 degrees.

Since this is the sort of problem that I think is excellent for students to attack via computer simulation, following are the relevant formulas and constants collected in one place for them to use:

The acceleration of a thrown or batted baseball due to gravity, drag, and lift is given by

$a = g + a_D + a_L$

$a_D = -\frac{1}{2m}\rho v^2 A C_D \hat{v}$

$a_L = \frac{1}{2m}\rho v^2 A C_L (\hat{\omega} \times \hat{v})$

where:

Acceleration due to gravity $|g| = 9.80665$ meters/second^2
Mass $m = 5.125$ ounces (the midpoint of the regulation tolerance)
Air density $\rho = 1.225$ kilograms/meter^3 (sea level on a standard day)
$v$ and $\omega$ are the magnitudes of velocity and angular velocity, respectively, with $\hat{v}$ and $\hat{\omega}$ being corresponding unit vectors in the same direction
$A = \pi r^2$ is the cross-sectional area of the baseball, where the circumference $2\pi r = 9.125$ inches (the midpoint of the regulation tolerance)
Coefficient of drag $C_D = 0.35$ (see Reference 3)
Coefficient of lift $C_L = S/(0.4+2.32S)$ , where $S = r\omega/v$ is the “spin parameter” (see Reference 2)
Backspin on a typical fastball $\omega = 1500$ rpm (or 2000 rpm for a typical batted ball; see Reference 1)