[中學] 2011奧林匹亞試題一

[JohnMash (Paul)]

   試題分享


   給定整數 n > 0.
   有一個天平與 n 個重量分別為 2^0, 2^1, . . . , 2^{n-1} 的砝碼.
   現通過 n 步操作依次將所有砝碼都放上天平,
   使得在操作過程中,
   右邊的重量從未超過左邊的重量.
   每一步操作是從尚未放上天平的砝碼中選擇一個砝碼,
   將其放到天平的左邊或右邊,
   直到所有砝碼都被放上天平.

   求整個操作過程的不同方法個數.

--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 27.147.57.77
推 FAlin       :IMO_Taiwan 472篇有解法
   原來有這個版

推 justinj     :這題還不算難...f(n)=f(n-1)+(n-1)*2*f(n-1)
推 justinj     :f(n)=1*3*5*..*(2n-1)=(2n)!/(n!*2^n)
推 justinj     :看了一下它的寫法..我的想法是最後一次放時只要分成
→ justinj     :最重的及其它的..所以就有第一個等式..
推 justinj     :其實只要每個重量都是長2^k這種的,而重量都不一樣的
→ justinj     :m個...那方法數就一定是f(m)..例如2^0,2^2,2^5,...
   me too
※ 編輯: JohnMash        來自: 27.147.57.77         (04/03 09:56)