　二人が南北の道路を合計で $k$ 回通ったとするとき，明らかに $k$ は偶数である．また，そのうち左側から $2i-1$ 本目と $2i$ 本目の南北の道路を使った人は同じである．南北の道路の使う場所の決め方は ${}\_{10}\mathrm{C}\_{k}$ 通り，左側から $1,3,\ldots,k\/2-1$ 本目の南北の道路を使う人の決め方はそれぞれ $2$ 通りあるから，求める総数は
$$ {}\_{10}\mathrm{C}\_{0}\times 2^0 + {}\_{10}\mathrm{C}\_{2}\times 2^1 + \cdots + {}\_{10}\mathrm{C}\_{8}\times 2^4 + {}\_{10}\mathrm{C}\_{10}\times 2^5 = \bf{3363}.$$
公式解説
https://onlinemathcontest.com/contests/omc181/editorial/3197
　一般に $2\times n$ の長方形で二人が左から右に行く道順の数を $a_n$ とします．すなわち求めたいのは $a_9$ です．\
漸化式を使って解きましょう．

・二人が最初にどちらも右に移動するならば残りの道順は $a_{n-1}$ だけあります．\
・小野寺さんが初手で下に行き， $1\leq k\leq n-1$ 回右に行った後で上に移動すると残りの道順は $a_{n-k-1}$ だけあります．( $a_0=1$ とします)\
・芹沢さんが初手で上に行き， $1\leq k\leq n-1$ 回右に行った後で上に移動すると残りの道順は $a_{n-k-1}$ だけあります．\
・小野寺さんが初手で下に行き， $n$ 回右に行った後で上に移動すると残りの道順は $1$ だけあります．\
・芹沢さんが初手で上に行き， $n$ 回右に行った後で上に移動すると残りの道順は $1$ だけあります．

したがって次の漸化式が得られます．
$$a_n=a_{n-1}+2(a_{n-2}+\cdots+a_0)+2$$
これと $n$ を $n+1$ とした式の差をとって次を得ます．
$$a_{n+1}=2a_n+a_{n-1}　(n=2,3,...)$$ 
 $a_1=3,a_2=7$ なのでこの漸化式を用いて $a_3=17,a_4=41,a_5=99,a_6=239,a_7=577,a_8=1393,a_9=\mathbf{3363}$ を得ます．
ユーザー解説
https://onlinemathcontest.com/contests/omc181/editorial/3197/300
東西の道をそれぞれ北から北道，中央道，南道とする．\
南北の道が $n+1$ 本あるとき，小野田と芹沢が東西の道のうち最後に通るのがそれぞれ北道と南道である場合の数を $a_n$ ，北道と中央道である場合の数を $b_n$ ，中央道と南道である場合の数を $c_n$ とする．\
対称性より $b_n=c_n$ である．\
小野田と芹沢は同じ南北の道を通れないので，
$$a_{n+1}=a_n+b_n+c_n=a_n+2b_n$$ $$b_{n+1}=a_n+b_n$$ $$a_1=1，b_1=1$$
求めたいのは $a_9+2b_9$ なのであとは頑張りましょう．
ユーザー解説
https://onlinemathcontest.com/contests/omc181/editorial/3197/303
　中段にある東西方向の $9$ 本の道に対し，小野田が通る道を $x$ とし，芹沢が通る道を $y$ とし，二人とも通らない道を $z$ とすると，$x$ と $y$ は隣り合ってはならず，逆に，中段にある東西方向の $9$ 本の道に対し，$x$ と $y$ が隣り合わないように $x,y,z$ を振り分けることで，二人の経路がただ一つに定まる．  
よって，問題は「 $x,y,z$ を計 $n$ 個並べる方法のうち $x$ と $y$ が隣り合わないようなものの総数を $a_n$ とするとき，$a_9$ を求めよ」という問題に帰着された．  
 条件を満たす $n+2$ 文字の文字列において，$z$ から始まるものは $a_{n+1}$ 通りあり，$x,z$ から始まるものは $a_n$ 通りあり，$x,x$ か $y,y$ か $y,z$ から始まるものは(条件を満たす $n+1$ 文字の文字列において $x$ からはじまるものの左に $x$ をおくか $y$ からはじまるものの左に $y$ をおくか $z$ からはじまるものの左に $y$ をおく操作を考えて) $a_{n+1}$ 通り．  
以上より，$a_{n+2}=2a_{n+1}+a_n$ となり，あとは natu_math さんのユーザー解説と同様にして $a_9=\textbf{3363}$ が得られる．
ユーザー解説
https://onlinemathcontest.com/contests/omc181/editorial/3197/304
　以下のような，東西に $3$ 本，南北に $10$ 本の道路が走っている町があり，小野田と芹沢の二人はこの町に住んでいます．小野田は地点 $A$ に住んでおり，地点 $A^{\prime}$ にある学校に通っています．芹沢は地点 $B$ に住んでおり，地点 $B^{\prime}$ にある学校に通っています．二人はいつもそれぞれ同じ通学路を使っています．その際， 一度来た道を引き返したり，同じ道を二度通ることはありません．\
　小野田は芹沢をライバル視しており，通学中に会いたくありません．二人の通学路の組み合わせであって，共有点が存在しないものは何通りありますか？
![figure 1](\/images\/OANu7xqVfimPlbalJTHSsuw4T0pBZhh3kDGIkc3o)