MathLabs

第2問

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

二本の良い辺をもつ三角形は良い対角線を除くと葉になり、良い辺をもたない三角形は三本の非良い対角線との隣接を保つ。次数が 11 と 33 だけの木は (ni+2)/2(n_i+2)/2 個の葉をもつ。

deg⁡F(v)∈{1,3},L(F)=∑i=1k+1ni+22=1003+k\deg_F(v)\in\{1,3\},\qquad L(F)=\sum_{i=1}^{k+1}\frac{n_i+2}{2}=1003+k
詳しい解説

ステップ1より各三角形は良い辺を二本または零本もつ。境界辺はすべて良いので、良い辺をもたない三角形は三本の非良い対角線をもち FF で次数 33、良い辺を二本もつ三角形は非良い辺をちょうど一本もち次数 11 である。k+1k+1 成分の頂点数を n1,…,nk+1n_1,\ldots,n_{k+1} とすれば、第 ii 成分の葉数は (ni+2)/2(n_i+2)/2。∑ni=2004\sum n_i=2004 より、FF の葉の総数は 1003+k1003+k となる。