카드 제안 게임

예전에 직접 만든 "카드 제안 게임"이 있다.

(1) $n$개의 카드가 책상 위에 있고, 이 카드들에는 서로 다른 자연수가 적혀 있다. 이 자연수들은 각각 점수이다. 이 카드들은 적힌 자연수에 따라 오름차순 정렬되어 있다. (2) $P$은 먼저 $n$개의 카드 중 하나를 골라 에게 물어본다. “이 카드 가질래?”. $Q$는 이 제안을 거부할 수도 있고 수락할 수도 있다. 수락하면 그 카드를 $Q$가 가지고 $Q$는 $P$이 했던 것처럼 카드를 고르고 물어본다. 만일 거부한다면 $P$은 반드시 자신이 제안한 카드를 자신이 가져야 하며, 다시 카드를 골라 $Q$에게 물어봐야 한다. (3) 책상 위 모든 카드가 사라지면 게임이 종료되고 자신이 가진 카드들에 적힌 수들의 총합이 자신의 점수이며 높은 사람이 승리한다.

지지 않을 전략을 처음 증명하려 할 때는 $n$에 따라 경우를 나누며 복잡하게 접근했는데 아주 명쾌하게 귀납적으로 증명할 수 있었다.
크기순으로 카드의 숫자를 $a_{1}, a_{2}, \dots , a_{n}$라고 하자. $n=1$이면 그냥 $P$가 주는 카드를 $Q$가 수락하면 승리한다. 이제, 수학적 귀납법으로 $n-1$일 때 성립하면 $n$이 성립함을 증명하자. $n$개의 카드 중 첫 번째로 $P$가 준 카드의 숫자를 $a_{k}$라고 하자. 이제 $a_{k}$가 적힌 카드 제외 총 $n-1$개의 카드게 남게 된다. 이때 만약 $Q$가 $n-1$에서 지지 않을 전략을 가진다면 이기는 여러 전략 중에서 가장 최선의 전략으로 게임 종료 후 서로의 최대 점수 차이가 있다. 이를 $m$이라고 하자. $a_{k}>m$이라면 $a_{k}$를 가지고 $a_{k}-m$로 이긴다. 만약 $a_{k}=m$이면 가지든 말든 결국 비긴다. $a_{k}<m$이면 거부하고 $m-a_{k}$ 차이로 이긴다. 즉, $P$가 구성을 잘하면 비긴다.
근데 이 전략을 알고 있다고 해도 $n-1$때 $m$을 찾는 것도 일이라서 사실상 실제 게임을 하게 되면 딱히 효과적이지는 않다. 약간 논리 게임으로 간단하게 하기에 괜찮은 것 같다.