밤띠 1수능형

하노이의 탑이 완성될 확률

크기가 서로 다른 원판 $2$ 개와 막대 $3$ 개가 있다. 처음에는 한 막대에 큰 원판과 작은 원판이 아래에서부터 차례로 꽂혀 있다. 다음 시행을 $5$ 번 반복한다.

어느 막대의 맨 위에 있는 원판 하나를 다른 막대로 옮기되, 큰 원판을 작은 원판 위에 놓지 않는 모든 이동 방법 중 하나를 임의로 선택하여 옮긴다.

다섯 번째 시행 후 두 원판이 같은 막대에 꽂혀 있을 때, 이 다섯 번의 시행에서 큰 원판을 옮긴 횟수가 $1$ 일 확률은 $\vphantom{\begin{matrix}1\\1\end{matrix}}\dfrac{q}{p}$ 이다. $p+q$ 의 값을 구하시오. (단, $p$ 와 $q$ 는 서로소인 자연수이다.)