2べき分割

305

はじめに

　最近面白い発見をしたので共有します．
　かなり既出っぽいです．既出だったらこっそり教えて下さい

　 $9$ を $2^{2} + 2^{2} + 2^{0}$ や $2^{1} + 2^{1} + 2^{1} + 2^{1} + 2^{0}$ にするように，正整数を $1$ 個以上の $2$ べきの和として表す方法を $2$ べき分割とよぶ．この際， $和の順序は区別しない$ ．(例えば， $2^{3} + 2^{0}$ と $2^{0} + 2^{3}$ は同一視する．)

本題

　本題になってしまいました

　 $2$ 以上の整数について，その $2$ べき分割の総数は偶数である．

　これは証明を考えるだけでもかなり面白いので考えてみて下さい．

.
..
.
..
.
..
...
.
..
.
.
..
.
..
.
.
.
..
...
.
....
.
.

　 $2$ べき分割を，次のように $2$ グループに分ける．(当然共通部分を持たない．)

$(A)$ 　 $2$ べき分割に使っている $2$ べきのうち，最大のものがちょうど $1$ つ存在する．

$(B)$ 　 $2$ べき分割に使っている $2$ べきのうち，最大のものが $2$ つ以上存在する．

　例えば， $10$ の $2^{3} + 2^{1}$ という分割について，最大の $2$ べきは $2^{3}$ だが，これは $1$ 回しか表れていないので $(A)$ に分類される．逆に， $2^{2} + 2^{2} + 2^{1}$ や $2^{1} + 2^{1} + 2^{1} + 2^{1} + 2^{1}$ は $(B)$ に分類される．

　実は，この $2$ グループの間には次のように $1$ 対 $1$ 対応が作れる．

$(A)$ の分割について，最大の $2$ べきを $2^{n}$ として，それを $2^{n - 1} + 2^{n - 1}$ に置き換える．すると $2^{n - 1}$ は必ず $2$ つ以上使っていることになり， $(B)$ の分割に変わる．
逆に， $(B)$ の分割について，最大の $2$ べきを $2^{n}$ として， $2^{n} + 2^{n}$ を $2^{n + 1}$ に置き換える．すると $2^{n + 1}$ は必ずちょうど $1$ つ使っていることになり， $(A)$ の分割に変わる．

　よって， $(A)$ と $(B)$ に含まれる分割の個数は等しく，全体では偶数になる．

　( $6$ のときの対応の例を示す．)
$(4 + 2 ⟺ 2 + 2 + 2), (4 + 1 + 1 ⟺ 2 + 2 + 1 + 1), (2 + 1 + 1 + 1 + 1 ⟺ 1 + 1 + 1 + 1 + 1 + 1)$

　面白いと思いませんか？　 $2^{n + 1} = 2^{n} + 2^{n}$ という $2$ べき特有の性質を使っているのがポイントになっています．ちなみに， $2$ 以上の整数の $2$ べき分割の個数は必ず偶数になりますが， $1$ のときは奇数になります． $1$ は $2^{n} + 2^{n}$ にできないので上の議論が崩れるんですね．