[求助]一个简单的问题

hope7 · 发表于 2004-8-1 23:34:44

这是我弟的奥数题
说有AB两国开会，A国派了a名代表，B国派了b名代表，假设所有的B国代表都至
少认识一个A国代表，而所有的A国代表都不全认识B国代表，求证：
能找到a1，a2，b1，b2四个代表，使得a1认识b1，a2认识b2，且a1不认识b2,
a2不认识b1。

我知道这题很简单，好象挺明显的，但是我不知道怎么表述才好。

jasonnan · 发表于 2004-8-2 01:24:12

奥数。。。新一代的声音。。。

月夜草馒头 · 发表于 2004-8-2 01:56:01

只可意会不可言传。。。。。
证明题我最怕！

flyeyes · 发表于 2004-8-2 07:52:40

这道题目属于高中数学竞赛中的图论

证明：将各国的代表看作点，认识的人之间用线相连，不认识的不连。
   设A1为A国代表中认识的人最多的人
   因为“所有的A国代表都不全认识B国代表”
   所以，B国代表中一定有一个人是A1不认识的，记为B2
   因为“所有的B国代表都至少认识一个A国代表”
   所以，B2至少认识一个人，记为A2
   只需再证明：A1认识的人中至少有一个是A2不认识的，记这个人为B1。
   那么A1、A2、B1、B2这四个人满足题意。

   用反证法，如果A2认识A1认识的所有人，那么A2比A1至少多认识一个人（即B2），这与“A1为A国代表中认识的人最多的人”这一假设矛盾，所以A1认识的人中至少有一个是A2不认识的，证明完毕。（看时最好参照下图，有些点未画出）

PS：假设某点是连接点数最多或最少的点是图论中的常用方法。

hope7 · 发表于 2004-8-2 10:49:10

我后来想了想用文氏图来解释不知道可不可以

千分之三 · 发表于 2004-8-2 15:23:23

我不知道这样对不对……
把A和B看成两个集合，假设B都只认识一个A，那么可以把B看成自变量
由函数定义可知，一个B只能对应一个A，也就是说a1和a2不可能同时对应一个B，所以命题成立

我觉得我想错了……

kelejiabing · 发表于 2004-8-3 18:36:49

图论。

4楼证得很漂亮

账号		自动登录	找回密码
密码			注册

[求助]一个简单的问题

回复：

回复：

回复：

本帖子中包含更多资源

回复：

回复：

回复：