‘The journey of a thousand miles begins with a single step.’ —Lao Tzu


Imagine that you are imprisoned in a tunnel that opens out onto a precipice two paces to your left, and a pit of vipers two paces to your right. To torment you, your evil captor forces you to take a series of steps to the left and right. You need to devise a series that will allow you to avoid the hazards — if you take a step to the right, for example, you’ll want your second step to be to the left, to avoid falling off the cliff. You might try alternating right and left steps, but here’s the catch: You have to list your planned steps ahead of time, and your captor might have you take every second step on your list (starting at the second step), or every third step (starting at the third), or some other skip-counting sequence. Is there a list of steps that will keep you alive, no matter what sequence your captor chooses?

In this brainteaser, devised by the mathematics popularizer James Grime, you can plan a list of 11 steps that protects you from death. But if you try to add a 12th step, you are doomed: Your captor will inevitably be able to find some skip-counting sequence that will plunge you over the cliff or into the viper pit.

Around 1932, Erdős asked, in essence, what if the precipice and pit of vipers are three paces away instead of two? What if they are N paces away? Can you escape death for an infinite number of steps? The answer, Erdős conjectured, was no — no matter how far away the precipice and viper pit are, you can’t elude them forever.

But for more than 80 years, mathematicians made no progress on proving Erdős’ discrepancy conjecture (so named because the distance from the center of the tunnel is known as the discrepancy).

{ Quanta | Continue reading }