Problem 519 の変更点

• 追加された行はこの色です。
• 削除された行はこの色です。
• Problem 519 へ行く。

*[[Problem 519:https://projecteuler.net/problem=519]] 「三色コイン噴水」 [#tdcecab2]

隙間なく積まれた1段以上のコインの段があり, その上の段にあるコイン全てが下の段のちょうど2個のコインと接しているようなコインの配置をコインの''噴水''(fountain) と呼ぶ. '''n''' 個のコインによる配置可能な噴水の数を '''f'''('''n''') としよう. 4個のコインの場合3個の可能な配置がある:

#ref(p519_coin_fountain.png,center,nolink)

この結果  '''f'''(4) = 3, そしてさらに '''f'''(10) = 78 となる.

'''n''' 個のコインによる '''f'''('''n''') 個の噴水全てを, 2個の接するコインが同じ色にならないという条件のもとに三色に塗り分ける配色の数を '''T'''('''n''') としよう. 4個のコインからなる3個の妥当な噴水のうちの1つに対する可能な塗り分け方は以下のようになる:

#ref(p519_tricolored_coin_fountain.png,center,nolink)
'''T'''(4) = 48, そして '''T'''(10) = 17760 がすでに与えられている.

'''T'''(20000) の末尾9桁を求めよ.