엔젤 문제

엔젤 문제는 존 호튼 콘웨이가 제안한 조합 게임 이론의 문제이다.이 게임은 일반적으로 천사와 악마 ^[1]게임이라고 불린다.그 게임은 천사와 악마라고 불리는 두 명의 플레이어가 한다.무한 체스 보드(또는 2D 격자의 점)에서 플레이됩니다.엔젤의 파워 k(자연수 1 이상)는 게임 시작 전에 지정됩니다.천사가 한 칸에 있으면 게시판이 텅 비기 시작한다.각 턴마다, 천사는 체스 킹의 최대 k개의 움직임으로 도달할 수 있는 다른 빈 사각형으로 점프한다. 즉, 출발 사각형으로부터의 거리는 무한 노름에서 최대 k개이다.악마는 차례대로 천사를 포함하지 않는 정사각형 하나에 블록을 추가할 수 있습니다.천사는 막힌 정사각형을 뛰어넘을 수는 있지만, 그 위에 착륙할 수는 없습니다.천사가 움직일 수 없으면 악마가 이긴다.천사는 무한히 살아남음으로써 승리한다.

천사의 문제는 충분한 힘을 가진 천사가 이길 수 있느냐는 것이다.

선수 중 한 명에게는 반드시 승리 전략이 있어야 한다.악마가 억지로 이길 수 있다면 한정된 수의 움직임으로 이길 수 있다.만약 악마가 승리를 강요할 수 없다면, 천사가 패배를 피하기 위해 취할 수 있는 행동과 그것을 위한 승리 전략은 항상 그러한 행동을 선택하는 것이다.보다 추상적으로, "보상 세트"(즉, 천사가 이기는 모든 플레이 세트)는 폐쇄 세트(모든 플레이 세트의 자연 토폴로지에서)이며, 이러한 게임이 결정되는 것으로 알려져 있다.물론 어떤 무한게임이라도 플레이어 2가 승리전략을 가지고 있지 않으면 플레이어 1은 항상 승리전략이 없는 위치로 이어지는 동작을 선택할 수 있지만, 일부 게임에서는 단순히 영원히 플레이하는 것이 플레이어 1에게 승리를 주지 않기 때문에 미정의 게임이 존재할 수 있다.

Conway는 이 문제에 대한 일반적인 해결책에 대한 보상금(충분히 높은 힘을 가진 천사의 승리 전략에 100달러, 천사의 힘에 관계없이 악마가 이길 수 있다는 증거에 1000달러)을 내걸었다.더 높은 차원으로 먼저 진보가 이루어졌다.2006년 말, 천사가 이길 수 있다는 것을 보여주는 독립적인 증거가 등장하면서 원래의 문제가 해결되었다.보디치는 4천사(k=4의 힘을 가진 천사)가 이길 수 있다는^[2] 것을 증명했고 마테와^[3] 클로스터는^[4] 2천사가 이길 수 있다는 증거를 제시했다.

기본 전략과 그것이 작동하지 않는 이유

천사를 위한 많은 직관적인 탈출 전략은 물리칠 수 있다.예를 들어, 만약 천사가 가까운 블록으로부터 도망치려고 한다면, 악마는 북쪽 멀리 있는 거대한 말굽을 만든 다음, 천사의 바로 남쪽에 있는 광장을 반복해서 먹음으로써 천사를 덫으로 찔러 넣을 수 있다.만약 천사가 아주 멀리 떨어져 있는 덫을 피하려고 한다면, 악마는 북쪽으로 작은 말굽을 만들고, 남쪽으로 멀리 있는 사각형들을 먹음으로써 천사를 덫으로 찌를 수 있다.

엔젤은 가능한 한 빨리 올라가고 가끔 동쪽이나 서쪽으로 지그재그와 결합하여 명백한 함정을 피할 수 있을 것 같다.이 전략은 이 천사의 미래 위치가 원추형 안에 있고, 악마는 특정한 방법으로 원추형 사이에 벽을 쌓을 수 있다는 것을 지적함으로써 물리칠 수 있다. 그래서 마침내 천사가 멀리 도착했을 때, 악마는 뚫을 수 없는 벽을 만들었고, 천사는 북쪽으로 이동하기를 고집하기 때문에, 천사는 움직일 수 없다.조금도.

역사

이 문제는 "천사와 네모난 방패"라는 이름으로 1982년 Berlekamp, Conway, and ^[5]Guy에 의해 처음 출판되었다.2차원에서 일부 초기 부분 결과는 다음과 같다.

