作业帮1、现有一个8*8的方格,要从左下角完成不重不漏的遍历,要求每一步只能向右、上或者左下这三种走法.问是否能够完成此遍历?2、现有一个8*8的方格,要求把1到64这些数字一一填入其中,使得其
来源：学生作业帮助网 编辑：作业帮 时间：2024/05/04 22:39:14
1、现有一个8*8的方格,要从左下角完成不重不漏的遍历,要求每一步只能向右、上或者左下这三种走法.问是否能够完成此遍历?2、现有一个8*8的方格,要求把1到64这些数字一一填入其中,使得其
1、现有一个8*8的方格,要从左下角完成不重不漏的遍历,要求每一步只能向右、上或者左下这三种走法.问是否能够完成此遍历?
2、现有一个8*8的方格,要求把1到64这些数字一一填入其中,使得其中每一个T字样的四格里的数字之和是5的倍数.问是否能够完成此遍历?
以上两问题,均请给出染色方案和分析过程,
1、现有一个8*8的方格,要从左下角完成不重不漏的遍历,要求每一步只能向右、上或者左下这三种走法.问是否能够完成此遍历?2、现有一个8*8的方格,要求把1到64这些数字一一填入其中,使得其
楼上的答案值得商榷.至少我没有看懂他在说什么.
这应该算是五年级的奥数里较难的题了.记得当初小学时,染色问题一直比较弱.现在依然如此,以至于这两题花了我较长的时间.
1、首先,说思路.既然题目已经告诉你要染色了,那其实就限制了思考范围,从而降低了难度.题目中最关键的是你要看见“往右”或“往上”本质是一样的,非常对称.但是“往左下”就不一样了.为什么这么说?因为考虑一下最普通的黑白相隔的染色方案,“往右”或“往上”都能保证每走一步会经过不同颜色的方格,但是“往左下”则保证每走这样一步都会经过相同颜色的方格.所以,他们是不同的.所以,从直觉上判断这里应该是本题的关键所在.
那么,怎么利用这一性质呢?其实问题没有那么复杂,所以不需要考虑太多的方法（我一开始就因为在几种不同的方案上徘徊导致了浪费时间）而只要直接考虑最普通的方案,即找一染色方案保证每走一步（不论是往右或往上或往左下）都会经过不同颜色的方格.
这样,目标其实很清楚了.我们需要三色去染这8*8的方格.如图.至于如何得到此图的染色过程其实不难,只要考虑对角线必须保证不同的颜色,然后又需要三色,这样依次“蓝黑白”地去染每条对角线,然后对于不同的对角线只需要保证相邻的对角线的染色正好错开了一格即可.
染色完成后,数一下.蓝色共22格,黑白各21格,出发点在黑格上.由于蓝色的比黑白两色的多出了1格,这就使我们联想到如果从左上角出发是否能完成遍历?稍作努力便容易知道,这的确可能.如图.这样就更明确了我们的方向,即玄机肯定在这蓝色比黑白两色多出1格的这特点上.
然后,就有这样的思考.出发点不算我们要经过63格,既然每步都会经过不同颜色的方格,而且从左上角的蓝色格出发正好经过了蓝黑白三色各21格（出发点的蓝色不算）正好能够走完,但是从左下角的黑色格出发会经过蓝22格,黑20格,白21格,而且是走不完的.那么这时自然地我们就会考虑如果能够保证“每三步”（任意的）正好经过了蓝黑白三色,那么的确从左下角出发是到达不了的,因为如果能保证“每三步”都经过了蓝黑白三色,那总共的63步就会保证经过蓝黑白三色各21次,但是显然从右下角出发经过的蓝黑数不同.矛盾.另一方面,从左上角的确保证了经过蓝黑白各21次,而且也的确能遍历.
所以,我们就想到是否能够保证“每三步”（任意的）正好经过了蓝黑白三色（顺序不一定）呢?答案是肯定的.原因从图上观察便知.要到达每一黑色格子唯一的方法是通过一白色的格子,而要到达任何的白色的格子只有通过蓝色的格子,而要到达蓝色的格子只有通过黑色的格子,这样循环.所以任何的三步都经过正好三色.从而63步经过三色各21次.与要经过蓝22格,黑20格,白21格矛盾,所以无法遍历.
