是否可能全部都变成黑格? [:)]

野菜花 · 发表于 2005-12-14 21:36:22

mXn 的矩形魔板中，有黑白两种格子，且白格多于

(m-1)*(n-1)个，若在一个 2X2 的小正方形中有三个黑格，那么第4个白格过段时间也会变成黑格，问魔板上的方格有没有可能全部都变成黑格。

constant · 发表于 2005-12-14 22:49:24

不能。证明待会儿再写，多挣一块钱

野菜花 · 发表于 2005-12-14 23:01:27

狡猾狡猾地，我也挣一块钱！

constant · 发表于 2005-12-15 01:52:46

挺难的，应该加精

大头羊 · 发表于 2005-12-15 04:14:42

要过圣诞节，就这么挣钱啊？不如跟我去开飞机

husonghu · 发表于 2005-12-15 06:47:23

大头羊是pilot呀！怪不得见多识广。是中国民航吗？还是东方航空？我猜是前者[:B]

本贴由[husonghu]最后编辑于：2005-12-14 22:47:58

husonghu · 发表于 2005-12-15 07:32:30

很对。非常感谢大伙的好题。有时没及时见到，但早迟会加精；有的题还先加精再置顶

野菜花 · 发表于 2005-12-15 17:42:44

原来大头羊是 pilot，难怪

不仅脑子好，身体也棒，能够抓到歹徒。计算起来那么精确，争论起来那么认真，开飞机可不能带半点含糊的。知识面也广, 可以应付各种紧急情况.

那次说要出去执行任务, 生死难测，也有了解答。

PFPF!

可否问个问题，如果遇到劫机者，你怎么对付？

constant · 发表于 2005-12-15 18:08:51

首先有这两条：1）如果有一行或一列全为白格，则该行（列）不会变黑；2）如果所有黑格都包含在两个不相交的子矩阵中，则黑格不会长出子矩阵。现在证明少于(n+m-1)个黑格，一定满足其中之一。

设1）不成立。在每一列中选一个黑格。这n个黑格在k行上，即在k个不相交的子矩阵中。注意 k > 1，不然必有一行全为白。剩下的m-k行中，每行再选一个黑格。这些黑格再加到原来的n个中，还是k个不相交的（大一点的）子矩阵。现在还剩下k-2个黑格，每加一个最多可以连接两个子矩阵。都加进去后至少还有两个不相交的子矩阵包含所有黑格。

有没有好一点的证明？

wushuihe · 发表于 2005-12-15 18:59:03

响应Husonghu的号召, 咱也注册答题, 以便挣钱? 不知答错会不会倒扣?www.ddhw.com

www.ddhw.com

不理解’两个不相交的子矩阵’是什么意思.是不是没有共同行也没有共同列? 如果在3*3的矩形中,(1,2),(2,1),(2,3),(3,2)是黑格,怎么分两个不相交的子矩阵呢?www.ddhw.com

我也有个证明, 却好像有点似是而非.www.ddhw.com

不能.www.ddhw.com

如果m*n的矩形可以全部变黑, 那么增加m-n个黑格就能让m*m的正方形全部变黑.www.ddhw.com

如果2m-2个黑格能使m*m的正方形全部变黑, 那么至少存在一个2X2的矩形包含三张黑格. 在该矩形所在两列中, 如果其中一列某个位置是黑格, 那么把另一列相同位置染黑. 同样处理两行. 现在的正方形更能全部变黑了.www.ddhw.com

合并所处理的两列及两行. 角上四个(或两个)被分割的小正方形和中间的十字仍保持同样的结构和边界条件. 因此这新的(m-1)*(m-1) 的正方形也能全部变黑. 但原始的黑格数至少少了两个. 即2(m-1)-2个黑格能使(m-1)*(m-1)的正方形全部变黑.www.ddhw.com

可但是呢, 两张张黑牌是不能使2*2的正方形全部变黑的.

wushuihe · 发表于 2005-12-15 19:02:50

我居然和Hu班长是同样的蓝色小R嘛.

husonghu · 发表于 2005-12-15 19:13:47

注册了！欢迎欢迎

