主题：【原创】也出一道数学题，做个智力体操 -- 南京老萝卜
家园 【原创】也出一道数学题，做个智力体操 画个矩阵，例如5x7，再在矩阵上画上棋盘格。
在它的一角入射一道光线。光线是以45度角射入，光线在棋盘格内的行进规则如下：
1。光线沿直线前进；
2。当光线碰到棋盘的壁时，反射，即从这个方格的对角线转到边上另外一个方格的对角线，继续前进。
图贴不上来，不过很简单，画一下就知道了。
要证明的是：
对于任意 M x N 的棋盘格，（M,N互质）
1，光线一定能最终射出这个MxN的棋盘格，也就是说，不会在棋盘格中形成一个循环绕不出来；
2，光线在射出棋盘格前，一定路过每个小方格，并且每个小方格只路过一次。
祝大家玩得愉快。
家园 关于这条题目 这条题目来源于上中学时在课堂上的走神，自己在纸上乱画，老师远远看去好像做题目挺卖力的。至于什么是正确的证明，说实话自己也没谱。后来请教过两个博士，第一次是和一个博士在廊下躲雨，百无聊赖，顺便请教。那个博士想了五分钟，觉得这个题目太简单，不值得去动脑筋。正好当时没有笔，说回去了证给我看。可是后来再碰到，他也没有再提起。想是太小的事，没资格引大人动脑。后来又有一博士做presentation，正事完后，大吹特吹，说从小自己如何如何聪敏，人送外号小牛顿。就着这个劲，奉送两顶高帽之余，虚心请教。此人斜睨一眼，想了20秒，说：“你这个啊，应当是先找本图论来学学。当年我们上学的时候，!@#$%^”继续开吹。
我的想法和spin比较接近，也是先画一个（M*N)*(M*N)的大正方形。然后画一根直线从左上角一直画到右下角，斜穿过整个大图。这根线经过M*N个格子，也就是光线穿过的整个路程。然后我把这张纸折叠起来，横向折M次，纵向折N次，这个（M*N）*（M*N)的大图就变成了M*N的矩形。每折一次，光线就在折线上反射一次。用折纸来模拟反射。这样是不是能说明问题？
当然，这还不是严格的证明，只是看上去要简单一些。
家园 做操啦，一二三四，二二三四。。。 用M×N的小矩阵拼出一个M*N×M*N的大矩阵
光线从一个交射入，从对角线上的交射出。
而光线总共经历了M*N个小格子，
如果在光线经历的小格子中有两个格子对应于小矩阵中的同一位置
，则这两个小格子在x方向的距离必为M的整数备，而y方向的距离必为N的整数被，但因为x方向的距离=y方向的距离（因为在大矩阵的对角线上），但因为M,N互至，所以以上假设不成立，
所以每个小格子只能经历一次。
家园 有些疑问，探讨一下 你的解法中，实际上只证明了在你变换后的“M*N×M*N的大矩阵”中，光线经过了M*N个小格子再射出，并且这些小格子在每个M*N小矩阵中位置不同。你需要补充证明你的变换对原问题是等价的，即变换前后，光线的运行属性是一致的。直觉上你的解法没有问题，但需要证明。
我的解法是这样的，首先证明在M和N互质时，入射光线必然从某个固定的顶角(谢谢衲子的提醒,更具体的说明见下面的帖子)射出。再证明光线在矩阵内不能经过相同的线路（否则进入循环），且经过M*N格再射出。
家园 入射光线并不必然从对角射出, 例如2X3的棋盘 只有在M,N均为奇数时才从对角射出.
原题只需证明光线能射出棋盘(一定是从某个角射出, 不一定是对角).
还有, 只证明"光线在矩阵内不能经过相同的线路"还是不够的, 譬如 A->B 与 C->B 为两个不同的线路(A,B,C代表位于8-邻域内的棋盘格), 但B被经历了两次. 所以, 就算证明了"光线在矩阵内不能经过相同的线路（否则进入循环），且经过M*N格再射出"也不能得出每个格子被经历(且仅经历)了一次.
所以俺还是倾向于spin的证明思路. 只是不知有没有更简明的方法.
家园 可能有些没有说清楚 我省略了中间一步的引理。假设光线从左上角入射，并且以左上角为坐标原点，X轴向右为正，y轴向下为正。我们可以得出一系列光线经过的点的坐标，假设矩阵为4*3，光线经过
(0,0),(1,1),(2,2),(3,3),(4,2),(3,1),(2,0),(1,1),(0,2),(1,3),(2,2),(3,1),(4,0)射出矩阵。
我们可以观察出光线经过的点的坐标是有规律的，这些点的x,y坐标值的差的奇偶性是一致的，是由入射点决定的。因此，在任何一个方格的四个顶点里，只有两个坐标值的差的奇偶性和入射点符合的顶点是可以被经过的，另外两个不行。
另外修正一点，确实不是一定从对角点射出，而是从坐标值的差的奇偶性和入射点相同的顶点射出。如在上面的例子中，从(0,0)入射，只能从(4,0)射出，而不能从(0,3)和(4,3)射出.
家园 是啊，上面那个不严格 在M*N×M*N的大矩阵中，存在以下的情况
---------------
D | B | D
----------------
C | A | C
------------------
D | B | D
其中A,B,C,D都是M×N的矩阵
A,B镜像对称
A,C镜像对称
A,D反演对称
所以在M*N×M*N的大矩阵中并不都是M×N（A)这样一种
还包括B,C,D。这样光线在M×N中的反射就映射到大矩阵中的直线运动。
上面那个说法只能证明：如果光线经过某个格点两次，那这两个格点所处的M×N矩阵不可能都是A种类型的。
还需要证明：这两个M×N矩阵不可能是一个是A类型的，一个是B类型的，简记为A+B，
所以还要证明这两个矩阵不能是A+B， 或A+C 或A+D
这样才能涵盖所有可能。
下面就简单说一下
如果是A+B，或A+C的情况，
对应于那个被两次经过的小格点 光线必定如下图的那样穿过这个小格点
A-----B
| |
C-----D
如果第一次光线是从C到B，那第2此光线必定是从A到D或从D到A
在M×N的矩阵中考虑此问题，可以得出当光线没有打到4个交的时候，这是不可能的，（可以把C,B编成1,A,D编成-1，在边界反射的时候必定还保持1到1,而不可能变成-1到-1）
对于A+D的情况
光线经过某个格点两次的时候，如果第一次是从（如上图）C到B，那第二次必是从B到C（就是正好反过来）， 因为边界的反射是不可能提供入射光线被原路反射回去，所以这种情况也不可能。
HEHE，这个解法也太繁琐了，简直是在锻炼肌肉呀，谁有轻灵的解法。
家园 俺懒汉的证明, 手工验证一下即可(此法偶们的黑话叫"裸算") 家园 不解 每个棋盘格是正方形吗? 若是,则光线碰到格子的一角时是不是分裂成两束光? 若不分裂,那么"边上另外一个方格"是指哪一个边上?