In the movie Patton, the General sees two columns of his tanks crossing paths and getting stuck in gridlock. In frustration, Patton leaves his jeep and starts directing traffic. After a few minutes, he is called back to his higher responsibilities by Omar Bradley. Bradley mockingly praises Patton’s skills as a traffic cop. The fact is, though, that he was a bad traffic cop. There are much more efficient ways to have two columns cross one another, when you are not limited to roads. Let’s start by making the problem a little harder. Suppose there are four columns of vehicles, each of a different color. The columns are about to meet at an intersection as shown in figure 1.
Each column wants to exit the border of the rectangle on the side opposite from where it comes. So the Greens want to exit through the top side, the Oranges want to exit through the left side and so on. In doing so, the vehicles may move side-by-side rather than in single file. Because we’ve made the problem harder by allowing four columns, we’ll make the rules of movement simpler. Imagine that there is a grid. Each vehicle is in one grid cell location. Within a column, neighboring vehicles are in neighboring cells. A vehicle can move to its vertically or horizontally neighboring cell in one minute. If two vehicles end up in the same cell, they crash. You want to avoid crashes. As figure 1 shows, the four columns are converging onto the single central square, so if they all advance toward the center at once, there will be a crash. The question is how to arrange the movements so that all vehicles traverse their target sides in as short a time as possible. For concreteness, suppose that there are six vehicles of each color and the grid is 13-by-13 in dimension. Warm-Up: Consider a situation in which each column consists of a single vehicle as shown in figure 2:
Again, each vehicle wants to exit the opposite edge. So, B wants to cross the bottom edge; R wants to cross the right edge, and so on. How can we arrange it so all vehicles cross their target edges in four minutes? Solution to Warm-Up: All the routes are shown here in figure 3:
All vehicles exit their opposite edges after four minutes. It’s easy to see that there are no crashes.
Problems:
- Suppose you must keep the columns of cars in order and they all must go through the center. How long will that take?
- Now try to find a 14-minute solution for the six-vehicle-per-column, 13-by-13 grid problem in figure 1.
- Can you show that there is no faster solution?
- Suppose that eight of the vehicles – and you can choose which ones – could travel at twice the normal speed (so two cells in a minute) during the eighth minute of their journey. How could you then solve the six-vehicle-per-column, 13-by-13 grid problem in figure 1 in just thirteen minutes? Here is an open question: Can you achieve the 13-minute solution if only four vehicles can speed up on their eighth minute? Remember that crashing is not allowed.
The fact is, though, that he was a bad traffic cop. There are much more efficient ways to have two columns cross one another, when you are not limited to roads.
Let’s start by making the problem a little harder. Suppose there are four columns of vehicles, each of a different color. The columns are about to meet at an intersection as shown in figure 1.
Each column wants to exit the border of the rectangle on the side opposite from where it comes. So the Greens want to exit through the top side, the Oranges want to exit through the left side and so on. In doing so, the vehicles may move side-by-side rather than in single file.
Because we’ve made the problem harder by allowing four columns, we’ll make the rules of movement simpler. Imagine that there is a grid. Each vehicle is in one grid cell location. Within a column, neighboring vehicles are in neighboring cells. A vehicle can move to its vertically or horizontally neighboring cell in one minute. If two vehicles end up in the same cell, they crash. You want to avoid crashes.
As figure 1 shows, the four columns are converging onto the single central square, so if they all advance toward the center at once, there will be a crash.
The question is how to arrange the movements so that all vehicles traverse their target sides in as short a time as possible. For concreteness, suppose that there are six vehicles of each color and the grid is 13-by-13 in dimension.
Warm-Up: Consider a situation in which each column consists of a single vehicle as shown in figure 2:
Again, each vehicle wants to exit the opposite edge. So, B wants to cross the bottom edge; R wants to cross the right edge, and so on. How can we arrange it so all vehicles cross their target edges in four minutes?
Solution to Warm-Up: All the routes are shown here in figure 3:
All vehicles exit their opposite edges after four minutes. It’s easy to see that there are no crashes.
Problems:
Suppose you must keep the columns of cars in order and they all must go through the center. How long will that take?
Now try to find a 14-minute solution for the six-vehicle-per-column, 13-by-13 grid problem in figure 1.
Can you show that there is no faster solution?
Suppose that eight of the vehicles – and you can choose which ones – could travel at twice the normal speed (so two cells in a minute) during the eighth minute of their journey. How could you then solve the six-vehicle-per-column, 13-by-13 grid problem in figure 1 in just thirteen minutes?
Here is an open question: Can you achieve the 13-minute solution if only four vehicles can speed up on their eighth minute? Remember that crashing is not allowed.
