De duivel en de engel
Op een oneindig bij oneindig schaakbord bewegen zich
een duivel en een engel. Bij elke zet kan de engel
naar een nieuw veld gaan, dat afstand ten hoogste 1000
heeft van het oude veld. Bij elke zet verwijdert de duivel
een veld (naar keuze) uit het schaakbord, zodat de engel daar nooit meer
komen kan. De engel is gevangen als ze niet meer kan bewegen.
Honderd dollar vraag
$100 wordt uitgeloofd voor degene die bewijzen kan dat
de engel niet gevangen kan worden. Het is toegestaan
om dit te bewijzen met 1000000 in plaats van 1000 -
of een willekeurig ander, van te voren afgesproken getal.
Duizend dollar vraag
$1000 wordt uitgeloofd voor degene die bewijzen kan dat
de engel altijd gevangen kan worden, hoe ver zij ook
kan springen.
Commentaar
Dit is een open probleem.
Bekend is dat als de engel zo dom is om te beloven dat
ze altijd bij elke sprong de x-coordinaat zal vergroten,
dan kan ze gevangen worden, hoe ver zij ook kan springen.
Ook bekend is dat een engel die zich als een schaakkoning beweegt
(sprongetjes ter lengte 1) gevangen kan worden.
Ziehier een demonstratie.
Het is onbekend of een engel die zich als een schaakpaard beweegt
gevangen kan worden.
Referentie
J.H. Conway, The angel problem, pp. 3-12 in:
R.J. Nowakowski (ed.), Games of No Chance,
Cambrige Univ. Press, 1998.
Opgelost
In 2006 vonden verschillende groepen onafhankelijk van elkaar oplossingen.
De engel kan ontsnappen als zij sprongen ter lengte 2 kan maken.
Zie ook Wikipedia.