アットランダム≒ブリコラージュ

18625：3以上の自然数での分割...

問題18625・・・やどかりさんのブログ https://blogs.yahoo.co.jp/oka_yadokary/38902473.html#38902473 より Orz〜

　例えば 10 は、 7＋3 ，6＋4 ，5＋5 ，4＋6 ，3＋7 ，4＋3＋3 ，3＋4＋3 ，3＋3＋4 と、

　３以上の自然数 ２個以上の和での表し方が 8 種類あります。

　では、23 は ３以上の自然数 ２個以上の和での表し方は 何種類？

解答

上記サイト https://blogs.yahoo.co.jp/oka_yadokary/38911014.html より Orz〜

[解答1]

　a，b，c，d，e，f，g を３以上の自然数とします。

　a＋b＝23 と表される場合 (a−2)＋(b−2)＝19 、

　a＋b＋c＝23 と表される場合 (a−2)＋(b−2)＋(c−2)＝17 、

　a＋b＋c＋d＝23 と表される場合 (a−2)＋(b−2)＋(c−2)＋(d−2)＝15 、

　a＋b＋c＋d＋e＝23 と表される場合 (a−2)＋(b−2)＋(c−2)＋(d−2)＋(e−2)＝13 、

　a＋b＋c＋d＋e＋f＝23 と表される場合 (a−2)＋(b−2)＋(c−2)＋(d−2)＋(e−2)＋(f−2)＝11 、

　a＋b＋c＋d＋e＋f＋g＝23 と表される場合 (a−2)＋(b−2)＋(c−2)＋(d−2)＋(e−2)＋(f−2)＋(g−2)＝9

　のように書き換えると、(　　　)内は自然数なので、

　₁₈Ｃ₁＋₁₆Ｃ₂＋₁₄Ｃ₃＋₁₂Ｃ₄＋₁₀Ｃ₅＋₈Ｃ₆＝18＋120＋364＋495＋252＋28＝1277 種類です。


[解答2]

　n は ３以上の自然数の和での表し方が １個だけの場合も和と認め、 a_n 種類とすれば、

　a₁＝a₂＝0 ，a₃＝1 で、n≧4 のとき、最後に加える数が 3，4，5，…… のそれぞれの場合の和を考え、

　a_n＝a_n-3＋a_n-4＋a_n-5＋……＋a₁ で、a_n-1＝a_n-4＋a_n-5＋……＋a₁ なので、a_n＝a_n-1＋a_n-3 です。

　a₄＝a₃＋a₁＝1 ，a₅＝a₄＋a₂＝1 ，a₆＝a₅＋a₃＝2 ，a₇＝a₆＋a₄＝3 ，a₈＝a₇＋a₅＝4 ，a₉＝a₈＋a₆＝6 ，

　a₁₀＝a₉＋a₇＝9 ，a₁₁＝a₁₀＋a₈＝13 ，a₁₂＝a₁₁＋a₉＝19 ，a₁₃＝a₁₂＋a₁₀＝28 ，a₁₄＝a₁₃＋a₁₁＝41 ，

　a₁₅＝a₁₄＋a₁₂＝60 ，a₁₆＝a₁₅＋a₁₃＝88 ，a₁₇＝a₁₆＋a₁₄＝129 ，a₁₈＝a₁₇＋a₁₅＝189 ，a₁₉＝a₁₈＋a₁₆＝277 ，

　a₂₀＝a₁₉＋a₁₇＝406 ，a₂₁＝a₂₀＋a₁₈＝595 ，a₂₂＝a₂₁＋a₁₉＝872 ，a₂₃＝a₂₂＋a₂₀＝1278 ですので、

　求める場合の数は、a₂₃−1＝1278−1＝1277 です。

*ごく普通の発想で...^^;v

23=3*7
so…
3が2〜7個
2H17=C(18,1)=18
3H14=C(16,2)=120
4H11=C(14,3)=364
5H8=C(12,4)=495
6H5=C(10,5)=252
7H2=C(8,6)=28
so…
18+120+364+495+252+28=1277

18624：証明...部分集合Ai U Aj=Akを満たす相異なるi,j,kが存在する...

問題18624・・・http://www.mathlion.jp/problem/pr117.html より 引用 Orz〜

解答

・わたしの...

1個だけ足りない集合の個数

例えば、1〜9だけで...

2^9-1個

残り2個には10が入ってる...

その2個から10を除いたものは、1〜9だけでできている集合のいずれかと同じものである...(鳩の巣原理)

{Ax}

{Az}={Ax+Aj}

{Ax+10}={Ai}

{Az+10}={Ak}

so...

{Ai++Aj}={Ax+10+Aj}={Az+10}={Ak}

みたいなことでいいのかしらん...?

↑

やはり怪しかったようで ^^; Orz...

↓

・鍵コメT様からのもの Orz〜

例えば1〜9しか使わない集合は，空集合以外には2^9-1通りありますが，
2^9+1個の集合を選ぶとき，2^9-1個すべてを選ぶとは限らないので，
選ぶことを前提とする議論では不完全だと思います．

「{1,2,…,n}の空でない部分集合で相異なるものが2^(n-1)+1個あるとき，
それらの内の異なる3つの集合X,Y,ZでX∪Y=Zを満たすものがある」…[*]
を数学的帰納法で示します．

[I] n=2のときは，{1,2}の空でない部分集合は{1},{2},{1,2}だけなので，
相異なる3個はこの3つすべてに限り，{1}∪{2}={1,2}より[*]は成立．

[II] n=kのときに[*]が成り立つと仮定してn=k+1のときを考える．
・k+1だけを要素とする集合が含まれない場合，
{1,2,…,k,k+1}の部分集合が2^k+1個あれば，
その内でk+1を要素に持つもの，持たないもののどちらかが2^(k-1)+1個あり，
帰納法の仮定から，[*]は成立する．
・k+1だけを要素とする集合が含まれる場合，
鳩の巣論法で，{1,2,…,k}の部分集合PとP∪{k+1}をペアにした組
(空集合と{k+1}の組を除く2^k-1組)の中で，
属する2つの集合がともに選ばれている組が存在し，
X={k+1},Y=P,Z=P∪{k+1}がX∪Y=Zを満たすから，[*]は成立する．

以上[I],[II]により，[*]は任意の2以上の整数nで成立する．

*熟読玩味ぃ〜^^;v