第十九届中国东南地区数学奥林匹克 高一年级 第一天第四题()

给定整数m,n≥2.将-一个m行n列的方格表的每个格子染上红、蓝两色之一,使下述条件成立:对于同一行的两个格子,若它们均被染了红色,则它们所属的两列中,一列的所有格子都被染了红色,另一列中有格子被染了蓝色.求不同的染色方式的数目.

如果存在同一行有三个红色格子,那么至少有两个红格子所在列全是红格子,不满足题意。所以每行最多两个格子。

假如不存在同一行有两个红色格子,这种情况的有 (n+1)m个。

对于存在同一行有两个红色格子,但是不存在同一行有三个红色格子的情况,由题意可知,有且仅有一列全是红色。分为以下两步:

1.选一列全染成红色。这一步有n种可能

2.在剩下的列中,每列至多染一个红色,并且不能有以下情况:A:不能全染蓝色 B:不能存在所有的红色在同一列。   第二步可能的情况= nm-1-(n-1)=nm-n

所以存在同一行有两个红色格子,但是不存在同一行有三个红色格子的情况 一共有 n*(nm-n)=nm+1-n2种可能。

所以满足题意的染色方式一共有  (n+1)m+nm+1-n2   种。

————————

给定整数m,n≥2.将-一个m行n列的方格表的每个格子染上红、蓝两色之一,使下述条件成立:对于同一行的两个格子,若它们均被染了红色,则它们所属的两列中,一列的所有格子都被染了红色,另一列中有格子被染了蓝色.求不同的染色方式的数目.

如果存在同一行有三个红色格子,那么至少有两个红格子所在列全是红格子,不满足题意。所以每行最多两个格子。

假如不存在同一行有两个红色格子,这种情况的有 (n+1)m个。

对于存在同一行有两个红色格子,但是不存在同一行有三个红色格子的情况,由题意可知,有且仅有一列全是红色。分为以下两步:

1.选一列全染成红色。这一步有n种可能

2.在剩下的列中,每列至多染一个红色,并且不能有以下情况:A:不能全染蓝色 B:不能存在所有的红色在同一列。   第二步可能的情况= nm-1-(n-1)=nm-n

所以存在同一行有两个红色格子,但是不存在同一行有三个红色格子的情况 一共有 n*(nm-n)=nm+1-n2种可能。

所以满足题意的染色方式一共有  (n+1)m+nm+1-n2   种。