三角形三色問題

三角形三色問題（さんかくけいさんしょくもんだい、英語: Three-Color Triangle Problem）は、逆三角形に配置されたセルを上から下へある規則に従い3色で塗っていったとき、最下行の色が最上行の両端の色で予想できるかという問題。2012年、イギリスのスティーブ・ハンブル（Steve Humble）によって提唱された。エアハルト・ベーレントとの共著でひとつの解答を示している。また、ニューヨーク・タイムズ紙にこの問題が紹介されている。雑誌『数学セミナー』の「エレガントな解答をもとむ」欄に問2として出題されている。同2013年4月号に解答と講評がある。2色の場合が、Journal of Recreational Mathematics (2011年刊行)のProblems and Conjectures (269-270ページ) に出題されている。

概要

図1．ハンブルの予想

図1のような逆三角形がある。最上行の10個のセルは3つの色（赤，黄，青）でランダムに塗られている。2行目からはつぎの規則で色を塗っていく。

• 上の行の隣り合せる2つの色が同じであるなら，それと同じ色にする。
• 2つの色が異なるなら，どちらとも違う第3の色にする。

このようにして色を下へ下へと塗っていったとき，最下行（三角形の頂点）の色が何色になるかは，最上行の左右両端の色とは異なる色になると予想できるという。図1では最上行の左端は赤で右端は黄であるから規則を適用すると青と予想され、実際に最下行は青になっている。最上行の塗り方は全部で3^10=59049通りあるが、途中の色の生成パターンと関係なく、このような予想方法が成り立つことを証明せよという問題。

このような予想が成り立つ最上行の個数nの一般式を求めさせる問題でもある。

解法

解法1

合同式による証明で、演算式としてc=-(a+b) mod 3 を使う。この場合、反例の証明も必要である。

解法2

二項係数の剰余による証明で、パスカルの三角形の値を mod 3 としたものを使う。代数学ではLucasの定理としても有名。

解法3

重ね合わせの原理による証明で、n個の独立した基本パターンに分解されることを使う。解のフラクタル性とも関係。