第2問
を正 角形とする。 の対角線は、その両端点が の周をそれぞれ奇数個の の辺からなる二つの部分に分けるとき、良いと呼ぶ。 の辺もまた良いと呼ぶ。 が、 の内部で共有点を持たない 本の対角線によって三角形に分割されているとする。このような配置に現れ得る、二つの良い辺を持つ二等辺三角形の個数の最大値を求めよ。
ざっくり言うと
良い対角線を除くと両側に葉となる三角形が現れる。二つの特別な三角形は良い辺を共有できないので、除いた各対角線に異なる特別でない葉を一つ選べる。
詳しい解説
除いた良い対角線に対応する各辺について、除去後の成分の二つの端の葉を調べる。両端がともに特別になることはない。そうでなければ二つの特別な三角形がその良い対角線を共有するからである。森の外側から内側へ除去辺を処理し、まだ選ばれていない側の端を選ぶと、木構造により選択は相異なる（標準的な葉のペアリング）。したがって 個の葉のうち少なくとも 個は特別でなく、特別な三角形は高々 個である。