6. 找出所有的N, 使得下面這個式子有(非負)整數解 (a1, a2, a3, ... ,aN)：
(左式) (右式)
N = 1 時顯然可以 (a1 = 0)
N = 2 時也行 (a1 = a2 = 1)
N = 3 無解
...
------------------------------------------------------------------------
這題相當困難，全世界五百名選手只有十個人全對。(會讓我想三個月不是沒有原因的)
為求討論的方便我把二的次方和等於1這個條件叫做左式，三的次方和等於1叫做右式。
首先，做數學就是從小數字開始，所以上面那個 N = 1, N = 2, N = 3已經是提示了。很快就會發現 N = 1, 2 是可以的，但3, 4都是無解的。在尋找解答的時候，會自然去想到底左式會有怎麼樣的解。N=3時，(a1, a2, a3) 只能是 (1, 2, 2)，所以很快可以證明右式是無解的。N=4時，(a1, a2, a3, a4)可以是(2, 2, 2, 2)或(1, 2, 3, 3)，加上排列各有1和 12種可能, 幾個簡單的試驗就可以知道也是無解。
N=5的時候, 連左式也看起來越來越複雜了。所以我停下來去想左式是否有公式化的解答。在處理左式時由於次序並不影響總和我們可以假定 a1 <= a2 <= a3 <= .... <= aN。不難想出左式的最高次方不可能獨立存在，也就是a(N-1) = aN，否則總和不可能是整數。也因此對於任何一個N的解我們可以把最後兩項合併得到一個N-1的解。相對來說，任何一個N的解都必須是從N-1的解挑選一項"分裂"所得。分裂時次方要加1，也就是1/ 2^k分裂成 1/2^(k+1) + 1/2^(k+1)。(2, 2, 2, 2)分裂一項一定是(2, 2, 2, 3, 3) ，而(1, 2, 3, 3)可以有分裂1, 2或3三種選擇，得到(2, 2, 2, 3, 3), (1, 3, 3, 3, 3)和(1, 2, 3, 4, 4)三種答案。扣除重複後左式有三組解(不計次序)：(1, 2, 3, 4, 4), (1, 3, 3, 3, 3), (2, 2, 2, 3, 3)，經不同排列試驗後，可得：
1 1 1 1 1 1 2 3 4 5
--- + --- + --- + --- + --- = --- + --- + --- + --- + --- = 1
1 2 3 4 4 2 1 3 4 4
2 2 2 2 2 3 3 3 3 3
No comments:
Post a Comment