공가져가기 게임 timer 1s memory 64MB

두 명이 번갈아서 한 개 이상의 공을 가져가는 게임이 있다. 먼저 공을 가져가는 사람을 A라고 하고 A의 상대편을 B라고 할 때, 이 게임의 규칙은 다음과 같다.

(규칙-1) 맨 처음 게임을 시작할 때 A는 모든 공을 한 번에 가져가는 것을 제외하고는 임의의 수만큼 공을 가져갈 수 있다. (규칙-2) 처음에 A가 공을 가져간 다음부터는 한 개 이상의 공을 가져가며 상대편이 바로 전에 가져간 공의 2배 이하로만 공을 가져갈 수 있다. (규칙-3) 마지막 공을 가져가는 사람이 이긴다.

예를 들어, 4개의 공을 먼저 가져는 게임이라고 하자. A가 처음에 가져갈 수 있는 공의 개수는 1개 이상 3개 이하이다. 각각의 경우에 두 사람이 최선을 다한다면 다음과 같은 결과가 된다.

(1) A가 공을 1개 가져가면, B는 2개 이하의 공을 가져갈 수 있다. B가 공 1개를 가져가는 경우와 공 2개를 가져가는 경우 모두에 대해 A가 나머지를 모두 가져 갈 수 있으므로 A가 이긴다. (2) A가 공 두 개를 가져가면 B가 남은 두 개의 공을 가져가 B가 이긴다. (3) A가 공 3개를 가져가면 B가 남은 공을 가져가 B가 이긴다.

위의 경우를 보면 공 4개를 먼저 가져가기의 경우에는 A가 공 1개를 가져가면 다음에 B가 공을 몇 개 가져가더라도 A가 이길 수 있는 방법이 있다는 것을 알 수 있다. 한편, 공 2개를 먼저 가져가는 경우에는 A는 공을 1개 가져갈 수밖에 없으므로 B가 항상 이긴다. 문제는 먼저 공의 수가 주어졌을 때 A가 항상 이길 수 있는 방법이 있느냐하는 것이다.