方針
辺を共有する移動回数を距離とみなし、1個から距離以内にある三角形を数える。任意の有限初期配置は、基準三角形からの最大距離だけ半径をずらした二つの領域ではさむ。
解答
二つの単位正三角形の間の距離を、辺を共有する三角形へ移る最小回数とする。1回の操作は、塗られた集合の距離1以内を新たに塗ることに等しい。
(1)
最初の三角形から距離がちょうどである三角形を、格子の3方向に沿って一周して数えると個である。実際、第1層は3個であり、層を一つ外へ移すたび、三つの方向の各辺列が1個ずつ伸びて合計3個増える。従って(2)
最初に塗られた有限集合をとし、その中の一つをとする。からの各三角形までの距離の最大値をとおく。回後の集合は各を中心とする距離以内の領域の和集合である。だから、中心の距離以内の領域を含む。一方、三角不等式より、その和集合は中心の距離以内の領域に含まれる。よって従ってここで(1)の式から、固定したに対してはさみうちにより、どの有限な初期配置でも極限は存在し、
別解
解法2(各層の増分を数える)
方針
最初の1個から辺を共有する最短回数を距離とし、距離がちょうど の新しい層だけを数える。一般の有限初期配置については、基準三角形から初期集合までの最大距離 を取り、半径 と の一頂点型領域で挟む。
解答
(1)
最初の三角形から、辺を共有する三角形へ移る最小回数を距離とする。 回目に初めて塗られるのは、距離がちょうど の三角形である。
三角格子上でこの第 層を一周すると、3方向の辺列がそれぞれ 個ずつ現れる。従って新しく増える個数を とすればよって(2)
最初に塗られた有限集合を とし、その中の1個を基準三角形 とする。 から の各三角形までの距離の最大値を とする。
だから、 回後の塗られた集合は から距離 以内の領域を含む。一方、初期集合のどの三角形も から距離 以内にあるので、三角不等式により、 回後の集合全体は から距離 以内に含まれる。
従って個数についてである。よって(1)の式から、固定した に対してはさみうちの原理により、どの有限な初期配置についても極限は存在しである。
総評
難度7、計算量4。操作を格子上の距離による膨張と読むことが核心である。有限な初期配置の形を個別分類せず、最大距離だけを使って二つの一頂点型領域ではさむことで、すべての配置を一度に処理した。 2解法の数式と最終結論を相互照合し、原典本文との対応、小問の完答、境界条件、図の読み取りを再確認した。
