[문제적 남자] 2개, 3개, 8개로 나뉜 바둑알 가져오기 게임에서 선공이 반드시 이기는 방법은?

1. Question

2. Approach

비슷한 문제로 1개의 그룹에서 1개 또는 2개 또는 3개의 바둑알을 가져가는 문제가 일반적으로 알려져있다.

그 문제의 변형인데, 이런 식의 문제는 상대에게 가불기를 시전하면 된다.

위의 일반적인 문제는 $3n + 1$개를 남기고 가져가면 되지만, 이 문제는 더 꼬아놔서 여러경우를 찾아가야 한다.

필자가 찾은 규칙은 두 그룹에 1개씩 바둑알을 남기고 가져가는 것이다. 이러면 상대는 어느쪽이든 1개밖에 못가져가고 다음에 내가 가져가면 이길 수 있다.

방송에서도 이 규칙을 찾아서 한알씩 두 무더기 규칙 (한알두무)라고 하더라ㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋ

이 규칙을 반대로 풀면 상대방에게 한알두무를 주면 안된다. 따라서, 내가 바둑알을 남겼을 때 모양이 다음과 같으면 안된다.

• 한 그룹에는 바둑알 1개, 다른 그룹에는 바둑알 2개. (2 : 1 포지션)

이러면 상대는 쉽게 한알두무를 나한테 시전할 수 있다.

이를 막기 위해, 다음과 같은 포지션을 생각해 볼 수 있다.

• 한 그룹에는 바둑알 2개, 다른 그룹도 바둑알 2개 (두알두무)

이러면 상대는 역시 가불기에 빠진다. 1개를 가져가면 내가 한알두무를 시전하고 그렇다고 2개를 가져가면 나도 남은 2개를 가져가서 패배하고 만다.

당연하겠지만 상대가 나에게 두알두무를 시전하는 경우도 있으니 잘 생각해야한다.

• 한 그룹에는 바둑알 2개, 다른 그룹에는 바둑알 3개. (3 : 2 포지션)

그런데, 반대로 생각하면 3 : 2 포지션을 상대에게 강요하면 내가 이길 수 있다는 뜻이다. 하지만 상대에게 3 : 2 포지션을 강요할 방법이 없다. 2 : 3 : 1로 만들어도 상대가 다른 걸 가져갈 수 있기 때문이다.

셋 중 한 그룹이 2개가 최대이므로 이제 그룹을 추가하는 경우를 생각해보자.

• 한 그룹에는 바둑알 2개, 다른 그룹에는 바둑알 3개, 마지막 그룹에 바둑알 1개 (2 : 3 : 1).

이 경우에는, 내가 무조건 승리한다.

• 상대가 1개 짜리 그룹을 가져가면, 3 : 2포지션에 빠져 패배한다.
• 상대가 2개 짜리 그룹에서 1개를 가져가면 (1 : 3 : 1) 내가 3개를 가져가서 한수두무를 시전.
• 상대가 2개 짜리 그룹을 다 가져가면 (3 : 1), 내가 2개를 가져가서 한수두무를 시전.
• 상대가 3개 짜리 그룹에서 1개를 가져가면, 내가 1개를 가져가서 두수두무를 시전.
• 상대가 3개 짜리 그룹에서 2개를 가져가면 (2 : 1 : 1), 내가 2개를 가져가서 한수두무를 시전.
• 상대가 3개 짜리 그룹을 다 가져가면, 2 : 1 포지션에 빠져 패배.

따라서, 처음 시작할 때 8개 그룹에서 7개를 가져가면 된다.