分巧克力

constant · 发表于 2006-2-11 19:38:51

难度：++.5

www.ddhw.com2m x n 的矩形巧克力（n > 1），上面颜色如国际象棋的棋盘，黑白相间。但是其中有一块白巧克力和一块黑巧克力被吃掉了（这两块不一定连在一起，也不一定在边或角上，可以在任何可能的地方）。问：是否一定能将剩余的 (2m x n - 2) 块分成 (m x n - 1) 个"日"字型的小块？

huxlnn · 发表于 2006-2-16 16:31:07

1,对于此小矩形,长和宽分别为奇偶数个,考察其奇数的吃掉的两方格所在的两条边,还分别剩下偶数个黑白方格,故此两边能分割成日字,余下的是标准矩形,也能分割成日字

2,对于切除小矩形后的大矩形剩余部分,以小矩形的两边向外延伸切割,当n是偶数的时候,所切割的所有小的标准矩形都有偶数边,能分成日字;当n是奇数时,总能把组合成偶数边的小矩形,(具体有几种情形,都在此范围内,就不画图了)也即能分成日字.

constant · 发表于 2006-2-15 18:40:00

这两句话要证明：

“以此两点为顶点组成的矩形所含的剩余的方格必为偶数个相邻的黑白方格，故此矩形能分割成日字块”

“对于大矩形扣除此矩形后剩下的部分，有2m*n-a*b块即偶数块黑白相间且相邻的方格，亦能分割成日字块”

huxlnn · 发表于 2006-2-14 04:07:26

因为黑白相间，所以对吃掉的任意两块黑、白方格，设此两方格纵向相距a（同一列或行为1，相邻行或列则为2）,横向相距b，则a,b必有一个是偶数，以此两点为顶点组成的矩形所含的剩余的方格必为偶数个相邻的黑白方格，故此矩形能分割成日字块

对于大矩形扣除此矩形后剩下的部分，有2m*n-a*b块即偶数块黑白相间且相邻的方格，亦能分割成日字块

本贴由[huxlnn]最后编辑于：2006-2-13 20:11:35

constant · 发表于 2006-2-13 20:22:39

你有例子吗？

huxlnn · 发表于 2006-2-13 11:34:40

粗心了没看见黑白相间的条件[:E]

本贴由[huxlnn]最后编辑于：2006-2-13 19:51:47

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

动态微博

分巧克力

回复：这两句话要证明

这两句话要证明

黑白相间是很重要的条件，得出结论是一定能够分成mXn-1块日字型

你有例子吗？

粗心了没看见黑白相间的条件[:E]