민정과 성빈이 무한히 넓은 바둑판에서 다음 규칙에 따라 한번씩 번갈아 시행을 하는 게임을 한다.
처음에 민정부터 시작하며, 각 시행은 두 이웃한 교차점을 잇는 선분 중 아직 방향이 정해지지 않은 것 하나를 골라서 화살표 표시를 하여 방향을 정하는 것이다. 어느 순간에 방향이 정해진 선분들로 이루어진 유향폐곡선(한 점에서 출발하여 방향이 정해진 선분들의 화살표 방향을 따라 이동하면 시작점으로 되돌아올 수 있는 폐곡선)이 만들어지면 성빈이 이긴다. 성빈이 항상 이길 수 있는 전략이 존재하는가?
태그 보관물: 필승전략
1999 미국수학올림피아드 5번문제
두 사람이 다음과 같은 Y2K라는 게임을 한다. $1 \times 2000$ 판에 서로 번갈아가며 문자 S 혹은 O를 빈칸에 하나씩 써 넣는데, SOS라는 연속된 글자를 먼저 만드는 사람이 이긴다. 만약 SOS라는 문자열이 나오지 않으면 무승부가 된다. 두 번째 사람이 필승의 전략을 가짐을 증명하여라.
2013 제74회 William Lowell Putnam 수학경시대회 B6
홀수인 정수 $n\ge 1$이 있다. 철수와 영희가 철수부터 시작해서 교대로 아래와 같은 규칙으로 진행하는 게임을 한다. 게임판은 일렬로 나열한 $n$개의 칸으로 구성되어 있는데 처음에는 모든 칸이 비어있다. 각자 순서가 되면 아래 두 시행 중 하나를 할 수 있다.
- 빈 칸을 하나 골라 돌을 놓는다.
- 어떤 칸에서 돌을 하나 빼고, 그 칸의 왼쪽에 있는 칸들 중 빈 칸이 있다면 그 중 가장 가까운 빈 칸에 돌을 하나 놓고, 마찬가지로 그 칸의 오른쪽에 있는 칸들 중 빈 칸이 있다면 그 중 가장 가까운 빈 칸에 돌을 놓는다.
단, 앞서 나타났던 상황과 똑같은 돌 배치가 되는 상황이 되지 않는 시행만 허용된다고 한다. 철수나 영희 중 시행을 할 수 없는 사람이 진다고 한다. 두 사람 모두 최선을 다한다고 할때, 처음에 철수는 어떤 시행을 해야 하는가?
2012 국제대학생수학경시대회(IMC) 둘째날 1번문제
다항식 $f(x)=x^{2012}+a_{2011}x^{2011}+\cdots+a_1 x+a_0$를 이용하여 아인슈타인과 심슨이 다음 게임을 한다. 돌아가면서 각자 $a_0$, $a_1$, $\ldots$, $a_{2011}$ 중 하나의 계수를 골라서 거기에 실수 값을 대입한다. 아인슈타인이 먼저 계수를 골라 대입한다고 한다. 한번 값이 대입되면 그 계수는 누구도 바꿀 수 없다고 한다. 게임은 모든 계수가 정해지면 끝난다. 다항식 $f(x)$가 어떤 고정된 다항식 $m(x)$로 나누어떨어지면 심슨이 이기고, 그렇지 않으면 아인슈타인이 이긴다.
(a) 만일 $m(x)=x-2012$라면 누가 필승전략이 있는가?
(b) 만일 $m(x)=x^2+1$이라면 누가 필승전략이 있는가?
(2012년 7월 29일 불가리아 Blagoevgrad. 5문제/5시간)
2012 국제대학생수학경시대회(IMC) 첫째날 3번문제
정수 $n>1$에 대해 $S_n$을 $1$, $2$, $3$, $\ldots$, $n$의 순열군(permutation group)이라고 하자. 두 사람 $A$와 $B$가 아래와 같은 게임을 한다. 돌아가며 한 사람씩 아직 뽑지 않은 $S_n$의 원소를 하나씩 뽑는다. 뽑힌 $S_n$의 원소들이 $S_n$을 생성하면 게임이 끝난다. 마지막에 원소를 뽑은 사람이 진다고 하고 처음에 $A$부터 시작한다고 한다. 누가 필승전략이 있는가?
(2012년 7월 28일 불가리아 Blagoevgrad. 5문제/5시간)
2012 국제수학올림피아드 3번문제
두 명의 선수 A와 B가 거짓말쟁이 추측 게임을 한다. 이 게임의 룰은 두 양의 정수 $k$와 $n$에 의해 결정되고 이 숫자들을 선수들은 미리 알고 있다.
게임이 시작될 때 A는 먼저 양의 정수 $x$와 $N$을(단, $x\le N$) 선택한 후, A는 B에게 $x$는 감추고 $N$은 무엇인지 정직하게 알려 준다. B는 $x$에 대한 정보를 얻기 위해 다음과 같은 방식으로 A에게 질문들을 한다. B는 각 질문마다 양의 정수로 이루어진 집합 $S$을 지정해 그것이 무엇인지 설명한 후(이전에 지정한 집합과 같아도 상관없다), $x$가 그 집합에 속하는 지 물어 본다. B는 원하는 만큼 얼마든지 여러 번 질문할 수 있다. A는 B가 질문할 때마다 `예’ 또는 `아니오’로 즉시 답을 해야 한다. 단, A는 몇 번이고 거짓으로 대답할 수 있다. 하지만, A는 임의의 $k+1$번의 연속한 B의 질문에 대하여 적어도 한 번은 정직하게 대답하여야 한다.
B는 원하는 만큼 충분히 여러 번 질문한 후, $n$개 이하의 양의 정수로 이루어진 집합 $X$를 제시하여야 한다. 이때, $x$가 $X$에 속하면 B가 이기고, 그렇지 않으면 B가 진다. 다음을 각각 보여라.
- $n\ge 2^k$이면, B의 필승 전략이 존재한다.
- 충분히 큰 모든 $k$에 대하여, B의 필승 전략이 존재하지 않는 어떤 정수 $n\ge 1.99^k$이 존재한다.
(2012년 7월 10일 아르헨티나 Mar del Plata)