MathLabs

第2题

设 PP 是一个正 20062006 边形。如果 PP 的一条对角线的两个端点将 PP 的边界分成两部分，每部分都由奇数条 PP 的边组成，则称该对角线是好的。PP 的各条边也称为好的。假设用 20032003 条在 PP 内部互不相交的对角线将 PP 剖分成三角形。求在这样的剖分中，具有两条好边的等腰三角形最多可能有多少个。
第 4/5 步：每条好对角线去掉一片非特殊叶子
上一步下一步
通俗地说

删去一条好对角线后，其两侧各有一个叶三角形。由于两个特殊三角形不能共享好边，可以为每条被删好对角线选择一片彼此不同的非特殊叶子。

#{special leaves of F}≤(1003+k)−k=1003\#\{\text{special leaves of }F\}\le(1003+k)-k=1003
详细分析

对每条被删好对角线对应的边，考察删边后两个分量端部的叶子。两端至多一个是特殊三角形，否则两个特殊三角形会共享这条好对角线。从森林外侧向内侧处理被删边，并总选择尚未选择的一端；树结构保证这些选择彼此不同（标准的叶子配对论证）。因此 1003+k1003+k 片叶子中至少有 kk 片非特殊，特殊三角形至多有 10031003 个。