2984 の証明

今日は 29 日ということで。合ってるかどうかは知らない。

[補題 1] 任意の正整数 n について、J(2n) = 2J(n) - 1 かつ J(2n+1) = 2J(n) + 1
[証明]
前者を示す。人数が偶数 2n の場合、1 巡目で偶数番目の人が除かれ、n 人だけ残る。2 巡目以降で最後まで生き残るのは、1 巡目で残った人の中で J(n) 番目の人となる。したがって J(2n) = 2J(n) - 1 である。
後者を示す。人数が奇数 2n+1（≧ 3）の場合、1 巡目で偶数番目の人が除かれ、n+1 人だけ残る。2 巡目では、残った人のうち最初の人がまず除かれる。その状態から始めて J(n) 番目の人が最後まで生き残ることになるから、J(2n+1) = 2J(n) + 1 が成り立つ。

2984 関数 J を、整数上の関数ではなく、2 進表現された文字列上の関数だと思ったものを K とする。すなわち、正整数 n に対し、n を 2 進表記した文字列を [n] と書くこととし（[n] の最初の文字は '0' ではないとする）、K([n]) = [J(n)] と定める。
また、[ ] の逆変換を < > と書く。つまり <[n]> = n。
さらに、#(w) を、文字列 w の先頭にある '0' の並びを削除したものとする。たとえば #(0011101) = 11101 となる。

[補題 2] {0,1} 上の任意の文字列 w について、K(1w) = #(w1)
[証明]
w の長さ |w| に関する帰納法による。

w	= 0 のとき、K(1) = 1 だから命題は成り立つ。
w	> 0 かつ w の最後の文字が 0 のときを考える。このとき は偶数であり、w = v0 とおけば、補題 1 によって K(1w) = [2J(<1v>) - 1] = [2 - 1] となる。帰納法の仮定より K(1v) = #(v1) だから、2 - 1 = <#(v1)0> - 1 = <#(v10)> - 1 = <#(v01)> となる。したがって K(1w) = [<#(v01)>] = #(v01) = #(w1) となって命題が成り立つ。
w	> 0 かつ w の最後の文字が 1 のときを考える。このとき は奇数であり、w = v1 とおけば、補題 1 によって K(1w) = [2J(<1v>) + 1] = [J(<1v>)]1 = K(1v)1 となる。帰納法の仮定より K(1v) = #(v1) だから、K(1v)1 = #(v1)1 = #(v11) = #(w1) を得る。よって命題が成り立つ。

[定理（2984 のコレハヒドイ定理）] 任意の正整数 n について、n を 2 進表記した際の 1 の個数を c(n) と書くとき、n に対する 2984 の答えは 2^(c(n)) - 1
[証明]
n に対する 2984 の答えを N(n) とおく。定義より、N(n) は J(J(...J(n)...)) = N(n) および J(N(n)) = N(n) を満たす数である。J(x) = y と K([x]) = [y] とは同値であるから、K(K(...K([n])...)) = w および K(w) = w を満たす文字列 w について、N(n) = となる。
補題 2 より、{0,1} 上の文字列 v について、K(v) = v となるのは v が 0 を含まない場合に限る。また、K(v) に含まれる 1 の個数は v に含まれる 1 の個数と等しい。これらのことから、w = K(K(...K([n])...)) に含まれる 1 の個数は [n] に含まれる 1 の個数（すなわち c(n)）に等しく、かつ、w は 0 を含んでいない。したがって、w は 1 を c(n) 個並べたものであり、N(n) = = 2^(c(n)) - 1。