9名数学家,每人至多会3种语言,每3人至少有两人能通话,(1)证明:至少有3人会同一种语言;(2)如果把9名改为8名数学家,(1)中结论还成立吗?
2019-04-27
9名数学家,每人至多会3种语言,每3人至少有两人能通话,
(1)证明:至少有3人会同一种语言;
(2)如果把9名改为8名数学家,(1)中结论还成立吗?
优质解答
证明:(1)给9名数学家分别编为1~9号,
假设没有任意三个人会同一种语言.
令1号,2号,3号之间有2个语言相通的人(不妨令为1,2号)设为语言A,
剩余的1个人(3号)与4号,5号之间有2个语言相通的人(不妨令为3,4号)设为语言B,
剩余的1个人(5号)与6号,7号之间有2个语言相通的人(不妨令为5,6号)设为语言C,
剩余的1个人(7号)与8号,9号之间有2个语言相通的人(不妨令为7,8号)设为语言D,
于是得到四对语言相通的人(1,2),(3,4),(5,6),(7,8),
和另外一个人(9号)对四对语言不通的人.
任取通语言A、B之中的人各一个和对四对语言不通的人组成一组(不妨令为1,3号),
则1,3之间可以通话,且通话的语言不能为A,B,C,D,不妨令为语言E,
任取通语言A、C之中的人各一个和对四对语言不通的人组成一组(不妨令为1,5号),
则1,5之间可以通话,且通话的语言不能为A,B,C,D,E,不妨令为语言F,
任取通语言A、D之中的人各一个和对四对语言不通的人组成一组(不妨令为1,7号),
则1,7之间可以通话,且通话的语言不能为A,B,C,D,E,F,不妨令为语言G,
则1号数学家必须会A,E,E,F四种语言,
与“每人至多会3种语言”矛盾,假设不成立.
故至少有3人会同一种语言.
(2)如果把9名改为8名数学家,则(1)中的另外一个人(9号)对四对语言不通的人不存在.
故此时(1)中结论不成立.
证明:(1)给9名数学家分别编为1~9号,
假设没有任意三个人会同一种语言.
令1号,2号,3号之间有2个语言相通的人(不妨令为1,2号)设为语言A,
剩余的1个人(3号)与4号,5号之间有2个语言相通的人(不妨令为3,4号)设为语言B,
剩余的1个人(5号)与6号,7号之间有2个语言相通的人(不妨令为5,6号)设为语言C,
剩余的1个人(7号)与8号,9号之间有2个语言相通的人(不妨令为7,8号)设为语言D,
于是得到四对语言相通的人(1,2),(3,4),(5,6),(7,8),
和另外一个人(9号)对四对语言不通的人.
任取通语言A、B之中的人各一个和对四对语言不通的人组成一组(不妨令为1,3号),
则1,3之间可以通话,且通话的语言不能为A,B,C,D,不妨令为语言E,
任取通语言A、C之中的人各一个和对四对语言不通的人组成一组(不妨令为1,5号),
则1,5之间可以通话,且通话的语言不能为A,B,C,D,E,不妨令为语言F,
任取通语言A、D之中的人各一个和对四对语言不通的人组成一组(不妨令为1,7号),
则1,7之间可以通话,且通话的语言不能为A,B,C,D,E,F,不妨令为语言G,
则1号数学家必须会A,E,E,F四种语言,
与“每人至多会3种语言”矛盾,假设不成立.
故至少有3人会同一种语言.
(2)如果把9名改为8名数学家,则(1)中的另外一个人(9号)对四对语言不通的人不存在.
故此时(1)中结论不成立.