請問首尾兩間學校的最短距離是多少?

2013-01-20 9:03 am
有七間學校在同一條直線上,
彼此間的距離皆為整數,
而且從任兩間學校的距離就可以判斷是哪兩間學校,
也就是說任兩間學校的距離都不會重複。
請問首尾兩間學校的最短距離是多少?
請列出解題過程。
更新1:

例如有3間學校在同一條直線上依序分別為A、B、C。 A到B的距離為1;B到C的距離為2,則 知道距離為3則為A、C兩間學校; 知道距離為2則為B、C兩間學校; 知道距離為1則為A、B兩間學校。

更新2:

給麻辣大師: 1、2、3、4、5、6這組答案並不合題目的要求 若設七間學校依序為A、B、C、D、E、F、G 彼此間的距離依序為1、2、3、4、5、6 則A、C的距離為3,與C、D的距離是重複的; 另B、D的距離為5,與E、F的距離是重複的; A、D的距離為6,與F、G的距離是重複的。

更新3:

給sam大大: 此題的難在於似乎都有機會可以找出更好的解, 但都是經由不斷嘗試得到, 無法找到一個有系統的方法, 例如這組解2+3+6+1+13+4=29, 就比1+2+4+5+8+10=30來的好, 請sam大大幫忙再想想看~

回答 (2)

2013-01-23 7:02 am
✔ 最佳答案
2 + 1 + 7 + 6 + 5 + 4

最小25

暴力解法,沒有技巧

2013-01-22 23:02:42 補充:
2 + 1 + 7 + 6 + 5 + 4 = 25
1 + 3 + 6 + 8 + 5 + 2 = 25
2 + 5 + 6 + 8 + 1 + 3 = 25
1 + 6 + 4 + 9 + 3 + 2 = 25
1+ 10 + 5 + 3 + 4 + 2 = 25

所有兩兩之間距離 <= 10 的嘗試皆不存在 < 25 的結果
故最短距離為 25
2013-01-20 5:30 pm
設直線上七間學校依序為A、B、C、D、E、F、G,

且A、B距離為d1,B、C距離為d2,C、D距離為d3,D、E距離為d4,E、F距離為d5,F、G距離為d6

1、為使距離最小,設d1=1。
2、由條件知d2≠d1。為使距離最小,設d2=2。
3、由條件知d3≠d1≠d2≠d1+d2,即d3≠1≠2≠3。為使距離最小,設d3=4。
4、由條件知d4≠d1≠d2≠d3≠d1+d2≠d1+d2+d3≠d2+d3,即d4≠1≠2≠4≠3≠7≠6。為使距離最小,設d4=5。
5、由條件知d5≠d1≠d2≠d3≠d4≠d1+d2≠d1+d2+d3≠d1+d2+d3+d4≠d2+d3≠d2+d3+d4≠d3+d4,即d5≠1≠2≠4≠5≠3≠7≠12≠6≠11≠9。為使距離最小,設d5=8。
6、由條件知d6≠d1≠d2≠d3≠d4≠d5≠d1+d2≠d1+d2+d3≠d1+d2+d3+d4≠d1+d2+d3+d4+d5≠d2+d3≠d2+d3+d4≠d2+d3+d4+d5≠d3+d4≠d3+d4+d5≠d4+d5,即d6≠1≠2≠4≠5≠8≠2≠7≠12≠20≠6≠11≠19≠9≠17≠13。為使距離最小,設d6=10。

故最短距離為1+2+4+5+8+10=30。

2013-01-20 19:01:57 補充:
抱歉,考慮不周。

我想到另一種想法:
要使距離最小,必需能讓d1、d2、d3、d4、d5、d6儘可能的小。

先將3、4、5、6分解成相異數字的和,則有:

3=1+2…(1)
4=1+3…(2)
5=1+4=2+3…(3)
6=1+5=2+4=1+2+3…(4)


一、設若d1,d2,d3,d4,d5,d6為1,2,3,4,5,6六個數字的組合,
由(1)知1與2必不相鄰;(否則3不存在)
由(2)知1與3必不相鄰;(否則4不存在)
由(3)知1與4、2與3必不相鄰;(否則5不存在)
由(4)知1與5、2與4必不相鄰;(否則6不存在)

2013-01-20 19:02:35 補充:
由上述4條件只能排出序數(d1,d2,d3,d4,d5,d6)=(1,6,2,5,3,4)、(1,6,2,5,4,3)
但上述兩組解都有1+6=2+5與題意不合

故d1,d2,d3,d4,d5,d6不可能由1,2,3,4,5,6六個數字組成

2013-01-20 19:02:44 補充:
二、設若d1,d2,d3,d4,d5,d6中有五個數由1,2,3,4,5組成,

(Ⅰ)設若d1=1,則有序數(d1,d2,d3,d4,d5,d6)=(1,_,_,_,_,_)
由(1)知2必不與1相鄰,因此有(d1,d2,d3,d4,d5,d6)=(1,_,2,_,_,_)、(1,_,_,2,_,_)、(1,_,_,_,2,_)、(1,_,_,_,_,2)四種可能。

2013-01-20 19:03:03 補充:
 (Ⅰ.1)若(d1,d2,d3,d4,d5,d6)=(1,_,2,_,_,_),
 由(2)知3必不與1相鄰,因此有(d1,d2,d3,d4,d5,d6)=(1,_,2,_,3,_)、(1,_,2,_,_,3)  
 兩種可能。

2013-01-20 19:03:30 補充:
 (Ⅰ.1.1)若(d1,d2,d3,d4,d5,d6)=(1,_,2,_,3,_),
  由(3)可得(d1,d2,d3,d4,d5,d6)=(1,_,2,4,3,_)、(1,_,2,_,3,4)
 (Ⅰ.1.1.1)若(d1,d2,d3,d4,d5,d6)=(1,_,2,4,3,_),
   則有(1,5,2,4,3,_)、(1,_,2,4,3,5),再由條件驗算可得(1,5,2,4,3,10)、  
   (1,9,2,4,3,5)兩組解。和分別為25與24

2013-01-20 19:03:41 補充:
  (Ⅰ.1.1.2) 若(d1,d2,d3,d4,d5,d6)=(1,_,2,_,3,4)
則有(1,5,2,_,3,4)、(1,_,2,5,3,4),再由條件驗算可得(1,5,2,9,3,4)、(1,9,2,5,3,4)  
   兩組解。和分別為24

2013-01-20 19:04:01 補充:
在此提供思考方式給你,剩下的(Ⅰ.2)、(Ⅰ.3)、(Ⅰ.4)就留待大大自行計算囉。
不過看起來最小距離應為24

2013-01-20 19:47:34 補充:
還有(Ⅱ)即(_,1_,_,_,_)與(Ⅲ)即(_,_,1_,_,_)需討論。

另外因為6個數字彼此對稱,因此d4=1,d5=1,d6=1的情形不需討論。
(如d4=1與d3=1的情形是彼此對稱而相同的)…

2013-01-23 22:33:50 補充:
哈哈,我自己也算到頭昏

2013-01-23 22:34:34 補充:
哈哈,我自己也算到頭昏了,(1,5,2,9,3,4)、(1,9,2,5,3,4)有5+2=3+4,所以不合。Sorry~~

2013-01-23 22:39:11 補充:
謝謝khsdloflof大大提供的答案~~


收錄日期: 2021-04-27 20:04:03
原文連結 [永久失效]:
https://hk.answers.yahoo.com/question/index?qid=20130120000016KK00311

檢視 Wayback Machine 備份