珍珠湾ART

标题: 平面上有 2N 个点，其中恰有 N 个红点， N 个蓝点 [打印本页]

作者: 野菜花 时间: 2005-4-8 01:57
标题: 平面上有 2N 个点，其中恰有 N 个红点， N 个蓝点

证明可以作出 N 条端点为一个红点一个蓝点的线段，使得这 N 条线段两两不相交。

作者: 乱弹 时间: 2005-4-8 02:18
标题: 好题。不过在这儿出过的。[@};-]

我贴到WXC 去吧, 好不好？

作者: fzy 时间: 2005-4-8 02:18
标题: 回复：平面上有 2N 个点，其中恰有 N 个红点， N 个蓝点

We use induction. Suppose it is true for any number < N.

Pick a point P inside the polygon formed by the points so that no two points in the original sets are colinear with P. Draw a line thru P, and rotate the line, to a place where there are equal numbers of blue and red points on each side of the line. By the inductive assumption we can do it for each side.

作者: 野菜花 时间: 2005-4-8 02:58
标题: 回复：好题。不过在这儿出过的。[@};-]

出过吗？对不起！贴到 WXC， no problem.

作者: 野菜花 时间: 2005-4-8 03:00
标题: Great![@};-]It is different from the proof I know.

Great!

It is different from the proof I know.

作者: 乱弹 时间: 2005-4-8 07:35
标题: 我知道的一个解答。跟野菜花的大同小异

让距离最近的两个红蓝点配成一对，其他点无论怎么连，都不会与他们相交（证明同野菜花的）。可以把他们拿开了。剩下的以此类推。

这题在WXC 贴出后，有人指出在一些退化情形题目是不对的，比如说都在一条直线上，并且红蓝各在一端的时候。不过WXC还没有人正确解答，虽然有一个有正确的思路。

作者: 野菜花 时间: 2005-4-8 08:09
标题: 回复：我知道的一个解答。跟野菜花的大同小异

不太明白为什么"让距离最近的两个红蓝点配成一对，其他点无论怎么连，都不会与他们相交 "

能否解释一下? Thanks

作者: 乱弹 时间: 2005-4-8 08:19
标题: 呵呵，错了。

呵呵，错了。

作者: fzy 时间: 2005-4-8 19:16
标题: Can I see your proof? [:D)]

Can I see your proof?

作者: 野菜花 时间: 2005-4-8 21:19
标题: 回复：Can I see your proof? [:D)]

It is not my idea, I only rewrite it. www.ddhw.com

Since there are finitely many points, there are only finitely many ways to draw N lines such that each line has two ends in different colors.
（转自：顶顶华闻 www.TopChineseNews.com ）
Choose one way so that the sum of the lengths of the N segments is the shortest. We may prove that any pair of these N segments do not intersect.
（转自：顶顶华闻 www.TopChineseNews.com ）
Prove it by contradiction:
Assume that two segments AB,CD intersect(A,C are red, B,D are blue), then easy to see:
AD+BC < AB+CD ( using the fact: 两边之和大于第三边 )
So using AD,BC instead of AB,CD, we get a shorter sum of the lengths, Contradiction.

作者: fzy 时间: 2005-4-8 23:36
标题: nice proof

but no very intuitive. I hate induction, and don't use it unless could not think of another way.

欢迎光临珍珠湾ART (http://art.zhenzhubay.com/)