老王的夢田

給定一個長寬各為m,n單位的矩形，分割成mn個小正方形，那麼連接一條對角線，會通過多少個小正方形？

這個問題，應該可以從比較小的情況下手，大概就可以猜出答案了；只是猜出來之後，要去證明這結果的正確性。

先考慮m,n互質的情況，為什麼要先考慮這種狀況？因為這樣子，對角線上就沒有其他格點，比較簡單一些。

除了邊線外，內部會有(m－1)條縱線，(n－1)條橫線。
那麼我們想像一下，我從左下角的端點出發，要到右上角的端點，
從橫向來看，要跨過這(m－1)條縱線；
從縱向來看，要跨過那(n－1)條橫線；
每跨過一條線，就進入另外一格，而且在沒跨線的時候，不會進入另外一格。
所以就知道，總共會經過1＋(m－1)＋(n－1)＝m＋n－1個格子。

如果(m，n)＝d＞1，那麼表示對角線會通過中間的格子點，
令m＝d*p，n＝d*q，這條對角線就可以分成d段，
每段都是p*q的矩形的對角線，所以每段都會通過p＋q－1個方格；
一共就有d(p＋q－1)＝m＋n－d個方格。

最後一式就是我們所要的一般性結果。

我們也可以把問題推廣到三維的情形。

給定一個長寬高各為m,n,k單位的長方體，分割成mnk個小正方體，那麼連接一條體對角線，會通過多少個小正方體？

同二維的討論，如果m,n,k兩兩互質，那麼結論是m＋n＋k－2個；
如果(m，n)＝d＞1，且(m，k)＝1，(n，k)＝1，就會是m＋n－d＋k－1

其他情況，還沒想清楚，留做習題好了。