※ 引述《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