|
問題2638・・・ひよこさんのサイト http://myhome.cururu.jp/gersdorffite/blog/article/71002233837 より Orz〜
D = { 2^n ； n≧0 （n∈Z) } とするとき、
100をＤのいくつかの要素の和として表現する方法は何通りあるか。
* たとえば、 7をDの要素の和で表現するとき、
7 = 2＾2＋2＾1＋2＾0
7 = 2＾2＋2＾0＋2＾0＋2＾0
7 = 2＾1＋2＾1＋2＾1＋2＾0
7 = 2＾1＋2＾1＋2＾0＋2＾0＋2＾0
7 = 2＾1＋2＾0＋2＾0＋2＾0＋2＾0＋2＾0
7 = 2＾0＋2＾0＋2＾0＋2＾0＋2＾0＋2＾0＋2＾0
このように6通りある。
解答
既出問かも...^^; Orz〜
上記サイトより Orz〜
・ひよこさんからのヒント
ひとつの方法としては、次に定めるような関数fを考えるというのがあります。
f_k(n) = （nを2^k以下の2の巾の和で表現する場合の数）
たとえば、f_0(7)=1, f_1(7)=4, f_2(7)=6 です。
・スイーツさんのもの Orz〜
f_0(n)=1
f_1(2n)=f_1(2(n-1))+f_0(2n)=f_1(2(n-1))+1
f_1(2n)=f_1(2)+?_[i=2,n]1=n+1
f_2(4n)=f_2(4(n-1))+f_1(4n)=f_2(4(n-1))+(2n+1)
f_2(4n)=f_2(4)+?_[i=2,n](2i+1)=(n+1)^2
f_3(8n+4)=f_0(8n+3)+f_1(2(4n+1))+f_2(8n)+f_3(8n-4)
=f_3(8n-4)+4(n+1)^2
f_3(8n+4)=f_3(4)+?_[i=1,n]4(i+1)^2=(2/3)(n+1)(n+2)(2n+3)
f_4(16n+4)=f_4(16(n-1)+4)+f_3(16n+4)
f_4(16n+4)=f_4(4)+?_[i=1,n]f_3(16i+4)
=(2/3)(n+1)(n+2)(2n+1)(2n+3)
求める場合の数=f_6(100)=f_6(36)+f_5(68)+f_4(100)
f_6(36)=f_5(36)=f_5(4)+f_4(36)=4+f_4(36)
f_5(68)=f_5(36)+f_4(68)=(4+f_4(36))+f_4(68)
求める場合の数=8+2*f_4(36)+f_4(68)+f_4(100)
f_4(36)=280, f_4(68)=1980, f_4(100)=7280
求める場合の数=9828
（注意）
f_4(36), f_4(68), f_4(100) はそれぞれ、
f_4(16n+4)=(2/3)(n+1)(n+2)(2n+1)(2n+3) に
n=2, 4, 6を代入して求めている。
・否定する者さんのもの Orz〜
nをDの要素で表す方法の総数をA(n)と書くとき、次がいえる。
以下、N*を正整数全体として、Nを非負整数全体とする。
「任意のn∈Z*に対して、以下が成立する。
A(2n+1)=A(2n), A(2n+2)=A(2n+1)+A(n+1)」 ・・・(＊)
（実はn=0のときにも成立するが、これは都合上の問題）
これを使えば、A(1)=1からスタートして、
A(2)=A(1)+A(1)=2, A(3)=A(2)=2, A(4)=A(3)+A(2)=2+2=4
というように順序機械的に求めていくことができる。
（A(100)だけを算出するときに都合が良いというわけではないけど、
コンピュータで順序的に計算していくには適していると思う）
(*)を証明したいとおもう。
正整数nを任意に固定する。
次のように集合A,B,Cを定める。
以下、akなどはa_kを略記しているものと判断してほしい。
そうすると、ak-1などはどう判断するかという問題になるが、
そのようなときは、a_(k-1)の略記であると判断してほしい。
また、a_k-1を記述したいときは、-1+akと書くことにする。
・A(2n+2)=A(2n+1)+A(n+1) を示す。
A:=｛(a1,a2,...,ak)|Σ_[i=1,k]2^(ai)=2n+2, a1≧a2≧...≧ak, ∀ai∈N, k∈N*｝
B:=｛(a1,a2,...,ak)|Σ_[i=1,k]2^(ai)=2n+1, a1≧a2≧...≧ak, ∀ai∈N, k∈N*｝
C:=｛(a1,a2,...,ak)|Σ_[i=1,k]2^(ai)=n+1, a1≧a2≧...≧ak, ∀ai∈N, k∈N*｝
示したいことは、|A|=|B|+|C| の成立である。
B∩C = φ であることはすぐわかるので、
AからB∪Cへの全単射の存在がいえればよい。
実は、次のようにAからB∪Cへの写像fを定めることができて、
そのとき、fが全単射であることを示すことができるといえる。
[fの定義]
(a1,a2,...,ak)∈A に対して、
f(a1,a2,...,ak) = (a1,a2,...,ak-1) （aiが全て1以上でないとき）
f(a1,a2,...,ak) = (-1+a1,-1+a2,...,-1+ak) （aiが全て1以上であるとき）
fはwell-definedであり、全単射であるといえる。（確認容易故略）
・A(2n+1)=A(2n) を示す。
次のように集合D,Eを定める。
D:=｛(a1,a2,...,ak)|Σ_[i=1,k]2^(ai)=2n+1, a1≧a2≧...≧ak, ∀ai∈N, k∈N*｝
E:=｛(a1,a2,...,ak)|Σ_[i=1,k]2^(ai)=2n, a1≧a2≧...≧ak, ∀ai∈N, k∈N*｝
示したいことは、 |E|=|D| の成立である。
EからDへの全単射の存在がいえればよい。
実は、次のようにEからDへの写像gを定めることができて、
そのとき、gが全単射であることを示すことができるといえる。
[gの定義]
(a1,a2,...,ak)∈E に対して、
g(a1,a2,...,ak) = (a1,a2,...,ak,0)
gは明らかにwell-definedであり、
これが全単射であることを確認するのはfより容易である。
着いていけてないわたし...^^;
熟読玩味...
|
コメント（0）
