购买
下载掌阅APP,畅读海量书库
立即打开
畅读海量书库
扫码下载掌阅APP

第26讲
染色问题与染色方法

解答题(每题10分,共100分)

1.在线段AB的两个端点,一个涂红色,一个涂蓝色,在线段中间插入n个分点,在各个分点上随意地涂上红色或蓝色,这样就把原线段分为n+1个不重叠的小线段,这些小线段的两端颜色不同者叫作标准线段。求证:标准线段的个数是奇数.

2.把一个正方体形的房子分割成27个相等的小正方体房间,每相邻(即有公共面)两个房间都有门相通,在中心的那个小正方体房间中有一只甲虫,甲虫能从每个小房间走到与它相邻的小房间中的任何一间去。如果要求甲虫只能走到每个小房间一次,那么甲虫能走遍所有的小房间吗?说明你的理由.

3.4×4的方格表中最多选择几个格子涂黑,使得不存在黑色四角矩形?

4.如图26-1所示,图中的黑点叫作图的顶点,连接2个顶点的线段叫作图的边,有公共顶点的边叫作相邻的边。现给图中每一条边都涂上某一种颜色,试问:至少要几种颜色才能使图中所有相邻的边有不同的颜色?

图26-1

5.某班有50位学生,男女各占一半,他们围成一圈席地而坐开营火晚会。求证:必能找到1位两旁都是女生的学生.

6.试证:不能用面积为1×4的长方形木块将10×10的棋盘覆盖.

7.在2k×2k的方格表上,有3k个格子涂黑,求证:可以选择k行及k列,包含了全部这3k个黑格.

8.7×7的方格表中有19个方格涂成红色。如果该行或该列中至少有4个红格,那么称这一行或这一列是红色的。问:该方格表中红色的行和列的总和最多有多少?

9.有一个矩形顶点坐标分别为(0,0),(0,m),(n,0)与(n,m),其中m和n均为正奇数。将这个矩形分拆(既无重叠,也不遗漏)为一些三角形,使得每个三角形的顶点均为格点(横纵坐标均为整数的点称为格点),同时保证每个三角形至少有一条边与坐标轴平行并且这条边上的高为1.求证:一定存在至少两个三角形,它们各有两条边平行于坐标轴.

10.已知mn是偶数,将m×n的方格表中每个小方格涂上黑色或白色,两种颜色的方格数相等。问:能否有一种涂法,使每一行、每一列中都有一种颜色的方格数超过75%? 4F+PLgqBcaJ8pUbufYtD32+wlbdI6rspnKJE+yTxc0Vyff1tJs7138mb2EXI9wv8

点击中间区域
呼出菜单
上一章
目录
下一章
×