一道小学题目--有答案、有扩展应用

老财迷

陪丫丫上奥数，今天有一道题目，给各位活动一下。
如图，有5块4*1的纸板，能否拼成5*4的长方形？如能，给出一个方案；如不能，说明理由。

loy_20002000

看了20分钟了，找不到通解。。。。。

只能暴力破解么么么么么么。。

白天爱黑夜

当年儿子也学习奥数，被推荐参加学而思杯竞赛，结果半小时就出来了。
问这么这个快就考完了。答：做对不容易，做错还不容易吗？
从此，孩子就脱离了奥数的苦海。

smileREGENT

染色与覆盖问题

在长方形的小格子里相间涂色黑白，结果是10个黑,10个白。
按照同样规则在5个4*1纸板里做，只能得到11个黑，9个白；或11个白，9个黑（最下面的 T形 有两种涂法，3黑1白或3白1黑）

假如能拼成，5个4*1纸板的黑白方块数，应该同5*4长方形相等。但由上述过程可知黑白方块数必然不等，故不能拼成。

propane

横看竖看都是俄罗斯方块

老财迷

smileREGENT 发表于 2018-7-19 21:23
染色与覆盖问题

在长方形的小格子里相间涂色黑白，结果是10个黑,10个白。

回答的是如此专业，当年肯定是个奥数娃

老财迷

在“地板”层已经有了专业回答。
这类题目好多啊，这是另一个：

图中，“马”能否按规则在半个象棋盘内走棋，每点走且仅走一次，不重复不遗漏地遍历完所有点？
---（修改，此处我写的不对，按刷牙鼠在12楼的说法，应该是“马”能否按规则在半个象棋盘内走棋，每点走且仅走一次，不重复不遗漏地遍历完所有点后，下一步回到起点。   或者直接看12楼的问题也行）
.
.
.
.
.
.
.
.
.
.
.

主帖中的题目，用暴力破解可能还行，但这题暴力破解就太麻烦了。
解题思路是一样的，涂上黑白点，马的相邻2步一定是异色，而黑白点数量不等，因此 不能 “每点走且仅走一次，不重复不遗漏地遍历完所有点”

（此图，马的下面也应涂上黑框）

夏翁

smileREGENT 发表于 2018-7-19 21:23
染色与覆盖问题

在长方形的小格子里相间涂色黑白，结果是10个黑,10个白。

试想一下，把T形状换成一个长条的，黑白各为10格，你能说这样五个1x4就可以拼成5x4吗？

澹泊敬诚

老财迷 发表于 2018-7-19 22:47
在“地板”层已经有了专业回答。
这类题目好多啊，这是另一个：

如果此马从车的位置开始走，就可以了吗？

smileREGENT

夏翁 发表于 2018-7-21 03:31
试想一下，把T形状换成一个长条的，黑白各为10格，你能说这样五个1x4就可以拼成5x4吗？ ...

不能，同样可以用染色法来解决，但要换一种染法。

试规定5x4同列同色，奇数列与偶数列为异色。在5x4内有12黑，8白或12白，8黑


依此法，对5个4x1而言：

第1个L形，由于横置或者纵置及黑白选色，有4种涂色法，结果为 黑1白3 或 黑3白1

第2个Z形，四种涂色法，结果总为 黑2白2

第3个田字形，四种涂色法， 结果总为黑2白2

第4、5个长条形，四种涂色法，结果为 黑4 或 白4 或 黑2白2


因此黑白方块数总计有多种情况（总计有2x3x3=18种情况）

在这18种情况中，第1个L形黑白方块数总为奇数个，故5个4x1最后总计的结果一定是奇数个（因为其余四个图形黑白块是偶数）。但5x4的黑白方块数均为偶数，故不能拼成。

————————

染色法的关键在于找到某种染色方法，最后推出矛盾。这个方法只能欺负下不能拼成的，教授的意思应该是想找一个充分必要条件，只要满足该条件，就能拼成5x4；能拼成5x4的，都满足该条件。这个方法其实只是在必要性上下了功夫：能拼成5X4, 按照某种染色方法，4X1和 5X4 不同颜色的方块数应当相同。凡违背这一条件的都不能拼成。

教授你叫俺写个充分必要条件出来，那也太难为俺一个拔牙的了呀

