Friday, March 8, 2013

奧林匹亞數學2012年第六題


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