Sign In

Communications of the ACM

ACM News

A Magical Answer to an 80-Year-Old Puzzle

View as: Print Mobile App Share:
A precipice lies two paces to your left and a pit of vipers two paces to your right. Can you devise a series of steps that will avoid the hazards, even if you are forced to take every second, third or Nth step in your series?

University of California, Los Angeles mathematician Terence Tao has presented a solution to an 80-year-old number theory problem posed by legendary mathematician Paul Erd?s.

Credit: Olena Shmahalo/Quanta Magazine

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?

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.


From Quanta Magazine
View Full Article



No entries found

Sign In for Full Access
» Forgot Password? » Create an ACM Web Account