南京老萝卜

澹泊敬诚 发表于 2018-7-21 05:18
如果此马从车的位置开始走，就可以了吗？

smile说的是对的，马从车的位置走，只是满足了必要条件，但不是充分条件。能不能走通，还要试。

smileREGENT

老财迷 发表于 2018-7-20 12:47
在“地板”层已经有了专业回答。
这类题目好多啊，这是另一个：

又看了下，财迷童鞋你这个表述有误啊

如果确定是竞赛题的话，这道题完整表述应该是这样的：“马能否 按规则在半个象棋盘内走棋，每点走且尽走一次，不重复不遗漏地遍历完所有点，且最后又能回到出发点？”类似下面这道题的第二问：



解题思路正如7楼里所说，继续用“二分图法”来解决：



涂上黑白点，分别有22个黑点和23个白点。

假设 存在一个走法，不重不漏地遍历所有点，且最后返回到出发点。由与马的相邻2步一定是异色，其路径一定是：白（初始点）-黑-白-黑……-白-黑-白（初始点），依照此路径，在返回到出发点前，已经遍历了全部点。从该路径来看，黑白点数目应该相同。

这与22个黑点，23个白点相矛盾，故不能。

那么老财迷童鞋的这个问题：“马”能否按规则在半个象棋盘内走棋，每点走且仅走一次，不重复不遗漏地遍历完所有点？有没有解决方法呢？答案是没有。或者说只能靠回溯算法来计算，也就是暴力解决法，如同南京老萝卜童鞋回答的那样，得写成算法，让计算机去解决。

夏翁

smileREGENT 发表于 2018-7-21 06:02
不能，同样可以用染色法来解决，但要换一种染法。

试规定5x4同列同色，奇数列与偶数列为异色。

来斯

一个黑一个白，看来笑牙医拔牙是隔一个拔一个。。。哈哈哈。。。

老财迷

smileREGENT 发表于 2018-7-21 19:03
又看了下，财迷童鞋你这个表述有误啊

如果确定是竞赛题的话，这道题完整表述应该是这样的：“马 ...

这不是竞赛题，是我写的不严谨

我是在陪读时听了2句，随手写下来的，想了想，你写的是对的！！！

dynthia

smileREGENT 发表于 2018-7-21 05:03
又看了下，财迷童鞋你这个表述有误啊

如果确定是竞赛题的话，这道题完整表述应该是这样的：“马 ...

1978年，Paul Cull和Jeffery de Curtins证明了，在m(>=5)乘n(>=5)的棋盘格上，一定存在从一个角落开始的马步不重复遍历，如果m或n是偶数，则存在不重复遍历返回出发点。

smileREGENT

dynthia 发表于 2018-7-22 00:10
1978年，Paul Cull和Jeffery de Curtins证明了，在m(>=5)乘n(>=5)的棋盘格上，一定存在从一个角落开始的 ...

厉害，感谢分享！

他们已经直接在文章里做出了5*9从左下角开始的knight's path，引用如下：

loy_20002000

dynthia 发表于 2018-7-22 00:10
1978年，Paul Cull和Jeffery de Curtins证明了，在m(>=5)乘n(>=5)的棋盘格上，一定存在从一个角落开始的 ...

你这知识面........



我以前提到过快速排序，提出和发表的区别大部分人是不会留意的。我早就想问了，你这些知识是怎么来的。是读书学的还是看书？还是工作?还是其他什么。

loy_20002000

dynthia 发表于 2018-7-22 00:10
1978年，Paul Cull和Jeffery de Curtins证明了，在m(>=5)乘n(>=5)的棋盘格上，一定存在从一个角落开始的 ...

歪个楼，请教你几个语言方面的问题。我最近这一年在学哑巴外语，爱坛学哑巴语文的印象中只有你。记得你说过你听不懂法语也不会说。问你几个问题自己好有个参照。

1.你每天投入多少时间。
2.每天记多少个单词。
3.一般来说坚持多长时间可以顺畅的看书和报纸。
4.累计自学了多长时间。是多门语言的总和，我指的是自学的哑巴外语。
5.学哑巴外语有没有什么要点，或者说你有没有什么心得。

这楼里有同样学哑巴外语的高人，也请赐教啊。