이제 $k$번 칸에 말을 올리기 위해 필요한 동작의 횟수를 알아봅시다. 편의상 $k$번 칸에 말을 올리는 동작을 k+, 말을 내리는 동작을 k-라고 적습니다.

• 2번: 1+ 2+
• 3번: 1+ 2+ 1- 3+
• 4번: 1+ 2+ 1- 3+ 1+ 2- 1- 4+
• 5번: 1+ 2+ 1- 3+ 1+ 2- 1- 4+ 1+ 2+ 1- 3- 1+ 2- 1- 5+

여기서 $k$번 칸에 말을 올리기 위해 필요한 동작의 수는 $2^{k-1}$임을 유추할 수 있습니다.

좀 더 논리적으로 설명하자면, $k$번 자리에 말을 올리기 위해서는 $k-1$번 자리에 말이 있고 1번부터 $k-2$번 자리에는 말이 없는 상태를 만들어야 합니다. 그리고 나서 $k+1$번 자리에 말을 올리려면 $k-1$번 자리에 있는 말을 제거해야 하는데, 이 과정은 $k-1$번 자리에 말을 올리고 그 앞의 말을 제거하는 과정을 거의 똑같이 반복하면 된다는 사실을 알 수 있습니다. 차이점은 $k-1$번 자리에 말을 올리는 동작이 $k-1$번 말을 제거하는 동작으로 바뀐 것 뿐입니다.

이제 원래의 문제로 돌아와서, 20번 칸에 말을 올리기 위해 필요한 동작의 수는 $2^{19}$이고, 이때 19번 칸에도 말이 있으므로 다음으로 채워야 하는 칸은 18번 칸입니다. 이를 반복하면 답은 $2^{19} + 2^{17} + \cdots + 2^1 = \frac{2(2^{20} - 1)}{3}$이 됩니다.