Manhattan without incident - Liceo Scientifico R. Bruni (Padova)

Some vehicles move on a grid, made up of intersecting horizontal and vertical lanes, and must avoid colliding. A collision between two vehicles could occur at a node (i.e. a point of intersection between a horizontal lane and a vertical lane), if the two vehicles pass through this node at the same instant of time. Or, a collision could also happen at a point in a lane between two nodes, if two vehicles are traveling in the same lane and pass that point at the same time.
In particular, all vehicles start from the lowest horizontal lane and must reach the highest horizontal lane. Furthermore, each vehicle is assigned a vertical departure lane and a vertical arrival lane. The problem is understanding how the vehicles should be routed, so that each vehicle reaches its destination without colliding with the others.
You can reason in the following hypotheses:
• the distance between two consecutive lanes, both vertical and horizontal, is always the same, and all vehicles travel at the same speed;
• the vertical departure lanes of the vehicles are all different from each other, as are the vertical arrival lanes;
• all vehicles leave at the same time;
• each vehicle moves along a path of minimum length that connects its starting position and its arrival position, i.e. it never goes back (we call a path of this type "Manhattan type");
• each vehicle stops only when it has arrived at its destination.

(a) Imagine you have a "large" grid, where the number of horizontal lanes equals the number of vertical lanes and equals the number of vehicles. Find rules to route all vehicles while avoiding collisions; the rules must apply regardless of the departure and arrival lanes of the vehicles.

(b) Try to reduce the number of horizontal lanes used. For example, suppose you have vertical lanes, while you need to build horizontal ones; What is the minimum number of horizontal lanes necessary to route all vehicles without collisions?
Can you write rules to route vehicles efficiently in this case too?

(c) If you want, you can try to understand how the problem changes by removing one of the hypotheses from the list above.