美夢成真教甄討論區

1.想在某個國家的大城市中建立航空網，其規則如下：
(1) 任何一個大城市都與不多於三個大城市有直達航班。
(2) 從任一個大城市到另一個大城市可找到一條直達或轉機一次的路徑。
試問：這個國家最多可能有幾個大城市？就你的答案畫出相應的航空網，並說明之。

這題有找到網路的答案如下，可是感覺很沒頭緒~
_____________________________________________________
找到10個大城市的解：ABCDEFGHIJ 十個大城市
A連BCD
B連AEF
C連AGH
D連AIJ
E連BGI
F連BHJ
G連CEJ
H連CFI
I連DEH
J連DFG

因為最多10個，而且10個大城市有解，所以上限為10個
____________________________________________________________________


2.設 m，n 為正整數，k = |12^m - 5^n |，
(1) 試證k不可能為5。
(2) 求k的最小值。


我想好久想不出來@@~感謝~

第 2 題
12^m 是偶數，5^n 是奇數，故 k 是奇數

(1) k = 1
12^m - 5^n = 1 or 12^m - 5^n = -1

12^m - 1 = 5^n
12^m - 1 是 11 的倍數，但 5^n 非 11 的倍數，不合

12^m + 1 = 5^n
m = 4k - 2 (k 為自然數) 時，12^m + 1 ≡ 5 (mod 10)
12^m + 1 = 144^(2k - 1) + 1 是 145 的倍數，但 5^n 不是 145 的倍數，不合

(2) k = 3
12^m - 5^n = 3 or 12^m - 5^n = -3
12^m 是 3 的倍數，但 5^n 非 3 的倍數，不合

(3) k = 5
12^m - 5^n = 5 or 12^m - 5^n = -5
5^n 是 5 的倍數，但 12^m 非 5 的倍數，不合

(4) m = n = 1 時，k = 7 為最小值

第 1 題
用類似樹狀圖可找到您提到的 10 個城市的解
且不可能再增加 1 個城市 K，因為前面 10 個城市都與某三個城市有直達航班了
換句話說，K 不能與這 10 個城市相連