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^2$ （ $2^{2n}$ でもあります）となることが予想できます．
　一般化は次のようになります．

　正整数 $n$ に対し， $m=2^n$ ， $S=\{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」に置き換えました）

*1:https://en.wiktionary.org/wiki/oddify

わさっきhb

大学（教育研究）とか，親馬鹿とか，和歌山とか，とか，とか．

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