蓝色的是GG，红色的是MM，黑色的是性别不明.

constant · 发表于 2005-12-15 21:25:20

没看懂。等野JJ来看吧。（1，2），（3，2）和（2，1），（2，3）是两个不相交的子阵。

tttttttttttyyyy · 发表于 2005-12-15 22:16:27

That was good!

I used induction to proof the problem.

First define some terms,

(1) A rectangular is a rectangular of any size filled with black square(s), a single black square is a 1*1 rectangular.

(2) A L shape is something like

*******

*

(* stands for black square)

(3) Two rectangulars are contiguous if and only if they intersect or share a (or part of ) edge.

Let's introduce several lemmas.

(1) Rectangular can not fill more black squares by itself

(Proof omiited)

(2) L shape can generate a whole rectanguar

(Proof omitted)

(3) If two rectangulars are not contiguous, they can not fill more black squares by themself

Proof, since two rectangulars are not contiguous, No such thing like

*

**

Can be found in them, so we can not use the rule

(4) When the process of black square growing can not continue, only rectangular left.

Proof, (i) at the beginning, only 1*1 rectangular (ii) If two rectangulars are contiguous, they form 0,1 or 2 L shape(s), filling these L shape (lemma 2) gets a new rectangular which contain both 2 original rectangulars.

Now we prove the generalized form of the original problem

To generate a rectangular of m*n , at least m+n-1 original squares are needed.

Proof by induction

(1) 1*1 rectangular needs 1+1-1=1 original black square, (note 1*1 rectangular is not generated, must be original)

(2) By lemma (1), we need two contiguous (lemma 3) rectangulars to fill more black squares.

Suppose the two rectangulars are m1*n1, m2*n2, they have m1+n1-1, m2+n2-1 original black squares respectively. Since the two rectangular must overlap at least one row or column so the new rectangular (suppose m*n) must be less than (not equal to) (m1+m2)*(n1+n2), that is m

The generalized form is correct

野菜花 · 发表于 2005-12-16 02:11:44

我特别把你们的证明印下来，带到考场准备监考时来拜读研究。结果右面边上约1/4 的字都没印出来。

constant 的证明很妙. 不过开始对不相交的子矩阵我也搞不清楚，以为是取k个不相交的子矩阵，其它同行的黑点就不要了，这样我就不确定扔掉的黑点后来会不会起作用。看了你给wushuihe 的解释才懂。www.ddhw.com

wushuihe 的证明有些细节我也没看懂，思路是对的，用反证法和倒推归纳法。我知道的方法就是用反证法和归纳法。

tttttttttttyyyy的证明很详细规范，很不错！

大头羊 · 发表于 2005-12-19 04:54:48

彻底误会了，其实我是设计飞机的一个子系统的。开飞机？我晕

		自动登录	找回密码
密码			立即注册

动态微博

是否可能全部都变成黑格? [:)]

不能。证明待会儿再写，多挣一块钱[:))]

狡猾狡猾地，我也挣一块钱！[:E]

挺难的，应该加精 [:E]

要过圣诞节，就这么挣钱啊？不如跟我去开飞机[:O]

大头羊是pilot呀！怪不得见多识广。是中国民航吗？还是东方航空？我猜是前者[:B]

很对。非常感谢大伙的好题。有时没及时见到，但早迟会加精；有的题还先加精再置顶[:P]

我开飞机的话可能绕地球一周又回到原地还不知道。Wow，我们这里人才真是应有尽有, 原来大头羊

回复：是否可能全部都变成黑格? [:)]

回复：回复：是否可能全部都变成黑格? [:)]

我居然和Hu班长是同样的蓝色小R嘛.

注册了！欢迎欢迎[@};-][@};-][>:D<]蓝色的是GG，红色的是MM，黑色的是性别不明.

回复：回复：回复：是否可能全部都变成黑格? [:)]

回复：回复：是否可能全部都变成黑格? [:)]

三个人给出三个不同的证明，都很棒, 各有千秋![@};-][@};-][@};-]

回复：我开飞机的话可能绕地球一周又回到原地还不知道。Wow，我们这里人才真是应有尽有, 原来大头羊