2021년도 한국정보올림피아드 1차 대회 1교시 고등부 문제 5번

5. 돌 무더기 게임 (9점)

문제

   A, B 두 사람이 다음과 같은 게임을 한다.

   두 사람은 테이블 하나에 서로 마주 보고 앉아있다.

   테이블 위에는 세 개의 돌 무더기가 있고, 각 무더기에는 각각 1개, 2개, 3개의 돌이 있다. A부터 시작해서 돌아가면서 게임을 진행하는데, 세 돌 무더기 중 하나를 고르고, 가져가고 싶은 개수만큼의 돌을 가져간다.

   단, 돌을 최소한 한 개는 가져가야 한다. 돌을 가져간 다음, 테이블에 돌이 남아있지 않다면, 이 사람이 이긴다.

   A, B 모두 항상 자신이 이기기 위해서 최선을 다한다. 이 때 게임의 결과는 어떻게 될까?

 

1. A가 항상 승리한다.

2. B가 항상 승리한다.

3. A가 승리할 수도, B가 승리할 수도 있다.

정답

2번

풀이

이 문제는 NIM game에서 유래된 게임으로 A, B와 같이 2명이서 하는 경우에는 필승법이 존재한다.

바로 플레이어의 차례일 때 불균형상태인 돌들을 균형 상태로 맞춰주면 된다.

이때 균형상태는 세 줄의 돌들을 2의 거듭제곱의 합으로 표현했을 때 2의 거듭제곱이 쌍으로 존재하는 것을 의미한다.

예를 들어 지금 문제의 경우에는 1,2,3 개가 있는데 1=1, 2=2, 3=2+1 이므로 1이 2개, 2가 2개가 존재한다.

이에 대한 증명은 구글에 NIM game이라고 검색하면 나온다.

A, B 모두 항상 자신이 이기기 위해서 최선의 수를 선택한다고 하였으므로 지금 돌 무더기는 균형 상태이기 때문에

A는 어쩔 수 없이 불균형상태로 만드는 수밖에 없고 결국 균형 상태로 만드는 B가 항상 승리하게 된다.

 

나는 NIM game 을 이 링크를 통해 공부하였다. 새로운 알고리즘을 알게 된 것 같아서 기분이 좋았다.

https://m.blog.naver.com/PostView.naver?isHttpsRedirect=true&blogId=nyseul&logNo=220009539606