OSを作ってみよう (534ﾚｽ)
上下前次1-新
234: LightCone ◆sSJBc30S5w 03/03/21 09:55 AAS
証明1
(i) 今、Aの要素からm個の要素を選んだ集合をB(m)とし、Sum(B(m)) > 2^n と仮定する。
B(m)の要素のうち、最小の要素を2^kとすると、Sum(B(m))は、2^kの倍数だから、自然数Lを用いて、Sum(B(m))=L･2^kと表せる。
B(m)から、2^kを一つ取り除いた集合をB(m-1)とすると、Sum(B(m-1))=Sum(B(m))-2^k=(L-1)・2^k である。
ところで、定理の仮定より、2^k < 2^n であるから、2^n は、2^k の倍数である。
ところが、2^kの倍数であるSum(B(m))に一番近くてSum(B(m))より小さい2^kの倍数がSum(B(m-1))であるから、2^nは、Sum(B(m-1))と等しいか小さくなくてはならない。
つまり、2^n <= Sum(B(m-1)) < Sum(B(m)) という関係が成り立つ。
(ii) 今、集合Aそのものも、B(m)の条件を満たす事に注意する。
もし、Sum(B(m-1)) > 2^n であるならば、(i)のB(m)を、B(m-1)に置き換えて議論を繰り返すと、2^n <= Sum(B(m-2)) < Sum(B(m-1)) が言えて、いつか必ず、2^n=Sum(B(p)) となるような自然数pが存在しなくてはならない事が分かる。
この集合B(p)が、定理の条件を満たすAの要素の組み合わせである。(Q.E.D. by LightCone)
上下前次1-新書関写板覧索設栞歴
あと 300 ﾚｽあります
ｽﾚ情報 赤ﾚｽ抽出 画像ﾚｽ抽出 歴の未読ｽﾚ AAｻﾑﾈｲﾙ
ぬこの手 ぬこTOP 0.004s