Communications of the ACM
A Magical Answer to an 80-Year-Old Puzzle
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