3

2べき分割

261
1
$$$$

はじめに

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

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

本題

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

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

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

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

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


$\mathbf{(A)}$ $2$べき分割に使っている$2$べきのうち,最大のものがちょうど$1$つ存在する.

$\mathbf{(B)}$ $2$べき分割に使っている$2$べきのうち,最大のものが$2$つ以上存在する.

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


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

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

 よって,$\mathbf{(A)}$$\mathbf{(B)}$に含まれる分割の個数は等しく,全体では偶数になる.

 ($6$のときの対応の例を示す.)
$$(4+2 \iff 2+2+2), (4+1+1 \iff 2+2+1+1), (2+1+1+1+1 \iff 1+1+1+1+1+1)$$

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

 上の全単射において,使う$2$べきの個数はちょうど$1$個変わります.従ってこんなこともいえます.

 $2$以上の整数について,「使う$2$べきの個数が$\textbf{偶数}$である$2$べき分割の個数」と,「使う$2$べきの個数が$\textbf{奇数}$である$2$べき分割の個数」は等しい

拡張?

 同様に$m$べき分割を考えると次のこともいえます.

$\mathbf{(A_m)}$ $m$べき分割に使っている$m$べきのうち,最大のものがちょうど$1$つ存在する.

$\mathbf{(B_m)}$ $m$べき分割に使っている$m$べきのうち,最大のものが$m$個以上存在する.

という$2$つのグループを考えれば,この間に全単射が作れる.

 これが何かに使えるかは不明です

最後に

 すごい綺麗な議論を思い付いたので嬉しいです.ここまで読んで頂きありがとうございました!  

 

投稿日:33
OptHub AI Competition

この記事を高評価した人

高評価したユーザはいません

この記事に送られたバッジ

バッジはありません。

投稿者

じゃむ
じゃむ
30
2882
競技数学を食べています

コメント

他の人のコメント

コメントはありません。
読み込み中...
読み込み中