数学题,会编程的进!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!(够醒目)

Question

一共有16间房子组成一个正方形,相邻房间各有一扇门相通,现在要求每个房间必须通过一次(只能一次),问:有没有可能做到从左下角的房间进,然后从右上角的房间出.如有,则给出一条路径.
房间编号如下所示:
4  5  12  13
3  6  11  14
2  7  10  15
1  8  9   16
(从房间1进,房间13出.)

Answer 1

用染色原理是这样证明的:
把房间1染成黑色,然后按照相邻房间(1和7这样的不相邻)不同色的原则分别然成白色或黑色,这样会发现房间13也是黑色.
那么路径必然是:黑->白->黑->白...因为16个房间通过且只通过一次,那么出去的那个房间必定是白色的,由此证明不能从房间1进房间13出.