※ 引述《present (情場殺手)》之銘言： : 問題4. : 給定整數n>0。有一個天平與n個重量分別為2^0,2^1,...,2^(n-1)的砝碼。 : 現通過 n步操作依次將所有砝碼都放上天平， : 使得在操作過程中，右邊的重量從未超過左邊的重量。 : 每一步操作是從尚未放上天平的砝碼中選擇一個砝碼， : 將其放到天平的左邊或右邊，直到所有琺碼都被放上天平。 : 求整個操作過程的不同方法個數。 假設 n 個砝碼的方法數是A_n 此時我們考慮把2^0先去掉 剩下的n-1個砝碼可以是的方法數就是A_(n-1) 再把2^0加回來 首先如果是擺在第一個，那剩下的砝碼依然就是A_(n-1) 如果不是擺在第一個，注意到一個關鍵，這個法碼不管擺在左邊或右邊 都依然使右邊不超過左邊(簡單的冪次性質) 所以這後面n-1個位置，每個都有兩種放法 也就是2(n-1) * A_(n-1) 所以 A_n = (2n-2 + 1) * A_(n-1) 而 A_1 = 1 所以 A_n = (2n-1)!! : 問題5. : 設f是一個定義在整數集上，取值為正整數的函數。 : 已知對任意兩個整數m,n，差f(m)-f(n)能被f(m-n)整除。 : 證明：對所有整數m,n，若f(m)≦f(n)，則f(n)被f(m)整除。 取 (m,n) = (m,0) → f(m) | f(m) - f(0) ∴ f(m) | f(0) 取 (m.n) = (0,n) → f(-n) | f(0) - f(n) ∴ f(-n) | f(n) 取 (m.n) = (0,-n) ∴ f(n) | f(-n) ∴ f(n) = f(-n) 以下採用反證法，如果 f(m) < f(n) 則 f(m) 不整除 f(n) 取 (m.n) = (m,-n) ∴ f(m+n) | f(m) - f(-n) = f(m) - f(n) ∴ f(m+n) ≦ f(n) - f(m) 取 (m.n) = (m+n,n) ∴ f(m) | f(m+n) - f(n) ∵ f(m) 不整除 f(n) ∴ f(m) 不整除 f(m+n) ∴ f(m) - f(m+n) ≠ 0 取 (m.n) = (m+n,m) ∴ f(n) | f(m+n) - f(m) ∵ f(m) - f(m+n) ≠ 0 可分成以下兩種狀況討論 (1) f(n) ≦ f(m+n) - f(m) 則 f(n) ≦ f(m+n) - f(m) ≦ [ f(n) - f(m) ] - f(m) = f(n) - 2f(m) 矛盾 因為f是整數對應到"正整數" (2) f(n) ≦ f(m) - f(m+n) 把此式與 f(m+n) ≦ f(n) - f(m) 相加 f(n) + f(m+n) ≦ f(n) - f(m+n) 矛盾，理由同上 --

※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 219.80.132.131