此文章來自奇摩知識+如有不便請留言告知
標題:
一條有趣的關於鴿籠原理的問題
發問:
甲國的公路系統是這樣的: 在每個交叉路口有三條公路交會。(該國的公路系統是封閉的)證明該公路系統有下列性質: 假定一司機從任一交叉路口A1 出發延著三條路中任一條到下一路口A2 向右轉開到下一路口A3。在A3 向左轉, 這樣繼續下去, 一次右轉一次左轉。那麼他最後會回到出發點A1。
最佳解答:
我找到一個很簡單的證明，「幾乎」用不到鴿籠原理。 將公路系統看為一個圖。由於公路系統是封閉的，因此只有有限個交點個有限條邊。將交點編號為V1,...,Vn，另設E為邊的集合。 為每一條邊加上兩個標記： 1. 如果從編號小的點走到編號大的點，則標示為+，相反則標示為 - 2. 如果走完這條邊後轉左，則標示為L，否則標示為R。 考慮集合 S={(e, a, b) : e in E, a= + or -, b= L or R} 從A1開始走，每走一條路，加上方向和轉向的標示，我們有一個S中的元素。記錄司機走的道路、方向和轉向，我們得出一個S中的序列 s1,s2,.... 由於S是有限集，所以這序列必會出現重覆的元素。假設第一次出現的重覆元素是 si = s_i+k，其中k不為0。 Claim: i=1 若claim成立，則s_i+k這條路是由A1出發的，即走完s_i+k-1後，司機回到A1。 Proof of claim: 若 i 不是1，不失一般性，設si=s_i+k=(e,a,L)，其中a為+或-。記si的起點為v。連接v的三條路，其中一條為e，記另外兩條為x,y。 考慮s_i-1和s_i+k-1。 由於這兩條路的終點都是v，而且這兩條路都不可以是e，所以只可能是x或者y。另一方面，基於L和R是相間出現的，而si和s_i+k的轉向都是L，所以s_i-1和s_i+k-1的轉向都是R。即走完s_i-1和s_i+k-1之後，都是右轉入e。因此s_i-1和s_i+k-1走的必須是相同的路，假設是x，而且方向相同(都以v為終點)。 換句話說，s_i-1和s_i+k-1的三個coordinate都是相同的，即 s_i-1=s_i+k-1=(x,b,R)，其中b為+或-。 這和si是第一個重覆的元素矛盾。因此i必須為1。證畢
其他解答:
很難呢...CAAD3F79AE16AF09
留言列表
