　$x$ または $y$ を $n$ 文字並べる方法であって, 同じ文字が $3$ つ連続しないようなものを考える. さらに末端の $2$ 文字が同じであるものの総数を $a_n$ とおき, そうでないものの総数を $b_n$ とおくと, $a_2=b_2=2$ であり, 整数 $n\geq 3$ に対して以下の漸化式が成立することが容易にわかる.
　　$$a_n=b_{n-1},\ \ b_n=a_{n-1}+b_{n-1}$$
　このとき, 求める確率は $\dfrac{a_{10}+b_{10}}{2^{10}}$ で与えられるから, これは $\dfrac{178}{1024}=\dfrac{89}{512}$ であり, 求める値は $\textbf{601}$ である.\
　ちなみに, より思考を進めれば $c_n=a_n+b_n$ について $c_n=c_{n-1}+c_{n-2}$ が成立することがわかるから, 求値をより容易に行うことが出来る. 特に, $c_n$ は倍増されたFibonacci数列である.
公式解説
https://onlinemathcontest.com/contests/omc021/editorial/132
　直前に出た面と同じ面が出たときは $0$ と書き，違う面が出たときは $1$ と書くことにする．\
 すると，求める確率は $0,1$ をランダムに $9$ つ並べるときに $0$ が隣り合わない確率に対応する．\
 一般に， $0,1$ を計 $n$ 個並べてできる文字列 $2^n$ 通りのうち $0$ が隣り合わないものを $a_n$ 通りとすると， $a_{n+2}=a_{n+1}+a_{n}$ となることが容易にわかるので， $a_1=2,a_2=3$ を加味して $a_n$ は $n+2$ 番目のフィボナッチ数である．\
 以上より求める確率は $\dfrac{a_{9}}{2^9}=\dfrac{89}{512}$ であり，解答すべき数値は $89+512=\textbf{601}$
答えにフィボナッチ数が現れることの直接的な説明
https://onlinemathcontest.com/contests/omc021/editorial/132/117
　表と裏が等確率に出るコインを $10$ 回投げ, 一度も表または裏が $3$ 回以上連続して出ない確率を求めてください.\
　ただし, 答えは最大公約数が $1$ である正整数 $a,b$ を用いて $\displaystyle\frac{a}{b}$ と表されるので, $a+b$ を解答してください.