약수 게임

두 사람 A와 B가 다음과 같은 게임을 한다.

처음에 탁자 위에 개의 조약돌이 있다.

A부터 시작해서 번갈아 가면서 게임을 진행한다. 자신의 차례에 탁자 위에 개의 조약돌이 있다면, 이상 이하인 의 약수 를 원하는 대로 골라서, 개의 조약돌을 가져가야 한다. 그러한 약수 가 존재하지 않아서 더 이상 조약돌을 가져갈 수 없는 사람이 진다.

A와 B 모두 항상 자신이 이기기 위해 최선을 다한다.

이상 이하의 모든 자연수 가운데, 위와 같은 게임에서 A가 이기도록 하는 의 개수는?

문제 형식

주관식

출처

• KOI 2023 1차대회 고등부 1교시 12번