• 천사가 1의 힘을 가졌다면 악마는 이기는 전략을 가지고 있다(Conway, 1982)(Conway에 따르면 이 결과는 실제로 Berlekamp에 기인합니다).이것은 Kutz의 ^[6]논문 섹션 1.1에서 읽을 수 있습니다.
• 만약 천사가 y좌표를 줄이지 않는다면, 악마는 승리 전략을 가지고 있다(Conway, 1982).
• 만약 천사가 항상 원점으로부터 거리를 늘린다면, 악마는 승리 전략을 가지고 있다(Conway, 1996).

3차원으로 다음과 같이 나타났다.^{[citation needed]}

• 만약 천사가 항상 y좌표를 늘리고 악마가 한 평면에서만 플레이할 수 있다면, 천사는 승리 ^[7]전략을 가지고 있다.
• 만약 천사가 항상 y좌표를 늘리고 악마가 두 평면에서만 플레이할 수 있다면, 천사는 승리 전략을 가지고 있다.
• 엔젤은 파워 13 이상일 경우 승리 전략을 가지고 있습니다.
• 만약 우리가 악마의 무한한 거리 d에 각 경기 1<>d2<d3<⋯{\displaystyle d_{1}<, d_{2}<, d_{3}<, \cdots}을 가지고 있다면, 그것이 높은 충분한 힘을 그러면 천사는 여전히.("거리 d에서 놀{\displaystyle d}"으로서 우리는 악마는 얼마나 자주'o'를 이 거리에 노는 것을 허락 받지 않다는 의미에서 이길 수 있rigin).[의심스러운 –을 논의하]

마침내, 2006년에 (천사의 문제를 널리 알리는 데 도움을 준 피터 윙클러의 책 수학 퍼즐이 출판된 지 얼마 되지 않아) 천사가 2차원에서 승리 전략을 가지고 있다는 4개의 독립적이고 거의 동시적인 증거가 나왔다.브라이언 보디치의 증명은 4천사, 오드바르 클로스터의 증명과 안드라스 마테의 증명은 2천사입니다.Péter Gcss의 증거는 훨씬 더 큰 상수에 대해서만 유효하다.Bowditch와 Mathé의 증거는 Combinatorics, Probability and Computing에서 발표되었습니다.클로스터의 증거는 이론 컴퓨터 과학지에 실렸다.

해결되지 않은 추가 질문

3D에서는 천사가 항상 y좌표를 증가시키고 악마가 세 평면으로 제한된다는 점을 감안할 때 악마가 승리 전략을 가지고 있는지는 알 수 없습니다.

프루프 스케치

'가디언'의 증거

게임의 3차원 버전에서 고출력 천사가 승리 전략을 가지고 있다는 것을 보여주는 증거는 "가디언"을 이용한다.모든 크기의 큐브마다 그 큐브를 감시하는 보호자가 있다.보호자들은 그들이 지켜보고 있는 큐브가 안전하지 않은지, 안전한지 또는 거의 안전한지 매번 결정한다."안전"과 "거의 안전"의 정의를 선택해야 합니다.이 결정은 전적으로 해당 큐브에서 차단된 점의 밀도와 해당 큐브의 크기에 따라 결정됩니다.

천사가 명령을 받지 않으면, 그냥 위로 올라갑니다.만약 천사가 점유하고 있는 몇 개의 큐브가 안전하지 않다면, 이 큐브들 중 가장 큰 큐브의 수호자는 그 큐브의 테두리 중 하나를 통해 천사가 떠날 수 있도록 준비하라는 지시를 받는다.보호자가 큐브에서 천사를 특정 얼굴로 호위하도록 지시받으면, 보호자는 안전한 서브큐브의 경로를 그려서 호위합니다.그런 다음 이 큐브 안의 수호자들은 각각의 큐브를 통해 천사를 호위하도록 지시받습니다.주어진 서브큐브에서 천사의 경로는 천사가 그 큐브에 도착할 때까지 결정되지 않습니다.그래도 그 경로는 대략적으로 결정될 뿐이다.이것은 악마가 길을 따라 충분히 멀리 떨어진 곳을 골라 막을 수 없다는 것을 보증한다.

이 전략은 효과가 있다는 것을 증명할 수 있다. 왜냐하면 천사가 가는 길에 있는 안전한 큐브를 안전하지 않은 큐브로 변환하는 데 걸리는 시간이 천사가 그 큐브에 도달하는 데 걸리는 시간보다 더 길기 때문이다.

이 증거는 2006년에 Imre Leader와 Béla Bolobas에 의해 발표되었다.^[8]2005년 ^[6][9]마틴 커츠에 의해 실질적으로 유사한 증거가 발표되었다.

마테의 2-천사 증명

마테는^[3] 이 착한 악마를 소개하는데, 이 악마는 천사가 일찍부터 점령할 수 있는 광장을 절대 파괴하지 않는다.천사가 착한 악마와 경기를 할 때, 악마가 판의 유한한 경계 영역으로 제한한다면 패배를 인정한다(그렇지 않으면 천사는 두 칸 사이를 왔다 갔다 하며 절대 지지 않을 수 있다!).마테의 증거는 두 부분으로 나뉜다.

