　各整数 $i = 1, 2, \ldots, 14$ に対して，人 $i$ と 人 $i + 1$ の間にそれぞれ赤い糸，青い糸，糸なしのいずれかを割り当てる方法を考える．ここから，人 $i$ と 人 $j$，人 $j$ と 人 $k$ の間がそれぞれ同じ色の糸で結ばれているような組 $i\lt j\lt k$ が存在する限り，これらを取り除いて人 $i$ と人 $k$ の間をその色の糸で結ぶことを繰り返すと，最終的な状態は操作の方法によらず，かつ条件をみたす状態との間に一対一の対応が得られることがわかる．以上より，求める場合の数は $3^{14} = \mathbf{4782969}$ 通りである．
公式解説
https://onlinemathcontest.com/contests/omc130/editorial/5345
　$15$ 人の人 $1, 2, \ldots, 15$ に対し，以下の一連の操作を $0$ 回以上繰り返します．

- いずれの色の糸でも結ばれていない，相異なる $2$ 人の組を選ぶ．
- $2$ 人の間を $1$ 本の赤い糸または $1$ 本の青い糸で結ぶ．

このとき，最終的な状態としてありうるものであって，以下の条件をすべてみたすものの個数を求めてください．

- どの人についても，その人と赤い糸で結ばれているような人は高々 $1$ 人である．
- どの人についても，その人と青い糸で結ばれているような人は高々 $1$ 人である．
- $4$ 数 $a\lt b,c\lt d$（ただし $(a,b)\neq(c,d)$）について，人 $a$ が人 $b$ と糸で結ばれており，人 $c$ が人 $d$ と糸で結ばれているとき，$b \leq c$ または $d \leq a$ が成立する．