Angel Problem - History

History

The problem was first published in the 1982 book Winning Ways by Berlekamp, Conway, and Guy, under the name "the angel and the square-eater." In two dimensions, some early partial results included:

  • If the angel has power 1, the devil has a winning strategy (Conway, 1982). (According to Conway, this result is actually due to Berlekamp).
  • If the angel never decreases its y coordinate, then the devil has a winning strategy (Conway, 1982).
  • If the angel always increases its distance from the origin, then the devil has a winning strategy (Conway, 1996).

In three dimensions, it was shown that:

  • If the angel always increases its y coordinate, and the devil can only play in one plane, then the angel has a winning strategy.
  • If the angel always increases its y coordinate, and the devil can only play in two planes, then the angel has a winning strategy.
  • The angel has a winning strategy if it has power 13 or more.
  • If we have an infinite number of devils each playing at distances then the angel can still win if it is of high enough power. (By "playing at distance " we mean the devil is not allowed to play within this distance of the origin).

Finally, in 2006, not long after the publication of Peter Winkler's book Mathematical Puzzles, which helped publicize the angel problem, there emerged four independent and almost simultaneous proofs that the angel has a winning strategy in two dimensions. Brian Bowditch's proof works for the 4-angel, while Oddvar Kloster's proof and András Máthé's proof work for the 2-angel. Péter Gács's proof works only for a much larger constant. The proofs by Bowditch and Máthé have been published in Combinatorics, Probability and Computing (edited by Béla Bollobás and Imre Leader). The proof by Kloster has been published in Theoretical Computer Science.

Read more about this topic:  Angel Problem

Famous quotes containing the word history:

    “The history of work has been, in part, the history of the worker’s body. Production depended on what the body could accomplish with strength and skill. Techniques that improve output have been driven by a general desire to decrease the pain of labor as well as by employers’ intentions to escape dependency upon that knowledge which only the sentient laboring body could provide.”
    —Shoshana Zuboff (b. 1951)

    “The history of all countries shows that the working class exclusively by its own effort is able to develop only trade-union consciousness.”
    —Vladimir Ilyich Lenin (1870–1924)

    “To care for the quarrels of the past, to identify oneself passionately with a cause that became, politically speaking, a losing cause with the birth of the modern world, is to experience a kind of straining against reality, a rebellious nonconformity that, again, is rare in America, where children are instructed in the virtues of the system they live under, as though history had achieved a happy ending in American civics.”
    —Mary McCarthy (1912–1989)