I’ve heard many fun problems in which blindfolded parachutists are dropped somewhere and they need to meet up once they’re on the ground. They can’t shout or purposefully leave traces behind. They will recognize each other as soon as they bump into each other. Their goal is to get to the same assembly point. They can design their strategy in advance.
Here is the first problem in a series that gets increasingly difficult:
Two parachutists are dropped at different locations on a straight line at the same time. Both have an excellent sense of direction and a good geographical memory, so both know where they are at any moment with respect to their starting point on the line. What’s their strategy?
The strategy is that the first person stands still and the second one goes forward and back repeatedly, increasing the distance of each leg until they collide.
In the next variation, both are required to execute the same program, that is, if one stands still, then both stand still. To compensate for this increased difficulty, they are allowed to leave their parachutes anywhere. And both of them will recognize the other’s parachute if they bump into it.
In the third variation, the set-up is similar to the previous problem, but they are not allowed to change the direction of their movement. To their advantage, they know which way East is.
I recently heard a 2-D version from my son Sergei in which the parachutists are ghosts. That means that when they bump into each other they go through each other without even recognizing the fact that they met:
Several blindfolded men are sleeping at different locations on a plane. Each wakes up, not necessarily at the same time. At the moment of waking up, each of them receives the locations of all the others in relation to himself at that moment. They are not allowed to interact, nor will they receive any further information as time passes. They need to get together in one place. How can they do that, if they are allowed to decide on their strategy in advance?
They do not know where North is. So they can’t go to the person at the most Northern point. Also they do not know how locations correspond to people, so they can’t all go to where, say, Peter is. Let us consider the case of two men. Suppose they decide to go to the middle of the segment of two locations they receive when they awake. But they get different locations because they wake up at different times. Suppose the first person wakes up and goes to the middle. The fact that he walks while the other is sleeping, means that he changes the middle. So when the second person wakes up, his calculated middle is different from the one calculated by the first person. Consequently, they will never manage to meet. Hence, the solution should be different.
Actually Sergei gave me a more difficult problem:
Not only do they need to meet, but they need to stay together for a predefined finite time period.
Here is as bonus problem.
If there are three parachutists, it is possible to end up in a meeting place and stay there indefinitely. For four people it is often possible too.