多边形划分

乱弹

(贴在WXC乏人问津，呵呵，可能不太有趣。其实不难的。）

难度：++ 到 +++。www.ddhw.com

一个凸 n 边形(n≥3) 可以通过连接一些互不相交的对角线，划分成若干小的多边形。若一个划分里有偶数个小多变形，就叫做偶划分； 否则叫做奇划分。 用 e_n, o_n 分别记凸n边形偶划分和奇划分的个数。显然有 e_3=0, o_3=1, e_4=2, o_4=1, 等等。证明
e_n-o_n=(-1)^n.

www.ddhw.com

 

野 菜 花

用数学归纳法： n=1 显然成立 假设 e(n)-o(n)=(-1)^nwww.ddhw.com 对(n+1) 凸多边形，连接相邻两边的两顶点，得一n多边形和一三角形，www.ddhw.com 所以 n 多边形的偶划分加上这个三角形就是 (n+1) 多边形的奇划分，反之亦然。   e(n)+1=o(n+1) o(n)+1=e(n+1)www.ddhw.com   e(n+1)-o(n+1)=o(n)+1-e(n)-1=o(n)-e(n)= - (e(n)-o(n))= - (-1)^n = (-1)^(n+1) www.ddhw.com

乱弹

我做法差不多，但把顶点编上号后细致讨论了。最关键的是其中的奇偶互变。 www.ddhw.com

寒潭清

  谢谢乱弹帖来,让我可以多学习一点

fzy

要考虑这个划出去的顶点有没有对角线。你的公式到 n = 5 就不对了。大致算了一下，应该是   o_n = e_(n-1) + (o_3 + e_3)*(o_(n-2) + e_(n-2)) + (o_4 + e_4)*(o_(n-3) + e_(n-3)) + ... + (o_(n-2) + e_(n-2))*(o_3 + e_3) + （o_(n-1) + e_(n-1))   e_n = o_(n-1) + (o_3 + e_3)*(o_(n-2) + e_(n-2)) + (o_4 + e_4)*(o_(n-3) + e_(n-3)) + ... + (o_(n-2) + e_(n-2))*(o_3 + e_3) + （o_(n-1) + e_(n-1)) www.ddhw.com

乱弹

不过也许需要详细讨论。我中间有相互抵消，然后得出 e_n-o_n=-(e_(n-1)-o_(n-1)). www.ddhw.com

乱弹

  清MM客气。

fzy

  思路大家是一样的。但真算起来还是挺麻烦的

乱弹

  是呀。所以感兴趣的人少。

野 菜 花

  乱弹，互不相交的对角线是指顶点也不能相交吗？题目又理解错啦

fzy

Got this proof last night in bed.  www.ddhw.com Let the vertices of the n-gon be v1, v2, ..., vn. Suppose the first diagonal from v1 is to vk, where 3 <= k <= n (= n means no diagonal from v1). If k > 3, then the diagonal from v2 to vk can be turned on or off to change the parity of the dissection. So there are exactly the same number of odd and even dissections like these. The only situation left is when k = 3. This is reduced to the case 野菜花 considered. So we have these relations:   o_n = e_(n-1) + some number e_n = o_(n-1) + the same number   and o_n - e_n = e_(n-1) - o(n-1)  www.ddhw.com

乱弹

原文是 "nonintersecting diagonals". www.ddhw.com

乱弹

  

野 菜 花

  那么划分的个数是指分成多边形的个数还是有几个不同的分法？

乱弹

  划分的个数是指有几个不同的分法

乱弹

  怪我没说清楚。 在 n=3, 4 时两种看法没有区别的样子，容易混淆

野 菜 花

对呀，照我的理解，题目就太容易了，怎么可能是++ 到+++的题目呢？www.ddhw.com