5.一個非常大的城市，他的所有街道都是東西向或是南北向(如棋盤式)。小朱從此城市的點P車頭朝北開始駕車，最後回到點P車頭仍然朝北。在路程中除了開始及最後各經過點P一次外，其他任何地點都沒有通過兩次或兩次以上。若路程中小朱共作了100次左轉，請問他至少必須右轉幾次?(五分)
國中

回應

ARGY2K

2005-03-13 21:55
這次環球沒去考...
這提我的想法是這樣：(只簡單描述，需要各位想像或畫一下，不知大家覺得對不對)
由於這次的路徑完全不會有交叉，且最後回到原出發點並朝向同向，故整個路線將形成一封閉幾何形狀。
視行車的路線(回歸起點時的方向)，右轉可能為270或90度的內角，左轉便相對為90或270度(且在整個幾何圖形內都是)。
當右轉為270度時，設左轉X次，可列出
270*100 + 90X = 180*(100+X-2)
解得X=104
當右轉為90度時，設左轉X次，可列出
90*100 + 270X = 180*(100+X-2)
解得X=96
故至少要左轉96次。

yl871809

2005-03-13 22:11
引用：

ARGY2K 寫道:
這次環球沒去考...
這提我的想法是這樣：(只簡單描述，需要各位想像或畫一下，不知大家覺得對不對)
由於這次的路徑完全不會有交叉，且最後回到原出發點並朝向同向，故整個路線將形成一封閉幾何形狀。
視行車的路線(回歸起點時的方向)，右轉可能為270或90度的內角，左轉便相對為90或270度(且在整個幾何圖形內都是)。
當右轉為270度時，設左轉X次，可列出
270*100 + 90X = 180*(100+X-2)
解得X=104
當右轉為90度時，設左轉X次，可列出
90*100 + 270X = 180*(100+X-2)
解得X=96
故至少要左轉96次。

我一開始的想法跟你一樣，但是算法跟你不一樣...

訪客 (未驗證)

2005-03-14 21:46
這是個封閉的路徑必定可以把裡面都劃滿格子
(依照城市的路線格子就可以了)

由上可知所有的路徑都可以由最簡單的矩形( P 上下二格)出發用小格子接成 (路徑就是封閉區域的周長)

再用窮舉的方法討論小格子構造在一個轉折點,二個轉折點......等情況不需要啥技巧就可以看出左轉次數增加會和右轉次數增加一樣

由此知道左轉次數-右轉次數的可能基本上和最簡單的矩形完全一樣=+-4
所以右囀次數最少為 96



這是高中組的第四題
考試時我有想到小格子的概念不過最後沒親自去動手所以這 4 分沒拿
還好有同分的別題上我補回來了^^

shao

2005-03-15 19:10
原本是向北方，每左轉一次就是按照
西→南→東→北 轉一個方向。反之每右轉一次就是倒回去一個方向，抵銷一個左轉，又結束時也是向北方表示他轉了X圈。每轉一圈就是照著 西→南→東→北 轉四次，所以100─右轉的次數=四的倍數，但我不知道如何證在一個封閉曲線內不可能往一個方向轉超過360度，請大家幫忙。

yl871809

2005-03-18 20:15
引用：

shao 寫道:
原本是向北方，每左轉一次就是按照
西→南→東→北 轉一個方向。反之每右轉一次就是倒回去一個方向，抵銷一個左轉，又結束時也是向北方表示他轉了X圈。每轉一圈就是照著 西→南→東→北 轉四次，所以100─右轉的次數=四的倍數，但我不知道如何證在一個封閉曲線內不可能往一個方向轉超過360度，請大家幫忙。

這個部分我也不太會寫......

yl810131

2005-03-22 18:54
引用：

shao 寫道:
原本是向北方，每左轉一次就是按照
西→南→東→北 轉一個方向。反之每右轉一次就是倒回去一個方向，抵銷一個左轉，又結束時也是向北方表示他轉了X圈。每轉一圈就是照著 西→南→東→北 轉四次，所以100─右轉的次數=四的倍數，但我不知道如何證在一個封閉曲線內不可能往一個方向轉超過360度，請大家幫忙。

我想是因為:要想形成一個封閉曲線,就得轉360度(右轉和左轉相抵銷,一個左轉為90度),而最單純的封閉曲線就是矩形(360度,4個左轉),當轉到矩形的第3邊時,若小朱早了x個路口就左轉了,勢必要再往南走(即右轉).再向東走(左轉)才能連成一個封閉曲線,而這個情況有5個左轉.1個右轉,還是360度.如果他在再往南走的路上又向東走(右轉),還是要向南(左)轉一次,6個左轉,2個右轉,仍是360度.同理可證,左轉為n時,右轉是n-4,所以答案是96次. 8-) 8-) 8-) :-P