RSS Feed

콩 나누기

Problem 334

출제 일시 : 2021-06-07 00:06:42

플라톤의 천국에는 무한히 많은 수의 그릇이 한 줄로 놓여 있습니다.
각각의 그릇은 비어 있거나 유한 개의 콩을 담고 있습니다.
한 아이가 단 한가지 종류의 이동만 허용되는 게임을 합니다:
한 그릇에서 두 개의 콩을 꺼내서 인접한 두 그릇에 각각 하나씩 옮겨놓는 이동이 그것입니다.

예를 들어, 인접한 두 그릇에 각각 2개, 3개의 콩이 담겨있고 다른 모든 그릇이 비어있다고 하면 다음 8번의 움직임으로 게임이 끝납니다:

p334_beans.gif

다음 수열은 각 그릇이 담고 있는 콩의 개수 $b_i$를 정의합니다:

$\def\htmltext#1{\style{font-family:inherit;}{\text{#1}}}$ $ \begin{align} \qquad t_0 &= 123456,\cr \qquad t_i &= \cases{ \;\;\frac{t_{i-1}}{2},&$\htmltext{만일 }t_{i-1}\htmltext{이 짝수일 때}$\cr \left\lfloor\frac{t_{i-1}}{2}\right\rfloor\oplus 926252,&$\htmltext{만일 }t_{i-1}\htmltext{이 홀수일 때}$\cr}\cr &\qquad\htmltext{여기서 }\lfloor x\rfloor\htmltext{는 절사 함수 입니다 }\cr &\qquad\!\htmltext{그리고 }\oplus\htmltext{는 배타적 논리합 XOR 연산자 입니다.}\cr \qquad b_i &= (t_i\bmod2^{11}) + 1.\cr \end{align} $

수열 $b_i$의 첫 두 항은 $b_1 = 289$과 $b_2 = 145$ 입니다.
만일 두 인접한 그릇에 $b_1$과 $b_2$개의 콩이 담겨 있다면, 게임을 끝내기 위해서 $3419100$번의 이동이 필요합니다.

이제 $1500$개의 인접한 그릇에 각각 $b_1, b_2, \ldots, b_{1500}$개의 콩이 담겨 있고, 다른 모든 그릇은 비었다고 합시다.
게임을 끝내기 위해서 얼마나 많은 이동이 필요한지 구하세요.


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