平面上有 2N 个点，其中恰有 N 个红点， N 个蓝点

野菜花 · 发表于 2005-4-8 01:57:35

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

乱弹 · 发表于 2005-4-8 02:18:05

我贴到WXC 去吧, 好不好？

fzy · 发表于 2005-4-8 02:18:32

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:14

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

野菜花 · 发表于 2005-4-8 03:00:34

Great!

It is different from the proof I know.

乱弹 · 发表于 2005-4-8 07:35:52

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

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

野菜花 · 发表于 2005-4-8 08:09:51

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

能否解释一下? Thanks

乱弹 · 发表于 2005-4-8 08:19:33

呵呵，错了。

fzy · 发表于 2005-4-8 19:16:05

Can I see your proof?

野菜花 · 发表于 2005-4-8 21:19:17

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:21

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

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

动态微博

平面上有 2N 个点，其中恰有 N 个红点， N 个蓝点

好题。不过在这儿出过的。[@};-]

回复：平面上有 2N 个点，其中恰有 N 个红点， N 个蓝点

回复：好题。不过在这儿出过的。[@};-]

Great![@};-]It is different from the proof I know.

我知道的一个解答。跟野菜花的大同小异

回复：我知道的一个解答。跟野菜花的大同小异

呵呵，错了。

Can I see your proof? [:D)]

回复：Can I see your proof? [:D)]

nice proof

动态微博

平 面 上 有 2N 个 点 ， 其 中 恰 有 N 个 红 点 ， N 个 蓝 点

好题。不过在这儿出过的。[@};-]

回复：平 面 上 有 2N 个 点 ， 其 中 恰 有 N 个 红 点 ， N 个 蓝 点

回复：好题。不过在这儿出过的。[@};-]

Great![@};-]It is different from the proof I know.

我知道的一个解答。跟野菜花的大同小异

回复：我知道的一个解答。跟野菜花的大同小异

呵呵，错了。

Can I see your proof? [:D)]

回复：Can I see your proof? [:D)]

nice proof

平面上有 2N 个点，其中恰有 N 个红点， N 个蓝点

回复：平面上有 2N 个点，其中恰有 N 个红点， N 个蓝点