Re: [問題] IMO 2011 in Netherlands Day 2
※ 引述《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
推
07/20 00:21, , 1F
07/20 00:21, 1F
→
07/20 00:21, , 2F
07/20 00:21, 2F
→
07/20 00:22, , 3F
07/20 00:22, 3F
推
07/20 00:24, , 4F
07/20 00:24, 4F
討論串 (同標題文章)
本文引述了以下文章的的內容：
完整討論串 (本文為第 2 之 4 篇)：