RSS Feed

돌 제거 게임

Problem 260

출제 일시 : 2020-11-20 00:10:06

두 선수가 돌 더미 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)$를 구하세요.


로그인 하시면 답안을 제출할 수 있고,
정답을 맞히신 분들은 댓글을 달거나 볼 수 있습니다.