わさっきhb

大学(教育研究)とか ,親馬鹿とか,和歌山とか,とか,とか.

8個の数の和を工夫して求めよう

 いきなりですが問題です.

 9+10+11+12+13+14+15+16は?

 さっそくですが解答です.等差数列の和の公式を使いましょう.初項9,末項16,項数8ですから,\displaystyle\frac{8(9+16)}{2}4\cdot25=100となります.
 小学校の算数なら,「10をつくる」のがよさそうです.この場合,9+10+11+12+13+14+15+16=10+(9+11)+(14+16)+(12+13+15)=10+20+30+40=100です.
 次にですが問題です.oはoddify*1の頭文字です.それと整数でよく使う文字は,nやmですが,それらはあとで使用するため,ここではxにしています.

 任意の正整数xに対し,2で割り切れなくなるまで割って,最終的に得られる値をo(x)と書きます.与えられた数xが奇数のときは,o(x)=xです.例えばo(6)=3,o(7)=7,o(8)=1です.
 9≦x≦16の各整数xに対するo(x)を求めなさい.

 表にします.

x 9 10 11 12 13 14 15 16
o(x) 9 5 11 3 13 7 15 1

 さらにですが問題です.

 9≦x≦16の各整数xに対するo(x)の総和を求めなさい.

 9+5+11+3+13+7+15+1ですが,これは項を並べ替えると1+3+5+7+9+11+13+15となります.等差数列の和の公式(初項1,末項15,項数8)から,64と求められます.wikipedia:平方数に書かれた「1から連続する正の奇数の総和は平方数に等しい」を用いると,8×8の点の並びがイメージできますので,やはり,64です.
 某年月日,子らの授業参観に出席しました.うえの子(5年)のクラスは算数で,oという関数は出現しなかったものの,上記の操作を行い,総和を求めるものでした.自力解決の時間を小刻みにとりながら,教室の子どもたちは解答していました.
 さて,並べ替えることで「1から連続する正の奇数」になるのは少々不思議なところです.そこで問題です.

 ここまでの計算を一般化しなさい.

 「9≦x≦16」は,2つの整数値で挟んだ形ですが,実は1つの定数値を使って,表現できます.n=3とおきます.そして表記を簡単にするために,m=2^nとしますと,xの範囲はm+1\le x\le 2mと表せます.
 そして\{o(x)\mid m+1\le x\le 2m\}という集合を考え,その要素の和を求めるものとします.結果ですが,n=3のときは64ですので,任意の正整数nにおいては,m^22^{2n}でもあります)となることが予想できます.
 一般化は次のようになります.

 正整数nに対し,m=2^nS=\{o(x)\mid m+1\le x\le 2m\}としたとき,以下が成り立つ.

  • S=\{2k-1\mid 1\le k\le m\}.言い換えると,Sは,1から連続するm個の奇数からなる集合である.
  • \displaystyle\sum S=2^{2n}

 具体的なnの値で成立することを確かめるため,Rubyワンライナーを作りました.nが1から4までのときのコマンドと実行結果は次のとおりです.

$ ruby -e 'def o(x);while x%2==0;x/=2;end;x;end;n=(ARGV[0]||3).to_i;m=2**n;a=((m+1)..(m*2)).to_a;b=a.map{|i|o(i)};c=b.sort;puts a.inspect,b.inspect,c.inspect,c.sum' 1
[3, 4]
[3, 1]
[1, 3]
4
$ ruby -e 'def o(x);while x%2==0;x/=2;end;x;end;n=(ARGV[0]||3).to_i;m=2**n;a=((m+1)..(m*2)).to_a;b=a.map{|i|o(i)};c=b.sort;puts a.inspect,b.inspect,c.inspect,c.sum' 2
[5, 6, 7, 8]
[5, 3, 7, 1]
[1, 3, 5, 7]
16
$ ruby -e 'def o(x);while x%2==0;x/=2;end;x;end;n=(ARGV[0]||3).to_i;m=2**n;a=((m+1)..(m*2)).to_a;b=a.map{|i|o(i)};c=b.sort;puts a.inspect,b.inspect,c.inspect,c.sum' 3
[9, 10, 11, 12, 13, 14, 15, 16]
[9, 5, 11, 3, 13, 7, 15, 1]
[1, 3, 5, 7, 9, 11, 13, 15]
64
$ ruby -e 'def o(x);while x%2==0;x/=2;end;x;end;n=(ARGV[0]||3).to_i;m=2**n;a=((m+1)..(m*2)).to_a;b=a.map{|i|o(i)};c=b.sort;puts a.inspect,b.inspect,c.inspect,c.sum' 4
[17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32]
[17, 9, 19, 5, 21, 11, 23, 3, 25, 13, 27, 7, 29, 15, 31, 1]
[1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25, 27, 29, 31]
256

 nの値は,コマンドの最後に指定し,途中の「n=(ARGV[0]||3).to_i」で整数値にしています.aは\{x\mid m+1\le x\le 2m\},bは\{o(x)\mid m+1\le x\le 2m\}に対応する,数の順序付けられた並びです.そしてcは,bの要素を昇順で並び替えたもので,一般化のところで書いた「1から連続するm個の奇数」になっています.nの値にかかわらず出力は4行で,順に,a,b,c,そして総和です.
 4以下のnについては,一般化で述べた命題が成り立っているのが分かります.
 S=\{2k-1\mid 1\le k\le m\}が一般に成り立つことを証明するには,これらの出力の2行目,変数bに格納される値に着目します.例えばn=3とn=4の場合を比較すると,[17, 19, 21, 23, 25, 27, 29, 31](n≦3にはなくn=4のときに出現し,もとから奇数のためx=o(x)となる値を,昇順で並べたもの)と,n=3のときのbとを,1つずつ交互に並べてできる配列が,n=4のときのbになっています.n=hとn=h+1の関係に置き換え,hに関する数学的帰納法により,証明できそうです.

(最終更新:2020-02-09 夕方.LaTeXにおける正しい論文の書き方 - Qiitaを読み,tex記法の中の「|」を「\mid」に置き換えました)