마법사들의 결투

문제

두 마법사가 수면 위 100m 공중에서 마법대전을 펼친다. 두 마법사는 선공, 후공으로 나뉘어 번갈아가며 마법을 시전한다.

마법사들이 쓸 수 있는 주문 종류는 “자신과 상대의 고도를 각각 \(a\), \(b\)만큼 낮춘다” 이다. (\(0 < a < b\), \(a\), \(b\)는 실수)

공정한 대전을 위해 미리 사용 가능한 주문들의 집합이 주어진다. 마법사들은 이 집합 내의 주문만 사용 가능하며, 이전에 사용한 주문들은 몇번이고 다시 쓸 수 있다.

마법사는 주문 시전 이후, 본인은 수면 위에 있고 상대가 수면 아래에 있다면 승리한다.

다음 조건에서 후공 마법사가 이길 수 있는 주문 집합이 존재할까?

a) 주문 집합의 크기가 유한함
b) 주문 집합의 크기가 무한함

풀이

a) 주문 집합의 크기가 유한함

후공 마법사가 이길 수 있는 집합은 없다.

선공이 집합 내의 \(b-a\)가 최대인 주문만 시전하면 후공은 그 차이를 따라잡을 수 없다.

b) 주문 집합의 크기가 무한함

집합 \(\{(a,b) \mid 0 < a < b < 100\}\) 에서 후공 마법사가 반드시 이긴다.

선공이 아무 주문 \((a,b)\)을 사용하더라도, 후공은 \(a+d>100\), \(b+c<100\)을 만족하는 \((c,d)\)를 만드시 집합 내에서 찾을 수 있다.

출처

Tournament of Towns 2010 Fall, Seniors A level #4