constant 邀请了脑坛所有能去的人到他家作客，他很好客，准备了许多菜，点心和酒。
只有
9人能喝酒，其中，任三人中至少有两人喝了同一种酒，每人最多喝了三种酒。证明至少有三人喝了同一种酒。
我最少要准备多少种酒？最多多少？(别想时间太长，超过一分钟肯定错。) |
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? |
准备给几个 MM买花，怎么人都不见了呢？清儿要忙到一月中, 早打过招呼, 可是Jenny 约一个多月前说再忙一两星期就可以彻底轻松了，怎么也不翼而飞了? |
假设没有三人喝同一种酒。这个问题变成一个图，每人是一个顶点，二人同喝的酒是一条边。每个顶点最多有三条边，任意三个顶点至少有一条边。这样的图最多有8个顶点：两个不相交的4阶完全图。 |
我是要等人证明了我的题目，再来答你的。 你最少准备 3种酒(想了不到一分钟)最多 20种酒(想了超过一分钟，一定错)设有两人A，B喝了6种酒，另外7人，每个人最多另开两瓶新酒，这样最多6+14=20 事实上20瓶可以达到： 除了B以外另8个人都喝了1号酒： A：1，2，3 B：4，5，6 C：1，7，8 D：1，9，10 E：1，11，12 F：1，13，14 G：1，15，16 H：1，17，18 I：1，19，20 |
现在也没时间算到底是多少。| 欢迎光临 珍珠湾ART (http://zzwav.com/) | Powered by Discuz! X3 |