1. 그는 천사가 착한 악마에게 이기면 천사는 진짜 악마에게 이기게 된다는 것을 보여준다.
2. 그는 착한 악마와 맞서서 천사에게 명백한 승리 전략을 제시합니다.

대략적으로 말하면, 두 번째 부분에서, 천사는 왼쪽 반평면 전체가 파괴되는 척하고 파괴된 정사각형을 미로의 벽으로 처리함으로써, "벽에 손을 대는" 기술로 이긴다.즉, 천사는 왼손을 미로의 벽에 대고 벽을 따라 달린다.그리고 나서 누군가는 착한 악마가 이 전략을 채택하는 천사를 함정에 빠뜨릴 수 없다는 것을 증명한다.

첫 번째 부분의 증거는 모순에 의한 것이므로, 마테의 증거는 즉시 실제 악마에 대한 명백한 승리 전략을 제시하지 않는다.그러나 마테는 그의 증거가 원칙적으로 그러한 명시적인 전략을 제시하도록 조정될 수 있다고 말한다.

보디치의 사천사 증명

Brian Bowditch는^[2] 다음과 같은 규칙 변경으로 원래 게임의 변형(게임 2)을 정의합니다.

1. 천사는 그 후 악마가 막으려 해도 이미 갔던 어느 광장으로든 돌아갈 수 있다.
2. k-devil은 차단되기 전에 k개의 정사각형을 방문해야 합니다.
3. 천사는 위, 아래, 왼쪽 또는 오른쪽으로 한 칸씩 이동합니다(공작 동작).
4. 이기려면 엔젤은 회선 경로(아래 정의)를 추적해야 합니다.

$순회{\displaystyle }$ 경로는 경로 ${\displaystyle =}$ = ${\displaystyle i_{}^{}}$ ${\displaystyle {=}_{}^{}}$ ${\displaystyle 1_{\mathrm{}}^{}}$ ${\displaystyle i_{}}$ ${\displaystyle {}_{}}$ )${\displaystyle i_{}}$） { $displaystyle \pi$= \$cup$_ {i$$=$1$}^{\$infty$}({$i}\cup \cup$ $_$${i})$입니다.$여기$서 ${\displaystyle {}_{}^{}}$ ${\displaystyle 1_{}^{}}$ ${\displaystyle {=}_{}^{}}$ ${\displaystyle 1_{}^{}}$ ${\displaystyle {\mathrm{}}_{}^{}}$ 1 =$display style$ \ $cup$ _ { i } { $i$} { i }$§$ $i(\displaystyle_{i$})는 다음 속성을 가진 쌍으로 분리된 루프입니다.

• ${\displaystyle :}$ ${\displaystyle i{}_{}}$ : ${\displaystyle {\gamma }_{}}$ i$≤$ $i$ \$displaystyle$ \ $forall i$ : \ $displaystyle _ {$ i } \$leq$$$i ${\displaystyle \mathrm{。}}$${\displaystyle {여기}_{}}$서$i$ i \$displaystyle$ \ displaystyle _ { $i$}는$$ ith 루프의 길이입니다.

(${\displaystyle {적절하게}_{}}$ $정의$하려면 i$\$\$gamma$ _${i}$의 끝점과 i$displaystyle \sigma$ _${i+1$}$$의 끝점에서 끝나야 합니다$).$

Bowditch는 5-devil의 변경 사항 2와 3을 포함한 게임의 변형(1게임)을 고려합니다.그리고 그는 이 게임에서 이기는 전략이 우리의 원래 게임에서 4-엔젤을 위한 승리 전략을 산출한다는 것을 보여준다.그리고 나서 그는 5악마를 연기하는 천사가 꽤 간단한 알고리즘을 사용하여 이길 수 있다는 것을 보여준다.

Bowditch는 게임 2에서 팬텀 엔젤이 5악마를 연기하는 모습을 상상함으로써 4천사가 게임의 원래 버전을 이길 수 있다고 주장한다.

천사는 유령의 길을 따라가지만 루프는 피한다.따라서 경로$${\(\$displaystyle \sigma)$는 반무한호이기 때문에 엔젤은 이전에 갔던 사각형으로 돌아가지 않기 때문에 원래 게임에서도 패스가 승리 경로입니다.

「 」를 참조해 주세요.

• 살인 운전기사 문제, 강력하고 교묘하게 상대방을 상대하는 또 다른 수학 게임입니다.

레퍼런스

외부 링크

• John H Conway의 Angel 문제
• 클로스터의 천사 문제 사이트