查看: 1344|回复: 6

[求助]一个简单的问题

杯户中学生

0 主题	0 好友	2 积分

帖子: 153
精华: 0
积分: 2
威望: 0
ＲＰ: 0
金钱: 0 柯币
人气: 0 ℃
注册时间: 2004-3-1

发消息

电梯直达

顶楼

发表于 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。

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

分享到: QQ好友和群 微信

淘帖0 分享0 收藏0 喝彩0 无视0 分享到新浪微博

浪客印钞机你也听见了吗，那神风的清响声？

事务所微信公众号上线，快来关注吧~

使用道具举报

jasonnan

杯户中学生

0 主题	0 好友	1 积分

帖子: 58
精华: 0
积分: 1
威望: 0
ＲＰ: 0
金钱: 0 柯币
人气: 0 ℃
注册时间: 2004-7-23

发消息

沙发

发表于 2004-8-2 01:24:12 |只看该作者

回复：

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

柯南20周年纪念事务所专题站开放

使用道具举报

月夜草馒头

杯户小学生

0 主题	0 好友	0 积分

帖子: 48
精华: 0
积分: 0
威望: 0
ＲＰ: 0
金钱: 0 柯币
人气: 0 ℃
注册时间: 2004-7-17

发消息

板凳

发表于 2004-8-2 01:56:01 |只看该作者

回复：

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

命里有时终需有，命里无时莫强求！

事务所微信公众号上线，快来关注吧~

使用道具举报

flyeyes

杯户中学生

0 主题	0 好友	1 积分

帖子: 70
精华: 0
积分: 1
威望: 0
ＲＰ: 0
金钱: 0 柯币
人气: 0 ℃
注册时间: 2004-7-8

发消息

地板

发表于 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：假设某点是连接点数最多或最少的点是图论中的常用方法。