International Mathematics Tournament of Towns

環球城市數學競賽

1999秋季賽高中組　高級卷　 31 Oct. 1999

※ 每題必須詳細寫下證明及理由，只寫答案不一定有分數。

(1) 如果可以將正整數1 , 2 , 3 , …, ｎ填在圓周上，使得依順時鐘方向任何兩個相鄰的數之和，都能夠被它們的下一個數整除。求ｎ的所有可能值。(三分)

　　ｎ= 1,2時成立。當ｎ3時。如果圓周上有二個連續偶數，則被造成這個圓周上的每一個整數都是偶數(不合)。因為圓周上必有一個整數是偶數，而它的逆時鐘方向的下二個數及順時鐘方向的下個數，都必須是奇數。由於1～ｎ中，而且奇數的個數都是奇數，奇數的個數最多比偶數的個數多1個，所以圓周上最多只有一個偶數，這樣奇數有2個，所以ｎ最多是3，1, 2, 3這個數任意排在圓周上都可以，所以ｎ=1, 2, 3。

(2)在一張矩形紙片上有一些黑點：(a)當所有黑點共線；(二分)
　　　　　　　　　　　　　　(b)任意三黑點。(三分)
　試著將這張紙沿直線摺幾次，但摺線不可以通過任何黑點。然後，使用細針插進摺好的紙，使得針只穿過所有的黑點，但不能穿過其它的點。求證：在(a)和(b)二種情況下，上述穿法必能成功做到。

　　(a)設矩形紙上有共線的個點，依序取名為。令的垂直平分線為，。我們沿著依扇子折疊法，一正一反對折紙張後，此時這ｎ個點都會重合，而且ｎ – 1條直線把平面分成ｎ部份，所以一針插過黑點，它們穿過所有的黑點，但不會穿過其它的點。
　　 (b)白紙上任三點A,B,C(如圖一)，我們可以在B、C點附近各任取異於B、C點之點，使得與間之距離不大於d，且直線不與及其內部相交。以為對稱軸，取直線之鏡像直線與間之距離亦不大於d。
　　設直線與矩形之二邊交點為x,y。不失一般性，令與交於x；與交於y。摺疊紙片，將點O,x重合，取出中點，將點O,y重合，取出中點。將紙片沿直線對摺，則O點將落在直線上。再對摺紙片將與重合，得出摺線，再繼續將與重合，……一直依此方式繼續下去，總可以使與之距離小於d，這時與之間是一疊非常細窄的一疊“紙帶”，最後將這疊紙帶沿直線向方向對摺。
　　同樣，也可以在的、邊上作上述同樣的動作。此時，則原紙片變成及外部三條非常細窄的紙帶，其寬度要多小就可以多小，我們差不多可以忽略不計。這時(1)如果不是正三角形或等腰三角形，則總可以將最短邊上的二端點對摺重合，如圖二，不失一般性，假設，為摺痕，則，，，因為，得，故C點會落在之外部。

(3)小唐和小夏輪流構造一個數列，首先任給一個正整數作為首項，由小唐開始增添新項，他選擇的方法是將前一項的數值加上該數的某一位數字(例如：首項是234，小唐可選234+2或234+3或234+4)；接著換小夏，他選擇的方法是將小唐新添的數值減去該數的某一位數字(例如：小唐選的數是237，則小夏可選237-2或237-3或237-7)，如此不停地輪流構造下去。求證：有一個整數會在這數列中至少出現100次。(六分)

(一)如果希望某數在此數列出現100次，則我們該如何去解題呢？
小承：希望這個數列有上界，即存在一個，使得
　　 (事實上只需要此數列的某個無限子數列有上界即可)
　　我們從題目知，道小唐添的項是偶數項，其中，x是中的某數字，。小夏添的項是奇數項其中，y是中的某數字，。
(二)我們可以找集合其中，如果數列中任何項都不會大於Z，則有上界。
　　如果數列中某一項超過Z。由於每一項最多比前一項多9，而A集合有連續9個數，所以它或者它的前面有一項，則我們要證明存在一個使得。
(三)如果是n位數，則令。(如果，Z取位數即可)。
　　令

　　如果數列中，輪到小唐添新項會屬於；輪到小夏添新項會屬於。
　　如果數列中，輪到小唐添新項會屬於；輪到小夏添新項會屬於。
　　如果數列中，則必須輪到小夏，小夏添新項會屬於；由上述論證數列永遠屬於。所以Z + 9是它們的上界。
小君：令，我們可以令

小淳：跟你的想法一樣只不過，這也是一種正確答案。

(4)有n個砝碼，它們的質量分別為1,2,3,…,n克，在所有可以的方法中，打算從兩邊各拿掉兩個砝碼，而不影響平衡。
　　(a) 求證當n=100時，一定能成功。(四分)
　　(b) 當時，是否對所有的n值都保證能成功？(四分)

小承：我的想法是：將這n個砝碼分成二組放在天平的兩邊，使它們平衡，不失一般性，設1在左邊，左邊的砝碼都標L，右邊的砝碼都標R。
　　把所有砝碼拿出來，按輕重從小到大排成一列，成為一個L,R的序列其中。把這個序列分成數段(至少2段)，每段的標號L或R都相同，但和下一段不同。
　　 (i)只分成二段，因為任取四個砝碼及則

　　(1)n=100，因為不可能是(i)及(iv)。即不存在k使得(*)式成立得證。
　　故只能是(i)(ii)(iii)，即必可以。
　　 (2)討論一般的n。取n=20, k=14則可能分成(i)的狀況，所以可能使左右各拿掉2個砝碼使得仍舊平衡。

(5)在一個很大的棋盤上，其中有個小方格被塗上紅色，而這個小方格排列的方式，可讓一枚只能夠橫走或直走的棋子，從任一紅色格子不用穿過沒有塗色的格子，便能在數步移動後，到達任何其它的紅色格子。求證可以將這個紅色格子分割為n個矩形(包括正方形)。(八分)

　　一個紅色小方格和它的上、下、左、右的紅色小方格稱為它們相鄰令T為一堆紅色小方格所組成的集合。從任何T中一個紅色小方格開始，每次都可以從任一紅色格子移動與其相鄰的紅色小格子，能在數步移動後，到達任何其它的紅色格子。我們稱T為連通。
　　題目的意思是指這個紅色小方格形成一個連通部份。我們將證明一個更一般的定理。定理：題目裏大棋盤中的小方格改成或小方格，結果一樣可以分割成n個矩形。
　　證明：我們將用數學歸納法證明上述兩種情形同時成立。
　　當n=1時，顯然成立。
　　假設時，題目是成立。
　　當n = k + 1時，我們將把個紅色小方格分成兩個連通的子集合，它們分別有2s與2(k + 1 - s)，由假設可知它們可以被分為 s 和(k - s ) + 1個小矩形，所以共有k + 1小矩形。
　　 (a)我們首先考慮棋盤上有個連通紅色小方格，我們拿掉某一小方格A，剩下的2k個紅色小方格如果