돌 제거 게임
Problem 260
출제 일시 : 2020-11-20 00:10:06, ☕ 14
두 선수가 돌 더미 3개를 가지고 하는 시합입니다.
각 선수 차례마다 돌 더미에서 하나 이상의 돌을 제거합니다. 만일 여러 더미에서 돌을 제거한다면, 각 더미에서 제거하는 돌의 수는 같아야 합니다.
달리 말하면, 선수는 먼저 $N \gt 0$을 선택하고 다음 셋 중 한 방법으로 돌을 제거합니다:
- 한 더미에서 $N$개의 돌을 제거합니다; 아니면
- 두 더미에서 각각 $N$개씩의 돌을 제거합니다(총 $2N$개를 제거합니다); 아니면
- 세 더미에서 각각 $N$개씩의 돌을 제거합니다(총 $3N$개를 제거합니다).
마지막 돌을 제거하는 선수가 승리합니다.
승리하는 구성은 첫 선수가 무조건 이기는 구성입니다.
예를 들어, $(0,0,13)$, $(0,11,11)$, $(5,5,5)$는 첫 선수가 모든 돌을 즉시 제거할 수 있으므로 승리하는 구성입니다.
패배하는 구성은 첫 선수가 어떻게 하더라도 두번째 선수가 무조건 이기는 구성입니다.
예를 들어, $(0,1,2)$와 $(1,3,3)$는 패배하는 구성입니다: 첫 선수가 어떻게 하더라도 두번째 선수에게 승리하는 구성을 남겨 주게 됩니다.
$x_i \le y_i \le z_i \le 100$일 때, 모든 패배하는 구성 $(x_i, y_i, z_i)$ 에 대하여
$\sum (x_i + y_i + z_i) = 173895$입니다.
$x_i \le y_i \le z_i \le 1000$일 때, 모든 패배하는 구성 $(x_i, y_i, z_i)$에 대하여 $\sum (x_i + y_i + z_i)$를 구하세요.