[5월의 퍼즐] 초콜릿 와플

충명과 당신은 초콜릿을 무한히 많이 가지고 있다. 초콜릿은 두 가지 모양이 있으며, 각 모양은 X-초콜릿과 F-초콜릿이라는 이름이 붙어 있다.

X-초콜릿

F-초콜릿

충명과 당신은 이걸로 무엇을 하고 놀지 고민하다가, 옆에 우연히 200×200 크기의 정사각형 와플이 있는 것을 발견하고는 보드게임을 하기로 했다.

보드게임의 규칙은 간단하다. 충명부터 시작하여, 와플 위에 번갈아 가며 초콜릿을 하나 내려놓으면 된다. 초콜릿은 반드시 격자에 꼭 맞게 놓아야 하며, 돌리거나 뒤집어서 놓아도 된다. 초콜릿을 내려놓을 때는 이미 있는 초콜릿과 겹치지 않게 빈 공간에 놓아야 한다.

와플 밖으로 초콜릿의 일부가 튀어나갈 수도 있는데, 이 경우에는 와플의 상하좌우 모서리가 서로 이어진 것처럼 간주하고 튀어나간 만큼을 잘라서 반대쪽에 놓는다. 물론 자른 초콜릿을 놓을 공간에 이미 다른 초콜릿이 놓여 있었다면 초콜릿을 내려놓을 수 없다. 그림으로 설명하면 다음과 같다.

(여백이 부족해 16×16 크기의 와플을 사용했다.)

초콜릿을 내려놓지 못하는 사람이 패배하고, 승리한 사람이 초콜릿이 올라간 와플을 혼자 다 먹기로 했다. 충명을 확실히 이기고 초콜릿 와플을 독차지할 수 있는 전략을 세우자!

게임은 두 가지 버전이 있다. 1번 문제를 먼저 풀어 보는 것이 2번 문제를 푸는 데 도움이 될 것이다

1. 대칭 게임: 충명도 당신도 X-초콜릿과 F-초콜릿 두 가지 모두를 사용할 수 있다. 자신의 차례가 되면 둘 중 원하는 모양의 초콜릿을 하나 선택하여 내려놓으면 된다.

2. 비대칭 게임: 충명은 X-초콜릿만 사용할 수 있고 당신은 F-초콜릿만 사용할 수 있다.

비대칭 게임은 게임판을 잘 왜곡해서 대칭 게임과 동등해지도록 바꾼 뒤 대칭 게임의 해법을 적용하는 방향으로 전략을 세우는 것이 도움이 될 것이다. 왜곡을 어떻게 해야 할지 잘 모르겠는 독자는 다음의 힌트를 참고하자.

힌트: X-초콜릿을 두 줄과 한 줄로 자른 뒤 한 칸 밀면 어떻게 자르고 밀든 F-초콜릿이 되며, 반대로 F-초콜릿을 같은 방법으로 정확하게 잘 자르고 밀면 X-초콜릿이 된다.