三角形三色問題

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

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

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

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

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

 解法3 
重ね合わせの原理による証明で、n個の独立した基本パターンに分解されることを使う。解のフラクタル性とも関係Yutaka Nishiyama, The Three-Color Triangle Problem, International Journal of Pure and Applied Mathematics, Vol.85, No.1, 69-81, 2013.Nishiyama's Triangle。

脚注

Category:離散数学の定理
Category:数学に関する記事