Quant Interview - Grid Frog1

개구리가 동시에 점프 할 때 모든 칸에 대해서 개구리 1개만 있을 확률을 구해라

모서리에 있는 개구리는 이런 식으로 점프 가능하다

모서리가 아닌 곳에 있는 개구리는 이런 식으로 점프 가능하다

전체 경우의 수에 대해서 살펴보면 모서리 4개 아닌것 12개 해서 $2^4$ X $3^{12}$ 이다
처음에 문제를 봤을 때 규칙이 있고 어떻게 풀까 고민하다가 중앙을 먼저 봤는데 답이 안 나와서 전체적인 것을 보니 지그재그 형태로 독립적인 것을 발견했다.

만약 1번 개구리가 밑으로 간다면 전체 타일의 n-1개를 세는 것과 같고 개구리가 오른쪽으로 간다면 모든 타일에 개구리가 다 있을려면 10번 개구리가 왼쪽으로 가야함으로 전체 타일의 n-2개를 세는 것과 같다.

점화식을 세워보면 $f_n$ = $f_{(n-1)}$ + $f_{(n-2)}$ 이다.
$f_1$ = 1 , $f_2$ = 2 , $f_3$ = 3 .... $f_8$ = 34 이다

앞서 봤던 아래쪽 지그재그와 위쪽 지그재그가 서로 독립임으로 34 X 34 이고 전체는 $2^4$ X $3^{12}$ 이기 때문에 $17^2\over 2^2 X 3^{12}$ 이다