(贴在WXC乏人问津，呵呵，可能不太有趣。其实不难的。）
难度：++ 到 +++。
一个凸 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.
用数学归纳法： n=1 显然成立 假设 e(n)-o(n)=(-1)^n 对(n+1) 凸多边形，连接相邻两边的两顶点，得一n多边形和一三角形， 所以 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) |
我做法差不多，但把顶点编上号后细致讨论了。最关键的是其中的奇偶互变。 |
要考虑这个划出去的顶点有没有对角线。你的公式到 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)) |
不过也许需要详细讨论。我中间有相互抵消，然后得出 e_n-o_n=-(e_(n-1)-o_(n-1)). |
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) |
原文是 "nonintersecting diagonals". |
对呀，照我的理解，题目就太容易了，怎么可能是++ 到+++的题目呢？ |
| 欢迎光临 珍珠湾ART (http://zzwav.com/) | Powered by Discuz! X3 |