폴리매스

A, B, C가 다음과 같은 게임을 한다.

1. A와 C가 방에 들어간다.

2. C가 그림과 같은 체스판의 칸 중 한 곳에 열쇠를 숨긴다. 즉, A는 열쇠의 위치를 안다.

3. C는 체스판의 각 칸에 동전을 앞면 혹은 뒷면이 위로 오도록 배치한다.

4. A는 그 동전 중 하나를 뒤집는다.

5. A가 나가고 B가 들어와 열쇠의 위치를 맞춘다.

이를 시작하기 전, A와 B는 얼마든지 상의가 가능하지만, C는 A와 B가 상의하는 것을 듣고 2. 또는 3.에서 열쇠의 위치나 동전의 배열을 그 전략이 가능하면 통하지 않게끔 배치할 것이다. (예를 들어, A와 B가 "혼자 앞면이거나 뒷면인 동전에 열쇠가 있게 할게" 라고 상의했다면 C는 그것을 듣고, 동전을 앞면 32개, 뒷면 32개가 되도록 동전을 배치할 것이다.)

다음 물음에 답하라.

Q1. B가 항상 열쇠의 위치를 찾을 수 있는 방법이 존재하는가?

Q2. 8X8 체스판에서 딱 한칸만 제거한다면, 아직도 B가 항상 열쇠를 찾을 수 있는 방법이 존재하는가?

Q3. 8X8 체스판이 아니라 7X7, 6X6 체스판이었다면 B가 항상 열쇠의 위치를 찾을 수 있는 방법이 존재하는가?

Q4. B가 항상 열쇠의 위치를 찾을 수 있는 방법이 존재하는 nXn 체스판은 유한한가? 유한하다면 개수는 몇개인가? 무한하다면 n에 특징이 존재하는가?

Q5. 체스판이 정사각형이 아닐 경우에도 B가 항상 열쇠를 찾을 수 있는 방법이 존재하는가? 이 경우에, 체스판의 칸의 수는 어떤 특징을 띄는가?

(Q2.~Q5.에서 체스판이 변형이 되는데, "그런 체스판은 체스판이 아니니까 없다."는 답이 아닙니다.)