Difficult Expii Contest Question I came across this problem while writing a contest and I cant find the answer: The third dimension is another solution to traffic jams, if we first invent flying cars. Suppose that a metropolis is evenly distributed across a square of land which is 20 km on each side. Every morning, 1 million commuters each fly their car from one uniformly random point to another, by departing at a uniformly random time between 7 a.m. and 9 a.m., flying straight upward to a random altitude, then cruising in a straight line to the point above their destination, and flying straight downward, all at 100 km/hr. The flying cars are all spheres of diameter 5 meters.

To keep order, the cruising altitudes are always multiples of 10 meters. We say that a car encounters another if they are at the same altitude, and the centers of the cars pass the same point within 1 second of each other. How many different possible choices are needed for the random altitudes so that the expected number of other flying cars encountered by a given flying car is only 1? Any answer within 10% of the correct answer is accepted.
Some thoughts on how to tackle this. I'll read the problem definition quite literally, even if much of it doesn't make sense physically.


The size of the cars is irrelevant. The definition of “encounter” is for the centers of two cars to pass the same point within one second, which I'd read as “pass through the same point”. So you have some leeway in time but none in space.
This means that given two line segment trajectories you can decide whether two given cars will encounter one another by computing the point of intersection between the lines, checking whether it lies on the segments, then computing the time each car passes that point and checking whether the times are at most one second apart.
We can ignore encounters on the vertical legs. As there is no spatial leeway (as discussed above), any two cars will pass through a common point on their vertical journey with probability zero.
The difference between cruising altitudes is irrelevant. As we have no spatial leeway, cars on different altitudes can never encounter one another. Furthermore, although different altitudes mean different time till the cars reach these altitudes, that time is the same for all cars cruising at that altitude, so you can simply consider this a constant offset from the 2 hour departure time window, which doesn't matter since the arrival at cruising altitude still falls uniformly in a 2 hour window.
You essentially need to figure out the probability that two cars on the same altitude will encounter one another. Once you have that probability $p$, the expected number of encountered cars if there were $n$ cars at the same altitude would be $(n-1)p$, so you could solve $(n-1)p=1$ for $n$ and then divide the total poulation by this to obtain the number of required altitude levels.
Getting the pairwise encounter probability seems tricky to do symbolically, so you might want to try some Monte Carlo approach to this: Simulate pairs of cars at the same altitude until the probability value stabilizes, then perform your computation using that value.


If the question was meant differently, then it depends on what exactly the intended meaning was. Perhaps two cars enounter one another of their centers pass within 5 meters from a given point within 1 second from one another. How would that affect my approach?


Instead of intersecing line segments you'd essentially intersect long rectangles. Every point within such a rectangle will have a different time window when it is within 5m of one of the cars, so working out the exact geometry here will become a bit harder. You may want to simplify this somehow, or perform some simulations to e.g. turn this into an approximate time window within which the cars must pass through the same point.
Vertical legs become a problem as well. As do vertical legs encountering horizontal cruises. Hard work ahead! Perhaps you want to compute each of these probabilities separately (vertical vs. vertical, vertical vs. horizontal, horizontal vs. horizontal) for a given number of altitudes, and then tweak that number until you are satisfied.
If the cruise altitudes are exactly 10m apart, then points between them will be exactly 5m from the centers of cars cruising at adjacent altitudes. It is very unclear whether you'd consider this an encounter. If you do, cars on adjacent altitudes would suddenly start encountering one another.


On the whole, this makes the problem much harder, and less clearly specified as well.
Some thoughts on how to tackle this. I'll read the problem definition quite literally, even if much of it doesn't make sense physically.


The size of the cars is irrelevant. The definition of “encounter” is for the centers of two cars to pass the same point within one second, which I'd read as “pass through the same point”. So you have some leeway in time but none in space.
This means that given two line segment trajectories you can decide whether two given cars will encounter one another by computing the point of intersection between the lines, checking whether it lies on the segments, then computing the time each car passes that point and checking whether the times are at most one second apart.
We can ignore encounters on the vertical legs. As there is no spatial leeway (as discussed above), any two cars will pass through a common point on their vertical journey with probability zero.
The difference between cruising altitudes is irrelevant. As we have no spatial leeway, cars on different altitudes can never encounter one another. Furthermore, although different altitudes mean different time till the cars reach these altitudes, that time is the same for all cars cruising at that altitude, so you can simply consider this a constant offset from the 2 hour departure time window, which doesn't matter since the arrival at cruising altitude still falls uniformly in a 2 hour window.
You essentially need to figure out the probability that two cars on the same altitude will encounter one another. Once you have that probability $p$, the expected number of encountered cars if there were $n$ cars at the same altitude would be $(n-1)p$, so you could solve $(n-1)p=1$ for $n$ and then divide the total poulation by this to obtain the number of required altitude levels.
Getting the pairwise encounter probability seems tricky to do symbolically, so you might want to try some Monte Carlo approach to this: Simulate pairs of cars at the same altitude until the probability value stabilizes, then perform your computation using that value.


If the question was meant differently, then it depends on what exactly the intended meaning was. Perhaps two cars enounter one another of their centers pass within 5 meters from a given point within 1 second from one another. How would that affect my approach?


Instead of intersecing line segments you'd essentially intersect long rectangles. Every point within such a rectangle will have a different time window when it is within 5m of one of the cars, so working out the exact geometry here will become a bit harder. You may want to simplify this somehow, or perform some simulations to e.g. turn this into an approximate time window within which the cars must pass through the same point.
Vertical legs become a problem as well. As do vertical legs encountering horizontal cruises. Hard work ahead! Perhaps you want to compute each of these probabilities separately (vertical vs. vertical, vertical vs. horizontal, horizontal vs. horizontal) for a given number of altitudes, and then tweak that number until you are satisfied.
If the cruise altitudes are exactly 10m apart, then points between them will be exactly 5m from the centers of cars cruising at adjacent altitudes. It is very unclear whether you'd consider this an encounter. If you do, cars on adjacent altitudes would suddenly start encountering one another.


On the whole, this makes the problem much harder, and less clearly specified as well.