$5 \times 9$(5행 9열) 크기의 직사각 체스판에서 다음과 같은 게임을 한다. 처음에 몇 개의 원판이 이 체스판의 임의의 칸들에 놓여있었다. 단, 한 칸에는 원판이 하나만 놓일 수 있다. 완전한 움직임이란 이 체스판의 모든 원판을 다음과 같은 규칙에 따라 동시에 움직이는 것을 말한다.
(i) 각각의 원판은 위, 아래, 왼쪽, 오른쪽 중의 한 방향으로 한 칸을 이동할 수 있다.
(ii) 위나 아래로 움직였던 원판은 다음 번 완전한 움직임 때는 왼쪽이나 오른쪽으로 움직여야 한다.
(iii) 왼쪽이나 오른쪽으로 움직였던 원판은 다음 번 완전한 움직임 때는 위나 아래로 움직여야 한다.
(iv) 완전히 움직인 후에도 각 칸에는 두 개 이상의 원판이 있을 수 없다.
더 이상 완전한 움직임을 행할 수 없으면 이 게임은 끝난다. 처음에 이 체스판 위에 33개의 원판이 있었다면 이 게임은 유한번 안에 끝남을 증명하여라. 또한, 이 게임이 영원히 계속 되도록 처음에 32개의 원판을 잘 배치하고 게임을 진행하는 것이 가능함을 증명하여라.
태그 보관물: 게임
1995 아일랜드 수학올림피아드 4번문제
다음과 같이 수직선 위에서 혼자 하는 놀이가 있다: 이 놀이에서는 수직선의 어떤 정수점에 원판들이 쌓이게 된다. 두 장 이상의 원판이 쌓인 점 $j$를 하나 택하고, 거기서 이웃한 점 $j-1$과 $j+1$로 한 장씩 옮겨쌓는 움직임만이 허용된다. 처음에는 원점에만 $2n+1$개의 원판이 있었다.
이 놀이는 $\frac16n(n+1)(2n+1)$번의 움직임이면 어떻게 했어도 항상 더 이상의 움직임이 불가능하여 놀이가 끝나게 됨을 증명하여라. 그리고, 놀이가 끝났을 때는 항상 $-n$부터 $n$까지의 모든 점에 원판이 하나씩 있게 됨을 보여라.
1989 아일랜드 수학올림피아드 7번문제
$n$명의 사람들이 꼭 한 가지씩의 정보를 알고 있고, 모든 정보는 서로 다르다. 사람 A가 사람 B에게 전화할 때마다, A는 B에게 그가 알고 있는 모든 것을 말하고, B는 A에게 아무 것도 말하지 않는다고 하자. 모든 사람이 모든 정보를 알게 되기 위해 필요한 최소한의 전화걸기 횟수는 몇 번인가? 당신이 구한 답이 최소임을 증명하여라.
2013 국제수학올림피아드 Short List C8
두 선수 $A$, $B$가 수직선 위에서 색칠하기 게임을 한다. 선수 $A$는 4 cc의 검은색 페인트 통을 가지고 있는데, $p$ cc의 페인트는 길이가 $p$인 폐구간을 검정색으로 칠할 수 있다. 각자 차례가 되면 선수 $A$는 어떤 양의 정수 $m$을 골라 $1/2^m$ cc만큼의 페인트를 페인트 통에서 꺼내어 $B$에게 준다. 이때 $B$는 어떤 정수 $k$를 골라서 $k/2^m$부터 $(k+1)/2^m$까지의 폐구간을 검게 칠한다. (이미 그 중 일부는 검은색이었을 수 있다.) 페인트 통을 다 비웠는데도 $0$부터 $1$까지 실수 중 검은색이 아닌 것이 있으면 선수 $A$가 이긴다고 하자.
선수 $A$가 유한번만에 이 게임에서 이길 수 있는 전략이 존재하는가?
2013 국제수학올림피아드 Short List N5
정수 $k\ge 2$가 있다. 두 사람 A, B가 아래과 같은 수게임을 한다. 게인을 시작할 때 칠판에 $k$보다 크거나 같은 어떤 정수 $n$이 적혀있다. 이때, A부터 시작해서 돌아가면서 칠판에 적힌 수 $m$을 지우고 $k\le m’\lt m$이면서 $m$과 서로소인 어떤 수 $m’$으로 바꿔적는다. 더 이상 이렇게 바꿀 수 없는 사람이 진다고 한다.
처음에 적힌 수가 $n$($\ge k$)일 때 B가 항상 이길 수 있는 전략이 존재하면 그 수 $n$을 좋다고 하고 아니면 나쁘다고 하자.
어떤 두 정수 $n,n’\ge k$에서, $k$이하인 $n$의 소인수의 집합이 $k$이하인 $n’$의 소인수의 집합과 같다고 한다. 이때, 두 수 $n$, $n’$은 함께 좋거나 함께 나쁘다는 것을 증명하라.
2014 유럽여학생수학올림피아드 5번문제
양의 정수 $n$이 주어져있다. 총 $n$개의 상자 각각에 음아닌 정수개만큼의 바둑알이 있다. 어떤 상자를 골라 그 상자 안에 있는 두 개의 바둑알을 꺼내어 하나는 버리고 다른 하나는 다른 원하는 상자에 넣는 것을 하나의 시행이라 하자. 바둑알이 상자에 처음 주어진 초기 상황에서 0번 이상의 유한번 시행을 거쳐 빈 상자가 없게 만들 수 있으면 그것을 좋은 상황이라고 하자. 어느 상자에라도 바둑알을 하나만 더 넣으면 좋은 상황이 되는 좋지 않은 초기 상황을 모두 구하라.