一條有趣的關於鴿籠原理的問題

我找到一個很簡單的證明，「幾乎」用不到鴿籠原理。

將公路系統看為一個圖。由於公路系統是封閉的，因此只有有限個交點個有限條邊。將交點編號為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。證畢

很難呢...