가로 2012칸, 세로 2012칸인 바둑판의 제일 오른쪽 윗칸과 왼쪽 아래칸을 잇는 대각선 위의 몇 개 칸이 색칠이 되어 있는데 제일 오른쪽 윗칸과 왼쪽 아래칸은 색칠되어 있지 않다고 한다. 이 바둑판 각 칸에 아래 규칙에 따라 정수를 쓴다.
1) 제일 윗 행과 제일 왼쪽 열에는 1만 쓴다.
2) 색칠된 칸에는 0을 쓴다.
3) 1), 2) 규칙이 적용되지 않는 칸에 적힌 수는 그 칸의 윗칸과 왼쪽칸에 적힌 정수의 합과 같게 한다.
이때 제일 오른쪽 아래에 적힌 수는 2011의 배수가 될 수 없음을 보여라.
태그 보관물: 바둑판
2012 이란 TST 시험1 둘째날 1번문제
평면 상에 $m+1$개의 수평선과 $n+1$개의 수직선($m,n\ge 4)$으로 만든 $m\times n$ 바둑판 형태의 그림이 주어져있다. 이 선들의 일부를 모으되, 같은 점을 2번 이상 지나지 않고, 바둑판 내부의 $(m-1)(n-1)$개 교차점들(수평선과 수직선의 교점) 모두를 지나며, 바둑판 가장자리 점은 전혀 지나지 않는 폐곡선을 생각하자. 이 폐곡선이 일직선으로 통과하는 점의 수를 $A$라 하고, 바둑판을 이루는 $m\times n$개의 사각형 중에 맞은 편에 위치한 두 변만이 이 폐곡선에 사용된 것의 수를 $B$라 하자. 바둑판을 이루는 $m\times n$개 사각형 중에 어느 변도 이 폐곡선에 쓰이지 않은 것의 수를 $C$라 하자. 이때 아래 등식을 증명하라. \[ A=B-C+m+n-1.\]
2012 캐나다수학올림피아드 4번문제
가로로 $n$칸 세로로 $m$칸이 있는 전체 직사각형 모양인 바둑판이 있다. 이 바둑판에 로봇들을 배치한다. 한 칸에 들어갈 수 있는 로봇의 수는 제한이 없다고 한다. 두 칸이 접하는 곳에 있는 선분은 빨간색이거나 파란색인데, 직사각형 바깥 가장자리의 선분은 모두 빨간색이라고 한다.
로봇에게 위, 아래, 왼쪽, 오른쪽이라는 4가지 명령어를 줄 수 있다. 명령어를 주면 모든 로봇은 같은 명령을 동시에 수행하고자 지시받은 방향으로 한 칸 이동하되, 그 사이의 선분이 빨강색인 경우는 그 로봇은 이동하지 않고 제 자리를 지킨다. 이러한 명령어는 원하는 만큼 줄 수 있다.
임의의 로봇에 대해 그 로봇을 원하는 칸으로 이동할 수 있는 명령어 유한개의 나열이 존재한다고 하자. 이때, 모든 로봇을 같은 칸으로 모으도록 하는 명령어 유한개의 나열이 반드시 존재함을 증명하라.
2012 중국 TST3 둘째날 3번문제
가로로 2012칸, 세로로 2012칸이 있는 바둑판의 각 칸에 벌이 한마리 이하로 있다고 하자. 모든 벌이 일시에 자리를 이동하되 여전히 각 칸에 한마리 이하가 되도록 이동하였다고 하자. 어떤 벌 B가 어떤 칸에서 다른 칸으로 이동할 때, 출발한 칸의 중심에서 도착한 칸의 중심까지를 나타내는 벡터를 벌 B의 이동벡터라 하자. 이때, 모든 가능한 시작 상황과 도착 상황에 대해 벌들의 이동벡터의 합의 길이의 최댓값을 구하여라.
2011 제24회 한국수학올림피아드 최종시험 6번문제
가로로 $m$칸, 세로로 $n$칸, 총 $mn$칸이 있는 직사각형 모양의 바둑판을 생각하자. 바둑판의 각 칸에 정수를 하나씩 써넣는다. 하나 이상의 칸으로 이루어진 직사각형 $R$에 대하여 다음 두 조건을 만족하는 정수 $h$가 존재하면, $R$을 ‘선반’이라 하자. (단, 직사각형 $R$의 내부에 빠진 칸은 없다.)
(1) 직사각형 $R$에 속한 모든 칸에 적힌 수는 $h$보다 크다.
(2) 직사각형 $R$의 외부의 칸 중에서, $R$에 속한 칸과 꼭지점이나 변을 공유하는 모든 칸에 적힌 수는 $h$ 이하이다.
선반의 개수가 최대가 되도록 정수를 써넣는다면, 그때 선반의 개수는 모두 몇 개인가?
(2011년 3월 27일)
2009 제22회 한국수학올림피아드 최종시험 5번문제
가로줄 $m+1$개, 세로줄 $m$개로 이루어진 총 $m(m+1)$개의 교차점이 있는 바둑판과 바둑알 하나가 주어져 있다. 두 사람이 교차점 위에 놓여 있는 바둑알을 교대로 한 칸씩 이동시키는 게임을 하는데, 바둑알은 현재 우치에서 위 아래나 좌우로 이웃한 점으로 한 칸씩 이동하여야 하며, 같은 점을 두 번 들르는 것은 허용되나, 이동하는데 한 번 이용하였던 선분은 다시 이용할 수 없다. 자기 차례에서 바둑알을 이동할 수 없으면 게임에서 지는 것으로 하자.
처음에 바둑알이 맨 아랫쪽 가로줄에 있는 교차점에 놓여 있는 경우, 먼저 하는 사람이 반드시 이길 수 있는 전략이 존재함을 보여라.
(2009년 3월 29일, 출처4시간 30분)