MathLabs

第2問

PP を正 20062006 角形とする。PP の対角線は、その両端点が PP の周をそれぞれ奇数個の PP の辺からなる二つの部分に分けるとき、良いと呼ぶ。PP の辺もまた良いと呼ぶ。PP が、PP の内部で共有点を持たない 20032003 本の対角線によって三角形に分割されているとする。このような配置に現れ得る、二つの良い辺を持つ二等辺三角形の個数の最大値を求めよ。
ステップ 5/5: 境界辺を対にして上界を達成する
前のステップ次のステップ
ざっくり言うと

隣接する境界辺の各組から二等辺三角形を一つ切り出し、残りの多角形を任意に三角形分割する。

△P2i−1P2iP2i+1 (i=1,…,1003)⟹1003 special triangles\triangle P_{2i-1}P_{2i}P_{2i+1}\ (i=1,\ldots,1003)\quad\Longrightarrow\quad1003\text{ special triangles}
詳しい解説

多角形の頂点を巡回的に P1,…,P2006P_1,\ldots,P_{2006} と名付け、P1P3,P3P5,…,P2005P1P_1P_3,P_3P_5,\ldots,P_{2005}P_1 を引く。これら 10031003 本の交差しない対角線は、二本の多角形の辺、従って二本の良い辺をもつ 10031003 個の三角形 P2i−1P2iP2i+1P_{2i-1}P_{2i}P_{2i+1} を切り出す。残った 10031003 角形を 10001000 本の対角線で三角形分割すれば、10031003 個の特別な三角形をもつ分割となり、上界が達成される。