OMC091(D)

　一般に $2$ 行 $n$ 列の場合を考え，マス目を市松模様に黒と白で塗り分けることを考える．ただし，左上を黒で塗るとする．すると，黒で塗ったマスの矢印は白で塗ったマスを指し，白で塗ったマスの矢印は黒で塗ったマスを指すから，黒で塗ったマスと白で塗ったマスに書き込む矢印についてそれぞれ独立に考えてよい．
　ここで，黒で塗ったマスに矢印を書き込む方法が $a_n$ 通りあるとする．左上のマスに $\downarrow$ を書き込んだとき，残りの書き込み方は $a_{n-1}$ 通りである．左上のマスに $\rightarrow$ を書き込んだとき，その右下のマスは必ず $\leftarrow$ となり，残りの書き込み方は $a_{n-2}$ 通りである．よって，$a_1=1,a_2=2$ とあわせて，$a_{10}=89$ を得る．
　以上より，求める場合の数は $89^2=\textbf{7921}$ 通りである．