例217位学者中每人都和其他人通信讨论3个方向的课题 任意两人间只讨论其中一个方向的课题,则其中必可找出3 位学者,他们之间讨论的是同一方向的课题 证明 将每一学者看成一个顶点,作一个17阶完 全图。按讨论课题的方向对边染色,相同方向染 成同一颜色,得到一个17阶3色完全图。 任取一顶点A,与它相关联的有16条边, 其中必能找出6条相同颜色的边,不妨设A与 U1,…,υ6的连线有相同颜色。连接A和6个 顶点υ1,…,υ6如果这6个顶点间也有这种 颜色的边,则已找到讨论同一方向课题的三位学 者;否则,U1,…,υ6及连接它们的边构成 个6阶2色完全图,由例1,必可从中找到一个 3阶单色完全图,即找出三位讨论同一方向课题 的学者
例2 17位学者中每人都和其他人通信讨论3个方向的课题。 任意两人间只讨论其中一个方向的课题，则其中必可找出3 位学者，他们之间讨论的是同一方向的课题。 证明 将每一学者看成一个顶点，作一个 17 阶完 全图。按讨论课题的方向对边染色，相同方向染 成同一颜色，得到一个 17 阶 3 色完全图。 任取一顶点 A，与它相关联的有 16 条边， 其中必能找出 6 条相同颜色的边，不妨设 A 与 υ1，…，υ6的连线有相同颜色。连接 A 和 6 个 顶点υ1，…，υ6。如果这 6 个顶点间也有这种 颜色的边，则已找到讨论同一方向课题的三位学 者；否则，υ1，…，υ6及连接它们的边构成一 个 6 阶 2 色完全图，由例 1，必可从中找到一个 3 阶单色完全图，即找出三位讨论同一方向课题 的学者
>奇偶数校验及相关问题 例3证明、是无理数 证明: 采用同样方法可以证明:若m是大 于1的素数,n是大于1的整数, 则m必为无理数。 即 2 p1q
➢ 奇偶数校验及相关问题 q p 2 = 证明： 采用反证法，设 ，其中p、q互素，则有 p 2=2q 2 。因为2|p2 ，故2|p。记p=2p1，可得4p1 2=2q 2 ，即 2p1 2=q2 ，故又有2|q，与p、q 互素矛盾。 例3 证明 2 是无理数。 同样方法可以证明：若m是大 于1的素数，n是大于1的整数， 则 必为无理数。 n m
例4拟用40块方形瓷砖铺设如下图所示的地面,但商店只 有长方形瓷砖,其大小为方形的两块。问购买20块长方形瓷 砖后,是否可能不裁开而直接铺好地面? 解将图10a)(b黑白相间染色。 显然,如长方形瓷砖不裁开,只能用来复盖相 邻的两格,故复盖的两格必为一白一黑 下图a)中共有21个黑格和19个白格,故不可能 直接铺好,下图(b中黑白格各为20个,大家很 容易找到直接铺设的方法。 袭 图(b)
例4 拟用40块方形瓷砖铺设如下图所示的地面，但商店只 有长方形瓷砖，其大小为方形的两块。问购买20块长方形瓷 砖后，是否可能不裁开而直接铺好地面？ 解 将图11.4中的(a) (b)黑白相间染色。 显然，如长方形瓷砖不裁开，只能用来复盖相 邻的两格，故复盖的两格必为一白一黑。 下图(a)中共有21个黑格和19个白格，故不可能 直接铺好，下图(b)中黑白格各为20个，大家很 容易找到直接铺设的方法。 图(a) 图(b)
例5设一块mxn的棋盘被若干个形如□的板块恰好盖 满,试证明mxn必能被8整除。 证明: 显然有4mxn,故m、n中至少有一个为偶数,不妨 设n为偶数,将棋盘按列黑白相间染色,如下图(a) 所示,由于n为偶数,黑、白列的数目相同,故黑白 格数相同,设各为2k个。 图(a)
例5 设一块m×n的棋盘被若干个形如 的板块恰好盖 满，试证明m×n必能被8整除。 证明: 显然有4|m×n，故m、n中至少有一个为偶数，不妨 设n为偶数，将棋盘按列黑白相间染色，如下图 (a ) 所示，由于n为偶数，黑、白列的数目相同，故黑白 格数相同，设各为2k个。 图(a)
板块可以有许多种拼凑法,但容易看出,每一板块放 置的方向(称之为定向)只有八种可能的选择,如下 图(b)所示。 容易看出,不论按什么方向放置板块,每一板块均盖住 奇数个黑格(1格或3格),故盖住棋盘的板块必有偶数 个,从而,mxn的棋盘必能被8整除。 图(a) 图(b)
板块可以有许多种拼凑法，但容易看出，每一板块放 置的方向（称之为定向）只有八种可能的选择，如下 图(b)所示。 图(b) 容易看出，不论按什么方向放置板块，每一板块均盖住 奇数个黑格（1格或3格），故盖住棋盘的板块必有偶数 个，从而，m×n的棋盘必能被8整除。 图(a)