這道智力題能夠用數學方法求解或證明嗎？

01-17

有這樣一道智力題：

給定五個數，{1, 2, 3, 4, 5}，定義如下操作：

從五個數中任意選擇兩個數

求兩數之和及之差（始終以大減小，結果非負）

以它們的和及差替代原來選擇的兩個數

例如：
1 2 3 4 5 (1,3) =&> (2,4)
Output: 2 2 4 4 5
重複上述操作，直到五個數全部相等。
問：能得到的最小的結果是多少？

經過嘗試，可以找到正確答案；也可以通過編程搜索出正確答案。但是，沒有數學上的解釋，總覺得不滿意。考慮很久，沒有很好的思路。特此求教！

數學上的解釋在此！

答案是8沒錯，而且可以給出一個更為普適的結論：

給定n個數{1, 2, ……, n}，記能得到的最小結果為m。

當 $2^{k}<nleq 2^{k+1}$ 時， $m=2^{k+1}$ $(kgeq 1)$ 。（感謝 @qfzklm提出的猜想）

證明分為2.000000001步：

1、證明m沒有異於2的質因數，即 $exists qepsilon N^{*} s.t.m=2^{q}$ 。

1.000000001、因為m顯然大於n，所以有 $mgeq 2^{k+1}$ 。

2、給出使 $m=2^{k+1}$ 操作的構造性證明。

關於 $exists qepsilon N^{*} s.t.m=2^{q}$ 的證明：

定義逆操作：

從n個數中任意選擇奇偶性相同的兩個數；
求兩數之和及之差（始終以大減小，結果非負）
以它們的和的二分之一及差的二分之一替代原來選擇的兩個數

用操作將1,2,...,n變為m,m,...,m的過程可視作等價於用逆操作將m,m,...,m變為1,2,...,n。

可知如果選擇的兩數存在異於2且為質數的公因子p，在每一次逆操作後，替代的兩個數扔然都可以被p整除。

如果m擁有異於2的質因數p，那麼所有由m,m,...,m進行有限次逆操作得到的結果，必定滿足所有數都可以被p整除。

顯然1,2,...,n不具有這種性質，因此m,m,...,m不能經過有限次逆操作變為1,2,...,n，即1,2,...,n不能通過有限次操作變為m,m,...,m。

假設不成立，則 $exists qepsilon N^{*} s.t.m=2^{q}$ 恆成立。

構造性證明如下：

當 $k=1$ 時， $n=3$ 或 $n=4$ ，結論顯然。

若當 $kleq i$ 時結論成立，下證當 $k=i+1$ 時亦成立。

當 $2^{i+1} <n<2^{i+2}$ 時，對所有大於 $2^{i+1}$ 的數 $p_{j} =2^{i+1}+j (j=1,2,...,n-2^{i+1} )$ ，選擇 $p_{j}$ 和 $2^{i+2}-p_{j}$ 進行操作，得到 $2,4,...,2(n-2^{i+1} )$ 和 $n-2^{i+1}$ 個 $2^{i+2}$ 。剩下的數是 $1,2,...,2^{i+1}-1-(n-2^{i+1} )$ 和一個 $2^{i+1}$ 。

其中， $2^{i+1}-1-(n-2^{i+1})<2^{i+1}$ ，故 $1,2,...,2^{i+1}-1-(n-2^{i+1} )$ 可以通過有限次操作全變成 $2^{i+1}$ ；

$2^{i+1}$ 本身就是不用變了；

$2,4,...,2(n-2^{i+1} )$ 每個都先除以2，變成 $1,2,...,n-2^{i+1}$ ，由於 $n-2^{i+1} <2^{i+2} -2^{i+1}=2^{i+1}$ ，故這些也可以通過有限次操作全變成 $2^{i+1}$ ，把2都乘回去就全變成 $2^{i+2}$ 。

那些 $2^{i+1}$ 怎麼變 $2^{i+2}$ 我是知道的，可惜地方太小寫不下了。

