개와 고양이와 샌드위치

문제

햄이 들어간 샌드위치 \(100N\)개가 일렬로 놓여있다. 이 샌드위치로 개와 고양이가 턴제 게임을 한다.

개는 자신의 턴에 아래의 행위를 100번 시행한다.

• 양 끝 두 개의 샌드위치 중 하나를 선택하여 먹어치운다.

고양이는 자신의 턴에 아래의 행위를 1번 시행한다.

• 아무 샌드위치나 골라, 햄만 쏙 빼먹는다.

게임은 개가 먼저 진행하며, 샌드위치가 모두 사라질 때까지 진행된다.

개가 마지막으로 먹은 샌드위치가 햄이 들어있다면 개가 승리하고, 아니라면 고양이가 승리한다.

N이 얼마든 간에 개가 승리할 수 있는 전략이 있을까?

풀이

아니다. \(N=3^{100}\) 일 때 고양이의 필승 전략을 소개한다.

샌드위치에 번호를 붙이자. i번째 샌드위치의 번호는 \(i \pmod{100}\)이다.

첫 \(3^{99}\) 턴 동안 고양이는 중앙 3분의 1중 \(1\)번이 붙은 샌드위치를 골라 햄을 빼먹는다.

그 동안 개는 \(100 \times 3^{99}\) 샌드위치만 먹을 수 있으므로, 개는 고양이가 햄을 빼먹은 샌드위치를 아직 먹을 수 없다.

다음 \(3^{99}\)턴 동안 고양이는 아무 \(1\)번이 붙은 샌드위치를 골라 햄을 빼먹는다. 이제 모든 \(1\)번이 붙은 샌드위치는 햄이 없다.

다음 \(3^{100-i}\) 턴 동안 고양이는 남은 샌드위치들의 중앙 3분의 1 중 \(i\)번이 붙은 샌드위치를 골라 햄을 빼먹는다.

그 동안 개는 고양이가 햄을 빼먹은 \(i\)번이 붙은 샌드위치들을 아직 먹을 수 없다.

다음 \(3^{100-i}\)턴 동안 아무 \(i\)번이 붙은 샌드위치를 골라 햄을 빼먹는다. 이제 모든 \(i\)번이 붙은 샌드위치는 햄이 없다.

이를 반복하다 보면, 3턴동안 고양이는 중앙 3분의 1중 99번이 붙은 샌드위치를 골라 햄을 빼먹는다.

그 동안 개는 900개 중 중앙 300개는 먹을 수 없다.

다음 3턴 동안 아무 99번이 붙은 샌드위치를 골라 햄을 빼먹는다. 이제 모든 \(3\)번이 붙은 샌드위치는 햄이 없다.

이제 300개의 샌드위치가 남았으며, \(100\)번이 붙은 샌드위치들에만 햄이 들어있다.

고양이는 중앙 3분의 1 (즉, 100개) 중 \(100\)번이 붙은 샌드위치를 골라 햄을 빼먹는다. 개는 그동안 100개를 먹는다.

이제 남은 200개중 단 1개만 햄이 남았으므로 고양이가 그 샌드위치에서 햄을 빼먹으면 남은 모든 200개의 샌드위치에 햄이 없게 된다.

출처

Tournament of Towns 2021 Spring, Seniors A level #4