2006학년도 10월 고3 전국연합학력평가 수학 영역 가형 25번

오른쪽 그림은 어떤 오락기를 단순화하여 그린 것이다. 이 오락기는 입구에 공을 넣으면 $\mathrm A$, $\mathrm B$, $\mathrm C$, $\mathrm D$ 중 어느 한 곳을 지나면서 그 위치의 꺼져 있는 전등은 켜지고, 켜져 있는 전등은 꺼지도록 되어 있다.

예를 들어 전구가 모두 꺼진 상태에서 공을 두 번 넣어 두 번 모두 $\mathrm A$를 지나면 $\mathrm A$ 위치의 전등은 켜졌다 꺼지고, 각각 $\mathrm A$, $\mathrm B$를 지나면 $\mathrm A$, $\mathrm B$ 두 위치에 있는 전등은 모두 켜지게 된다. 이와 같이 공이 지날 때마다 전등이 켜지거나 꺼지기를 반복하다가 $\mathrm A$, $\mathrm B$, $\mathrm C$, $\mathrm D$ 네 곳 모두 전등이 켜지면 게임은 끝난다.

여섯 번째 공을 넣었을 때 이 게임이 끝나게 될 확률을 $\frac ab$ ($a$, $b$는 서로소인 자연수)라고 하자. 이때, $a+b$의 값을 구하시오. (단, 처음 상태는 전등이 모두 꺼져 있으며, 갈림길에서 양쪽 방향으로 공이 지나갈 확률은 서로 같다.) [4점]