原來還是能騰出地方來的......
簡單說一下，除了 $n=2^{i+2} -1$ 的情況下，我們手裡是有兩個或以上的 $2^{i+1}$ 的，任取兩個變成0和 $2^{i+2}$ ，再取0和一個 $2^{i+1}$ 變成兩個 $2^{i+1}$ ，這兩次操作結果上就是將一個 $2^{i+1}$ 變成了 $2^{i+2}$ ；一直重複下去直到還有兩個 $2^{i+1}$ 的時候，取兩個 $2^{i+1}$ 變成0和 $2^{i+2}$ ，再取0和一個 $2^{i+2}$ 就將所有的 $2^{i+1}$ 變成了 $2^{i+2}$ 。
那麼現在問題來了，挖掘......啊不不不，是當 $n=2^{i+2} -1$ 的情況，這時候我們手裡只有一個 $2^{i+1}$ ，所幸 $2,4,...,2(n-2^{i+1} )$ （當 $n=2^{i+2} -1$ 時就是 $2,4,...,2(2^{i+1} -1)$ ）這裡面還有一個。
那麼現在問題又來了，借走了一個 $2^{i+1}$ 之後， $2,4,...,2(2^{i+1} -1)$ 還能不能按照上面的方法變成 $2^{i+2}$ 的問題。從上面的方法我們可以看出，這依賴於 $1,2,...,2^{i+1} -1$ 在去掉 $2^{i}$ 這個中間項之後能否都變成 $2^{i+1}$ 的問題。
事實上，我們正巴不得擺脫那個中間項呢，從「挖掘」倆字到這裡的這麼多字就是為了處理那個多出來的中間項，把上面的論證過程里的下表稍微修改一下就能證明， $1,2,...,2^{i+1} -1$ 在去掉 $2^{i}$ 以後可以相當簡單地全變成 $2^{i+1}$ 。

逗B時間結束，總之還是可以的。

當 $n=2^{i+2}$ 時就更沒問題了。

綜上，對任意正整數 $k$ ，當 $2^{k}<nleq 2^{k+1}$ 時，m不超過 $2^{k+1}$ 。

即m= $2^{k+1}$ ，□。

====原答案（比 @Dawn 的方法要糙很多，不過對上面普適證明提供了思路）====

不請自來，隨便從結果往前逆推

xxxxx

xxxx0

1、
xxx00

（1）
xx000

1. x0000

2. x(0.5)(0.5)00

（2）
xx(0.5)(0.5)0

1. x(0.5)(0.5)00

2. xx(0.5)00

3. x(0.5)(0.5)(0.5)(0.5)

4. xx(0.5)(0.25)(0.25)

5. x(0.75)(0.5)(0.25)0

2、
xxx(0.5)(0.5)

（1）
xx(0.5)(0.5)0

1. x(0.5)(0.5)00

2. xx(0.5)00

3. x(0.5)(0.5)(0.5)(0.5)

4. xx(0.5)(0.25)(0.25)

5. x(0.75)(0.5)(0.25)0

（2）
xxx(0.5)0

1. xx(0.5)00

2. xx(0.5)(0.5)(0.5)

3. xxx(0.25)(0.25)

4. xx(0.75)(0.25)0

（3）
xx(0.75)(0.5)(0.25)

1. x(0.75)(0.5)(0.25)0

2. x(0.875)(0.5)(0.25)(0.125)

3. x(0.75)(0.75)(0.25)(0.25)

4. x(0.75)(0.625)(0.5)(0.375)

5. xx(0.625)(0.375)(0.125)

6. xx(0.5)(0.5)(0.25)

7. xx(0.75)(0.375)(0.125)

可以看出如果x為奇數，那麼它應不小於15（因為五數之和在在操作後是不減的）；

而五數之中的最大值是不減的，因此x不小於5

下證必不等於6：

反設x=6，

必須有一次1和5的操作，在這次操作中五數之和增加了4；

4隻能和1或2一起操作，每次操作至少使五數之和增加2，而含有4的操作至少有2次（初始一個，1和5產生一個），故含有4的操作會使五數之和至少增加4；

最後一步一定是0和6的操作，五數之和至少增加6；

