동전 게임

영희와 철수는 번갈아 가면서 동전을 이동하는 게임을 한다.

게임 시작 시 동전은 일렬로 된 빈칸의 0번 칸에 놓여 있다. 동전 이동 규칙은 아래와 같다.

• 두 사람은 번갈아 가면서 동전을 이동한다.
• 각 사람은 자기 차례가 되면 동전을 한 칸, 또는 두 칸, 또는 세 칸 오른쪽으로 옮길 수 있다.
• 칸의 번호가 7의 배수인 곳에는 동전을 놓을 수 없다.
• 게임 시작 시 주어진 목적지 번호 에 대해, 번호가 이상인 칸에 동전을 처음 옮기는 사람이 게임에서 이긴다.
• 영희가 먼저 게임을 시작한다.

두 사람 모두 게임의 승리 전략에 대해 잘 이해하고 있어 자기가 이기려는 전략을 따라 동전을 이동한다.

예를 들어, 인 경우, 아래 그림에서 보인 것처럼 동전을 옮기면 영희가 9번 칸에 동전을 놓을 수 있어서 게임에서 이긴다. 참고로, 인 경우엔 영희가 무조건 이길 수 있다.

일 때, 각 게임의 승자를 구하면?

문제 형식

객관식

출처

• KOI 2022 1차대회 고등부 1교시 11번