A Magical Answer to an 80-Year-Old Puzzle

Erica Klarreich in Quanta:

The mathematician Terence Tao, of the University of California, Los Angeles, has presented a solution to an 80-year-old number theory problem posed by the legendary Hungarian mathematician Paul Erdős. Erdős was famous for the thousands of puzzles he came up with, many of which have led to surprisingly deep mathematical discoveries. This particular problem, which came to be known as the Erdős discrepancy problem, was one of his favorites, said Ben Green, a mathematician at the University of Oxford. “He mentioned it many times over the years, particularly towards the end of his life.”

A simplified version of the problem goes like this: 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?

More here.