YLL討論網

將一至n的正整數重新排成一列，使任何兩個相鄰的正整數的和都是完全平方數，則n的最小值是多少？

n最小值是16
排法為
16,9,7,2,14,11,5,4,12,13,3,6,10,15,1,8
要證明嗎
就其他的排不出來囉

證明我也不會,不過16是可以去掉的
所以最小值應該是15

http://www.mathland.idv.tw/board/memo.asp?srcid=10507&bname=ASP

折服
15是對的

可以排成
8,1,15,10,6,3,13,12,4,5,11,14,2,7,9
至於可不可以再小
需要想一下

不過說真的我也很笨
之前那個16可以直接拿掉也不會影響答案
16本身就是一個完全平方數

我個人是覺得8,9是一個關鍵
如果15是目前可以找到最小的n
那8要去湊一個完全平方數就只能跟1配(總不行再有1個8去配16)
9要去湊一個完全平方數就只能跟7配
所以8,9一定是放在數列的端邊(在n<15的情況下)

來討論能不能比15小
從8,1,....,7,9來討論
1要湊成完全平方數需配合3或8或15
在8已經用的情況下
要使n減少(比15小),那下一個必須為3
得8,1,3,...,7,9

同理3的下一個就必須為(1)6或(2)13(不能找大於或等於15的數)

(1)6的情況(8,1,3,6...,7,9)
下一個只有10,再來就必須為6或15囉,此時矛盾

(2)13的情況(8,1,3,13,...,7,9)
下一個只有12的可能(3被用掉了)
可得8,1,3,13,12,....,7,9
下一個必須為4(13被用掉了)
得8,1,3,13,12,4,....,7,9
下一個必須為5(12用掉了)
得8,1,3,13,12,4,5,..,7,9
下一個必須為11(4用掉囉)
得8,1,3,13,12,4,5,11,...,7,9
下一個必須為14(5用掉)
8,1,3,13,12,4,5,11,14,...,7,9
下一個必須為2
8,1,3,13,12,4,5,11,14,2,...,7,9
下一個必須為7或14,得矛盾(14已用過,若用7則就必須結束數列,那6跟10就不會出現)

綜合以上,所以15是最小的n
這樣的證明應該還算嚴謹吧

寫這麼多才賺一點點y幣
早知道拆成好幾份

這題....好像也只能用這種算法了....

不然就是把每個數能配的數列出來....

1:3,8,15....
2:7,14....
3:1,6,13....
4:5,12....
5:4,11....
6:3,10....
7:2,9....
8:1....
9:7....
10:6,15....
11:5,14....
12:4,13....
13:3,12....
14:2,11....
15:1,10....

如只能配1個數字的話....必為頭或尾....

若將範圍縮小....出現超過2個只能配1個數字的項目....此範圍必不合....

所以....1~15為最小範圍=.=....

真難證....

網友提供的題目出處

100          回覆於: 2004/11/2 上午 11:45:51                        

-------------------------------------------------------------
2003亞洲城市青少年數學邀請賽
初中組第一試 2003/8/6 10:30-12:00 中國福州一中
填充題(每題10分)
9.將1至n的正整數(n>1)重新排成一列，使任何兩個相鄰的正整數之和都是完全平方
數，則n的最小值是　　　　。

沒錯！我當時也是算15。

不會ar~
笨 ..............