Problemă despre un înger și un diavol

Problema îngerului și diavolului este o problemă de teoria jocurilor propusă de Conway în 1982. [1] .

Formulare

Regulile jocului

Joacă doi jucători , numiți un înger și un diavol. Jocul are loc pe o tablă de șah nesfârșită . Îngerul are „puterea” k (este un număr natural 1 sau mai mult), care este stabilit înainte de începerea jocului. La începutul jocului, îngerul stă pe una dintre celule. Cu fiecare mutare, ingerul se muta intr-o alta celula libera, la care se poate ajunge in maxim k mutari ale regelui. Diavolul, la rândul său, poate bloca o celulă care nu are un înger. Îngerul poate sări peste spațiile blocate, dar nu poate ateriza pe ele. Diavolul câștigă dacă îngerul nu se poate mișca. Îngerul câștigă dacă trăiește la infinit.

Întrebare

Poate un înger să câștige dacă are suficientă putere?

Mai exact, este necesar să se găsească o strategie câștigătoare pentru unul dintre jucători. Dacă diavolul poate câștiga, trebuie să facă acest lucru într-un număr finit de mișcări. Dacă diavolul nu poate câștiga, atunci există întotdeauna o acțiune pe care îngerul o poate întreprinde pentru a evita pierderea, iar strategia câștigătoare este să aleagă o astfel de mișcare. Adică, setul de mișcări care duc la câștigarea îngerului este închis în topologia naturală a setului tuturor mișcărilor și se știe că astfel de jocuri sunt deterministe .

Istorie

Problema a fost publicată pentru prima dată în 1982 în Winning Ways de Berlekamp , Conway și Guy [2] sub titlul „Îngerul și devoratorul pătrat”.

Conway a anunțat o recompensă pentru soluția generală a problemei (100 de dolari pentru o strategie câștigătoare pentru un înger suficient de puternic și 1.000 de dolari pentru a demonstra că diavolul poate câștiga indiferent de puterea îngerului).

Pentru cazul bidimensional, iată câteva rezultate timpurii:

Dacă puterea îngerului este 1, atunci diavolul are o strategie câștigătoare. (Potrivit lui Conway, acest rezultat se datorează lui Alvin Berlekamp ).
Dacă îngerul nu reduce niciodată coordonatele, atunci diavolul are o strategie câștigătoare (Conway, 1982).
Dacă îngerul crește întotdeauna distanța față de celula centrală, atunci diavolul are o strategie câștigătoare (Conway, 1996).

Pentru o placă tridimensională, s-a dovedit că:

Dacă îngerul crește întotdeauna distanța față de pătratul central și diavolul poate juca pe același plan, atunci îngerul are o strategie câștigătoare.
Dacă îngerul crește întotdeauna coordonatele și diavolul poate juca doar pe două planuri, atunci îngerul are o strategie câștigătoare.
Un înger are o strategie câștigătoare dacă puterea sa este de 13 sau mai mare.
Dacă există un număr infinit de diavoli și toată lumea joacă la distanțe , atunci îngerul poate câștiga în continuare dacă are o putere suficient de mare. (Prin „jucare la distanță ” înțelegem restricția conform căreia diavolul nu are voie să joace la o distanță mai mică de careul de start.) $d_{1}<d_{2}<d_{3}<\cdots$ $d$

În cele din urmă, în 2006 (la scurt timp după publicarea Mathematical Puzzles a lui Peter Winkler , care a făcut această problemă populară), au fost prezentate patru dovezi independente și aproape identice că un înger are o strategie câștigătoare pe o tablă plată. Dovada lui Bowditch [3] funcționează cu puterea funcționează cu puterea îngerului 2.[4]André Matelui dovadaKloster șiOddvar probaîn timp ce,îngerului Dovezile lui Bowditch și Mate au fost publicate în Combinatorics, Probability and Computing (editorii Bolobas și Leader ). Dovada lui Kloster este publicată în Theoretical Computer Science .

Schițe de dovezi

Dovada „Gard”

O dovadă care arată că o versiune 3D a jocului cu un înger suficient de puternic are o strategie câștigătoare folosește „gărzi”. Pentru orice cub de orice dimensiune, există un paznic care veghează asupra cubului. Înainte de fiecare mișcare, gardianul decide dacă cubul pe care îl urmărește este periculos, sigur sau aproape sigur. Definițiile „sigur” și „aproape sigur” ar trebui clarificate - această decizie se bazează exclusiv pe densitatea punctelor de blocare din cub și pe dimensiunea cubului.

Dacă mișcarea îngerului nu este predeterminată, pur și simplu ne deplasăm în sus. Dacă unele cuburi pe care îngerul le lasă sunt în siguranță, atunci garda celui mai mare cub este instruit să se asigure că îngerul iese din cub printr-una dintre fețele cubului. Dacă gardianul este instruit să escorteze îngerul spre o anumită margine, gardianul face acest lucru construind o cale prin subcuburile sigure. Gardienii din aceste cuburi sunt instruiți să escorteze îngerul prin subcuburile sale. Calea unui înger într-un subcub nu este definită până când îngerul intră în acel cub. Chiar și așa, calea este aproximativ definită. Strategia asigură că diavolul nu poate alege un loc în calea îngerului suficient de departe pentru a-l bloca.

Se poate dovedi că strategia funcționează deoarece timpul necesar diavolului pentru a transforma un cub sigur pe calea îngerului într-unul periculos este mai mare decât timpul necesar îngerului pentru a ajunge la cub.

