跳舞问题

dunwan2tellu

一群男女参加一个舞会，但是没有任何一个男生和每一个女生跳过舞，而且每一个女生至少和一个男生跳过舞。
证明一定有 2 男 2 女 ， b , b' 和 g , g' 使到 b 和 g 跳过舞 ， b' 和 g' 跳过舞 ， 但是 b 和 g' 及 b' 和 g 没有跳过舞

晨天

没有任何一个男生和每一个女生跳过舞
这里有两个女生， 所以那男的可能和一个女生跳或没跳

每一个女生至少和一个男生跳过舞。
这里有两个男生， 所以那女的可能和一个男生跳或和两个男生跳

如此， 只能一个男和一个女跳

if  b , b' 和 g , g' 使到 b 和 g 跳过舞 ， b' 和 g' 跳过舞 ，
so  b 和 g' 及 b' 和 g 没有跳过舞

jinqwem

那是在舞会人数只有两男两女情况下成立,
如果推广到N男N女呢?

flash

原帖由 dunwan2tellu 于 7-4-2007 03:53 PM 发表
一群男女参加一个舞会，但是没有任何一个男生和每一个女生跳过舞，而且每一个女生至少和一个男生跳过舞。
证明一定有 2 男 2 女 ， b , b' 和 g , g' 使到 b 和 g 跳过舞 ， b' 和 g' 跳过舞 ， 但是 b 和 g'  ...

假设有 n 个女生参加舞会，每位都给个号码分别是 f(1), f(2),...f(n).

由于每一个女生至少和一个男生跳过舞，而没有任何一个男生和每一个女生跳过舞，那至少有两位男生跳舞。假设男生 M(x)和 f(1), f(2),...f(k)跳过舞 (k < n);称 f(1), f(2),...f(k) 为女(1), f(k+1), f(k+2),...f(n)为女(2).

如此一来，就必须有另一个男生称为 M(y)和女(2) 的至少其中一人跳舞。这可以出现 4 个情况：

情况 1：
M(y) 和女(2)的至少其中一人跳舞，假设 f(n)，没有和女(1)任何人跳舞。如此一来将会

M(x) -- f(k), M(y) -- f(n); M(x) -/- f(n), M(y) -/- f(k)

-- (跳舞), -/-(没跳舞)

情况 2：
M(y) 和女(2)的至少其中一人跳舞，假设 f(n)，和部分女(1)的人跳舞，假设没和 f(k)跳舞。如此一来将会和情况 1一样。

情况 3：
M(y) 和部分女(2)跳舞，假设 f(n)跳舞没和 f(k+1)跳舞，以及全部女(1)的人跳舞。如此一来，就必须有另一个男生称为 M(z)和女(2) 的至少其中一人跳舞，这将会出现 2 个情况：

情况 3(1):
M(z) 和全部女(2)跳舞，和部分女(1)的人跳舞，假设没和 f(k)跳舞。

M(x) -- f(k), M(z) -- f(k+1); M(x) -/- f(k+1), M(z) -/- f(k)

情况 3(2):
M(z) 和部分女(2)跳舞，假设没和 f(n)跳舞 和f(k+1)跳舞，和全部女(1)的人跳舞。

M(y) -- f(n), M(z) -- f(k+1); M(z) -/- f(n), M(y) -/- f(k+1)

呼，好长，希望大家看得明白。。。。

[ 本帖最后由 flash 于 12-4-2007 09:59 PM 编辑 ]

dunwan2tellu

谢谢 flash 精彩的解答

我的解法如下

设 M(1) 为和最多女伴跳舞的男生。

因此必定存在一个女生 F(2) ，而 F(2) 不曾和 M(1) 跳过舞 。（因为没有任何一个男生和每一个女生跳过舞 ）

而且必定存在一个男生 M(2) ,使到 F(2) 和 M(2) 跳过舞 （因为每一个女生至少和一个男生跳过舞 ）

如果 所有与 M(1) 跳过舞的女生都与 M(2) 跳过舞，那么 M(2) 就会比 M(1) 多女伴 (因为 M(2) 和 F(2) 跳过舞，F(2) 却没有和 M(1) 跳过舞 ) , 这么一来 M(2) 就是最多女伴的男生，矛盾。

因此必定存在一个女生 F(1) 使到 F(1) 和 M(1) 跳舞 ， 但是却不曾和 M(2) 跳过舞。
这四个 M(1),M(2),F(1),F(2) 就是我们要找的人。

证毕

flash

你的解答更精彩。。。。 简短而击中要点。。。。