多边形划分

乱弹 · 发表于 2005-10-7 00:38:02

(贴在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.

野菜花 · 发表于 2005-10-7 02:25:33

用数学归纳法：

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)

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)

乱弹 · 发表于 2005-10-7 03:05:36

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

寒潭清 · 发表于 2005-10-7 04:10:14

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

fzy · 发表于 2005-10-7 04:49:27

要考虑这个划出去的顶点有没有对角线。你的公式到 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))

乱弹 · 发表于 2005-10-7 05:37:10

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

乱弹 · 发表于 2005-10-7 05:46:52

清MM客气。

fzy · 发表于 2005-10-7 05:53:45

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

乱弹 · 发表于 2005-10-7 06:06:07

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

野菜花 · 发表于 2005-10-7 07:36:32

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

fzy · 发表于 2005-10-7 18:04:05

Got this proof last night in bed.

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)

乱弹 · 发表于 2005-10-7 18:16:19

原文是 "nonintersecting diagonals".

乱弹 · 发表于 2005-10-7 18:17:48

野菜花 · 发表于 2005-10-7 18:42:02

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

乱弹 · 发表于 2005-10-7 19:19:11

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

乱弹 · 发表于 2005-10-7 19:21:02

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

野菜花 · 发表于 2005-10-7 19:51:36

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

		自动登录	找回密码
密码			立即注册

动态微博

多边形划分

回复：多边形划分

[@};-][@};-]

谢谢乱弹帖来,让我可以多学习一点[@};-][@};-][>:D<]

好像不对

这是AMM八月份一道题目。野菜花思路是对的。

清MM客气。[@};-][@};-]

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

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

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

A proof

我觉得在顶点是可以相交的，比如五边形内两条对角线

[:D)][:D)]

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

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

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

我自己题目没搞清楚就糊里糊涂地往枪口上撞，看了Fzy 的更正更是一头雾水[:((][:((]

动态微博

多边形划分

回复：多边形划分

[@};-][@};-]

谢谢乱弹帖来,让我可以多学习一点[@};-][@};-][>:D<]

好像不对

这是AMM八月份一道题目。野菜花思路是对的。

清MM客气。[@};-][@};-]

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

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

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

A proof

我觉得在顶点是可以相交的，比如五边形内两条对角线

[:D)][:D)]

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

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

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

我自己题目没搞清楚就糊里糊涂地往枪口上撞，看了Fzy 的更正更是一头雾水[:((][:((]

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