Această dovadă a fost publicată de Lider [ și Bolobas în 2006 [5] . O dovadă similară a fost publicată de Martin Kutz în 2005 [6] [7] .

Proof of Mate pentru un înger cu putere 2

Mate [4] a introdus un diavol plin de tact , fără a distruge niciodată o celulă pe care o ocupase anterior un înger. Dacă un înger joacă împotriva unui diavol plin de tact, se presupune că diavolul câștigă dacă restricționează mișcarea îngerului la o zonă limitată (altfel, îngerul doar sare înainte și înapoi în două pătrate și nu pierde niciodată!).

Mate a oferit o strategie de câștig explicită pentru un înger împotriva unui diavol plin de tact și a arătat că dacă un înger câștigă împotriva unui diavol plin de tact, atunci un înger câștigă împotriva unui diavol adevărat.

În prima parte, îngerul învinge diavolul plin de tact presupunând că întregul semiplan stâng este distrus (în plus față de toate celulele distruse de diavol) și tratând celulele distruse ca pe pereții unui labirint, care este ocolit conform regulii „mâna stângă”. Adică, îngerul își ține mâna stângă pe peretele labirintului și merge de-a lungul peretelui. Se poate dovedi că un diavol plin de tact nu poate captura un înger care adoptă o astfel de strategie.

A doua parte este dovedită prin contradicție și, prin urmare, dovada lui Mate nu oferă o strategie imediată de câștig împotriva adevăratului diavol. Mate notează însă că această dovadă poate fi, în principiu, adaptată pentru a obține o astfel de strategie.

Dovada lui Bowditch pentru un înger cu putere 4

Bodwich definește [3] o variantă (jocul 2) a jocului de deschidere cu următoarele modificări de regulă:

Îngerul se poate întoarce în orice pătrat pe care l-a vizitat deja, chiar dacă diavolul a încercat apoi să o blocheze.
K-diavolul trebuie să viziteze celula de k ori înainte de a fi blocată.
Îngerul mută o celulă în sus/jos/stânga/dreapta.
Pentru a câștiga, îngerul trebuie să urmeze calea circulară descrisă mai jos.

O cale circulară este o cale în care există un arc semi-infinit (un drum auto-disjunc cu un punct de început, dar fără un punct final) și sunt bucle disjunse pe perechi cu următoarele proprietăți: $\pi =\cup _{i=1}^{\infty }(\sigma _{i}\cup \gamma _{i})$ $\sigma =\cup _{i=1}^{\infty}\sigma _{i)$ ${\gamma _{i)}$

$\forall i:|\gamma _{i}|\leq i$ unde este lungimea buclei i-a. $|\gamma _{i}|$

(Pentru a fi complet specific , trebuie să înceapă și să se termine la punctul final și trebuie să se termine la punctul de început .) $\gamma _{i)$ $\sigma_i$ $\sigma_i$ $\sigma _{i+1}$

Bodwich sugerează o variantă (jocul 1) a jocului cu modificările 2 și 3 și 5-diavol. El a arătat că strategia câștigătoare din acest joc ar oferi strategiei câștigătoare a jocului original pentru un înger cu putere 4. El a arătat, de asemenea, că un înger care joacă împotriva unui 5-diavol (jocul 2) ar putea obține o victorie folosind un algoritm destul de simplu.

Bodwich afirmă că un înger cu 4 forțe poate câștiga versiunea originală a jocului imaginându-și un înger fantomă jucând împotriva unui diavol cu 5 în jocul 2.

Îngerul urmează calea posibilă a îngerului fantomă, dar evită buclele. Deoarece calea este un arc semi-infinit, îngerul nu se va întoarce în niciun pătrat pe care l-a vizitat deja și, prin urmare, calea va fi calea câștigătoare a jocului original. $\sigma$

Variații și generalizări

În spațiul 3D, având în vedere că îngerul crește întotdeauna coordonatele y și diavolul este limitat la trei planuri, nu se știe dacă diavolul are o strategie câștigătoare.

Vezi și

Killer driver problem , un alt joc de matematică în care un jucător lent, dar agil, încearcă să depășească un inamic mai rapid, dar mai puțin agil.
Teoria căutării garantate

Note

↑ John H. Conway. Jocuri fără șansă / Richard Nowakowski. - Publicaţiile MSRI, 1996. - V. 29. - S. 3-12. Problema îngerilor Arhivat 29 septembrie 2020 la Wayback Machine
↑ Elwyn R. Berlekamp , John H. Conway și Richard K. Guy , Winning Ways for your mathematical plays, volumul 2: Games in Particular , Academic Press, 1982.
↑ 1 2 Brian H. Bowditch , Jocul îngerilor în avion , Combin. Probabil. Calculator. 16(3):345-362, 2007.
↑ 1 2 András Máthé, Îngerul puterii 2 învinge , Combin. Probabil. Calculator. 16(3):363-374, 2007
↑ B. Bollobás și I. Leader, Îngerul și diavolul în trei dimensiuni. Jurnalul de Teorie Combinatorie. Seria A. vol. 113 (2006), nr. 1, pp. 176-184
↑ Martin Kutz, Îngerul lui Conway în trei dimensiuni, Teoretul. Comp. sci. 349(3):443-451, 2005.
↑ Martin Kutz, The Angel Problem, Positional Games, and Digraph Roots, teză de doctorat Arhivată 11 decembrie 2007 la Wayback Machine FU Berlin, 2004