如果沒有3和3的操作只會變成x0000型，而這時的x不小於15，不可能等於6，所以一定有一次3和3的操作，五數之和增加3；

上述必要操作使五數之和至少增加了17，五數之和至少變為32大於30，矛盾。

因此只要構造出x=8的方法即可證明這是最小的。

(1,2,3,4,5)

(1,2,2,4,8)

(1,2,3,4,8)

(2,2,4,4,8)

(0,4,4,4,8)

(4,4,4,4,8)

(0,8,4,4,8)

(0,0,8,8,8)

(0,8,8,8,8)

(8,8,8,8,8)

嘗試一些情況之後，無責任猜想：

對於集合{1,2,3,...，n}，施加上述操作後最終得到集合{m,m,m,...,m}，其中m的最小可能值：

n=1，trivial，m=1。

n=2，無解。

當 $2^{k}< n leq2^{k+1}$ 時， $m=2^{k+1}$ 。

可以構造性地證明，m不超過 $2^{k+1}$ 。不過m不小於 $2^{k+1}$ 這個部分怎麼弄還不知道。。。

不過為了證明寫起來方便，還是利用歸納假設好了。

假設 $2^{k-1}<nleq 2^{k}$ 時，可以將集合 { 1, 2, 3, ..., n }，變成 { 2^k, 2^k, 2^k, ..., 2^k }。

這個可以根據{1,2,3}和{1,2,3,4}進行驗證。

注意：

集合{1,2}在根據需要時，可以變成{ 2^k, 2^(k+1)}。

集合{2^k, 2^k, 2^k, ..., 2^k}可以變成 {2^(k+1), 2^(k+1), 2^(k+1), ..., 2^(k+1)}。

1. 將集合 { 1, 2, 3, ..., n } 分為兩組 { 1, 2, 3, ..., 2^k } 和 { 2^k + 1, 2^k + 2, 2^k + 3, ..., n }

2. 分別對 { 2^k - 1, 2^k + 1 }, { 2^k - 2, 2^k + 2 }, { 2^k - 3, 2^k + 3 } 等等施加操作，然後就會得到一系列數 { 2, 2^( k + 1) }, { 4, 2^( k + 1) }, { 4, 2^( k + 1) } 等等。。

3. 重新整理這些數，這些數可以分成三個部分，分別得到集合 { 1, 2, 3, ..., s } 和 2*{ 1, 2, 3, ..., 2^k - s } 和 { 2^( k + 1), 2^( k + 1), 2^( k + 1), ..., 2^( k + 1)}。

注意到最後一部分已經達到 2^( k + 1) 了，而且s&<2^k。

4. 那麼那集合{ 1, 2, 3, ..., s }可以最終變成 { 2^k, 2^k, 2^k, ..., 2^k }。集合 2*{ 1, 2, 3, ..., 2^k - s } 則最終變成 2*{ 2^k, 2^k, 2^k, ..., 2^k }，即{ 2^( k + 1), 2^( k + 1), 2^( k + 1), ..., 2^( k + 1)}。

5. 將集合{ 2^k, 2^k, 2^k, ..., 2^k } 變成 { 2^( k + 1), 2^( k + 1), 2^( k + 1), ..., 2^( k + 1)}。

結束。

更新：

大家可以去看 @吳一塵的答案，他給出了m的形式，一定是2^q這樣的形式。那麼基於他的結論，就可以給出m的下限，正好就是2^(k+1)。至此，整個經過推廣化的命題已經完全被證明了。

@吳一塵的證明思路簡述一下。

（反證法）考慮逆向的操作，從{m,m,m,...,m}出發退回{1,2,3,...,n}。如果m包含異於2的質因數p，那麼從集合{m,m,m,...,m}出發進行的逆向操作得到的集合中，其每個元素都一定包含質因數p。在經過有限次逆向操作後，不可能得到{1,2,3,...,n}這樣的集合。那麼要得到{1,2,3,...,n}這樣的集合，m一定不包含異於2的質因數，m一定只能取2^q這樣的形式。

注意到m一定不小於n，那麼對於2^k&

m=2^(k+1)