脑坛第三次聚餐(当然不能拉下清MM，否则她要和constant 急)[;)]

野菜花 · 发表于 2005-12-20 22:44:24

constant 邀请了脑坛所有能去的人到他家作客，他很好客，准备了许多菜，点心和酒。

只有

9人能喝酒，其中，任三人中至少有两人喝了同一种酒，每人最多喝了三种酒。

证明至少有三人喝了同一种酒。

constant · 发表于 2005-12-20 23:07:40

大家喝呀！喝醉了少吃菜！

constant · 发表于 2005-12-21 01:22:08

我最少要准备多少种酒？最多多少？(别想时间太长，超过一分钟肯定错。)

寒潭清 · 发表于 2005-12-21 12:11:37

好姐姐

QL · 发表于 2005-12-21 18:09:13

Each person can be considered as a set, with at most 3 elements (wines)

Prove by contradiction:

Assume no three people drink the same wine, i.e., for any three out of the total nine sets, their intersection is empty.

First, we can prove that there exist two disjoint sets. Consider any four sets A,B,C,D,E, given the assumption that no three sets have non empty intersection, A need to have at least 4 elements in order to have non-empty intersection with each of B,C,D,E.

Now, suppose A n B = empty, put together, A u B has at most 6 elements. Now, added in another set C, then either A n C or B n C is non empty, i.e. (A u B) n C is non empty. Now, consider yet another set D, (A u B) n D is non empty, but by assumption, ((A u B) n C) n ((Au B) n D) is empty, in anothe word, each added set 'will take away some different wines' from A u B, and this kind of robbery can not go on beyond 6 times, but there are 7 robbers around, impossible.

Can some one give an example that the conclusion will not hold for 8 people?

野菜花 · 发表于 2005-12-21 18:15:38

准备给几个

MM买花，怎么人都不见了呢？清儿要忙到一月中, 早打过招呼, 可是Jenny 约一个多月前说再忙一两星期就可以彻底轻松了，怎么也不翼而飞了?

constant · 发表于 2005-12-21 18:21:09

假设没有三人喝同一种酒。这个问题变成一个图，每人是一个顶点，二人同喝的酒是一条边。每个顶点最多有三条边，任意三个顶点至少有一条边。这样的图最多有8个顶点：两个不相交的4阶完全图。

野菜花 · 发表于 2005-12-21 18:36:13

Perfect!

野菜花 · 发表于 2005-12-21 18:39:27

很妙！也给出了QL问的例子。

野菜花 · 发表于 2005-12-21 18:58:07

我是要等人证明了我的题目，再来答你的。

你最少准备

3种酒(想了不到一分钟)

最多

20种酒(想了超过一分钟，一定错)

设有两人A，B喝了6种酒，另外7人，每个人最多另开两瓶新酒，这样最多6+14=20

事实上20瓶可以达到：www.ddhw.com

除了B以外另8个人都喝了1号酒：

A：1，2，3

B：4，5，6www.ddhw.com

C：1，7，8

D：1，9，10

E：1，11，12www.ddhw.com

F：1，13，14

G：1，15，16

H：1，17，18

I：1，19，20

constant · 发表于 2005-12-21 19:16:03

想的太多了，都不对。

野菜花 · 发表于 2005-12-21 19:22:43

你的意思是，0，无穷大？

constant · 发表于 2005-12-21 19:24:59

1 and 26

野菜花 · 发表于 2005-12-21 19:27:51

26能达到吗？

野菜花 · 发表于 2005-12-21 19:45:06

如果没开瓶的也算，那你准备无论多少都可以呀!

constant · 发表于 2005-12-22 03:20:57

不能，算错了。

现在也没时间算到底是多少。

Do you have proof · 发表于 2005-12-22 04:17:43

Do you have proof

野菜花 · 发表于 2005-12-22 07:20:37

我算的20为什么不对呢？

constant · 发表于 2005-12-22 17:55:36

20 is correct.

野菜花 · 发表于 2005-12-22 19:41:58

Thanks!

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

动态微博

脑坛第三次聚餐(当然不能拉下清MM，否则她要和constant 急)[;)]

大家喝呀！喝醉了少吃菜！[:E][:D)][:))]

再加一问

好姐姐[:-][:-]

回复：脑坛第三次聚餐(当然不能拉下清MM，否则她要和constant 急)[;)]

班主的话我可牢记心中。看到清儿感到好亲切！[:-*][>:D<]现在我钱也赚了一点，节日也要到了，

回复：脑坛第三次聚餐(当然不能拉下清MM，否则她要和constant 急)[;)]

Perfect! [@};-][@};-]

很妙！也给出了QL问的例子。[@};-][@};-][:)]

回复：再加一问

想的太多了，都不对。[:E][:E][:E]

你的意思是，0，无穷大？

1 and 26

26能达到吗？

如果没开瓶的也算，那你准备无论多少都可以呀! [;)]

不能，算错了。[:>] 现在也没时间算到底是多少。

Do you have proof

我算的20为什么不对呢？

20 is correct.

Thanks!

动态微博

脑坛第三次聚餐(当然不能拉下清MM，否则她要和constant 急)[;)]

大家喝呀！喝醉了少吃菜！[:E][:D)][:))]

再加一问

好姐姐[:-*][:-*]

回复：脑坛第三次聚餐(当然不能拉下清MM，否则她要和constant 急)[;)]

班主的话我可牢记心中。看到清儿感到好亲切！[:-*][>:D<]现在我钱也赚了一点，节日也要到了，

回复：脑坛第三次聚餐(当然不能拉下清MM，否则她要和constant 急)[;)]

Perfect! [@};-][@};-]

很妙！也给出了QL问的例子。[@};-][@};-][:)]

回复：再加一问

想的太多了，都不对。[:E][:E][:E]

你的意思是，0，无穷大？

1 and 26

26能达到吗？

如果没开瓶的也算，那你准备无论多少都可以呀! [;)]

不能，算错了。[:>] 现在也没时间算到底是多少。

Do you have proof

我算的20为什么不对呢？

20 is correct.

Thanks!

好姐姐[:-][:-]