西西河

主题:【原创】据说是小学升初中的题 -- 华恩

共:💬75 🌺32 新:
全看分页树展 · 主题 跟帖
家园 无解的证明及其他

如图给地图编号:

点看全图

外链图片需谨慎,可能会被源头改

每个格子的x,y编号相加为奇数的标为浅黄色,偶数的标为浅蓝色。由题可知,路线不重复,无对角线,所以每步只可能是x或者y加减1,也就是说从浅黄格子只能去浅蓝格子,反之亦然。起点和终点都是浅黄格子,所以可知如果路径存在,整个路径中浅黄格子数比浅蓝格子数多一。又已知要经过所有的黑点,黑点都在浅黄格子中,那么可知路径中浅蓝格子数不应该小于黑点数-1(不是等于是因为可能通过空白浅黄格子)。

数得黑点30个,浅蓝格子28个,于是可知此路径不存在。

典型的小学数学奥赛题,给一年级学生做太发指了!

另外,如果把不重复理解成只是不重复经过黑点,则只需要重复经过至少一个空白浅蓝格子即可,有n种解法,下图为一例:

点看全图

外链图片需谨慎,可能会被源头改


本帖一共被 1 帖 引用 (帖内工具实现)
全看分页树展 · 主题 跟帖


有趣有益,互惠互利;开阔视野,博采众长。
虚拟的网络,真实的人。天南地北客,相逢皆朋友

Copyright © cchere 西西河