ゴールデンな数学に挑戦（その４）
2021年4月8日
待望の『数学ゴールデン』第２巻がついに発売しました！
私は楽天ブックスで注文していたのですが、到着したのは発売日の翌日でした^^;
到着後はもちろん即・読破しました！！
今回もたくさんの興味深い数学の問題が登場するのはもちろんですが、それ以外にも、数学がバリバリできる新キャラが登場したり、ちょっと恋愛要素（？）が加わったりと見どころ満載です^^♪
また、テストのシーンや、主人公・春一が（数学的に）進化するシーンは、まるでバトル漫画のような描写で表現されていて、第１巻以上に難問に立ち向かう少年たちのエネルギーを感じることができます！！
まさに数学というのは「紙の上の格闘技」ですね^^！！
今回の記事では、第２巻第５話に登場する「筧十三スペシャル宿題」にトライしてみました：
足す順番のみが異なる表し方は１通りと数える。
ただし、原題にはミスプリントと思われる部分があったのでそこだけ修正しました。
私は楽天ブックスで注文していたのですが、到着したのは発売日の翌日でした^^;
到着後はもちろん即・読破しました！！
今回もたくさんの興味深い数学の問題が登場するのはもちろんですが、それ以外にも、数学がバリバリできる新キャラが登場したり、ちょっと恋愛要素（？）が加わったりと見どころ満載です^^♪
また、テストのシーンや、主人公・春一が（数学的に）進化するシーンは、まるでバトル漫画のような描写で表現されていて、第１巻以上に難問に立ち向かう少年たちのエネルギーを感じることができます！！
まさに数学というのは「紙の上の格闘技」ですね^^！！
今回の記事では、第２巻第５話に登場する「筧十三スペシャル宿題」にトライしてみました：
問題
自然数 $n$ を $1$，$3$，$7$，$15$，$31$，$\cdots$（$2$ の累乗 $-1$）の和で表す方法の数と，どの２つの数も $2$ 倍以上離れた数の和で表す方法の数は等しいことを示せ．足す順番のみが異なる表し方は１通りと数える。
…では解説を始めようと思うのですが、そのまえに一つお断りです^^;
作品の中では本問は「ヤング図形」というものを使って証明されるという雰囲気で描かれています（証明の詳細までは書かれておりません…）。
「ヤング図形」は自然数 $n$ の分割数や、対象群の複素既約表現などの研究に登場するもので、本問とも相性が良さそうですが、私の力不足で「ヤング図形」を用いた証明を補完できませんでした。
以下でご紹介するのは作品で登場したものとは無関係な証明です。悪しからず…^^;
まず，問題を正確に記述するために記号を導入します。
自然数 $n$ を
\[ 2^k-1\quad(k=1,\,2,\,3,\,\ldots\,)\qquad\cdots\cdots\,(\ast 1) \]
の形の自然数の和で表す方法を考えます。和の順序が異なるだけのものは同一視するので，$(\ast 1)$ の数がそれぞれ何個ずつ登場するのかに注目します。
各 $k=1,\,2,\,3,\,\ldots$ に対し，$2^k-1$ が $a_k$ 回登場するとして，
\[ n=\textstyle\sum\limits_{k=1}^{N}a_k(2^k-1),\quad a_N\geqq 1 \]
と表わすとき，組 $(a_1,\,a_2,\,\ldots,\,a_N)$ の全体の集合を $A_n$ と定義します。例えば，
\[ 100=1+1+1+1+1+3+7+7+15+63 \]
については，
\begin{align*}
100&=1+1+1+1+1+3+7+7+15+63\\
&=5\times 1+1\times 3+2\times 7+1\times 15+0\times 31+1\times 63
\end{align*}
なので，
\[ (5,\,1,\,2,\,1,\,0,\,1)\in A_{100} \]
となります。次に，自然数 $n$ を「どの2つの数も2倍以上離れた自然数」の和で表す方法を考えます。
\[ n=b_1+b_2+\cdots+b_N\quad (b_k\geqq 2b_{k+1}) \]
と表すとき，組 $(b_1,\,b_2,\,\ldots,\,b_N)$ の全体の集合を $B_n$ と定義します。例えば，
\[ 100=55+25+12+5+2+1 \]
については，
\[ (55,\,25,\,12,\,5,\,2,\,1)\in B_{100} \]
となります。このように定めた集合 $A_n$，$B_n$ に対して，
\[ n(A_n)=n(B_n) \]
となることを示すのが目標です！！まずは小さい $n$ について「実験」をして，問題の雰囲気をつかみましょう。
$10$ 以下の自然数について具体的に調べてみます：
$n=1$ のとき
\begin{align*}
A_1=\{(1)\},\quad B_1=\{(1)\}
\end{align*}
なので $n(A_1)=n(B_1)=1$ で正しい。$n=2$ のとき
\begin{align*}
A_2=\{(2)\},\quad B_2=\{(2)\}
\end{align*}
なので $n(A_2)=n(B_2)=1$ で正しい。$n=3$ のとき
\begin{align*}
A_3=\{(3),\,(0,\,1)\},\quad B_3=\{(3),\,(2,\,1)\}
\end{align*}
なので $n(A_3)=n(B_3)=2$ で正しい。$n=4$ のとき
\begin{align*}
A_4=\{(4),\,(1,\,1)\},\quad B_4=\{(4),\,(3,\,1)\}
\end{align*}
なので $n(A_4)=n(B_4)=2$ で正しい。$n=5$ のとき
\begin{align*}
A_5=\{(5),\,(2,\,1)\},\quad B_5=\{(5),\,(4,\,1)\}
\end{align*}
なので $n(A_5)=n(B_5)=2$ で正しい。$n=6$ のとき
\begin{align*}
A_6&=\{(6),\,(3,\,1),\,(0,\,2)\},\\
B_6&=\{(6),\,(5,\,1),\,(4,\,2)\}
\end{align*}
なので $n(A_6)=n(B_6)=3$ で正しい。$n=7$ のとき
\begin{align*}
A_7&=\{(7),\,(4,\,1),\,(1,\,2),\,(0,\,0,\,1)\},\\
B_7&=\{(7),\,(6,\,1),\,(5,\,2),\,(4,\,2,\,1)\}
\end{align*}
なので $n(A_7)=n(B_7)=4$ で正しい。$n=8$ のとき
\begin{align*}
A_8&=\{(8),\,(5,\,1),\,(2,\,2),\,(1,\,0,\,1)\},\\
B_8&=\{(8),\,(7,\,1),\,(6,\,2),\,(5,\,2,\,1)\}
\end{align*}
なので $n(A_8)=n(B_8)=4$ で正しい。$n=9$ のとき
\begin{align*}
A_9&=\{(9),\,(6,\,1),\,(3,\,2),\,(0,\,3),\,(2,\,0,\,1)\},\\
B_9&=\{(9),\,(8,\,1),\,(7,\,2),\,(6,\,3),\,(6,\,2,\,1)\}
\end{align*}
なので $n(A_9)=n(B_9)=5$ で正しい。$n=10$ のとき
\begin{align*}
A_{10}&=\{(10),\,(7,\,1),\,(4,\,2),\,(1,\,3),\,(3,\,0,\,1),\,(0,\,1,\,1)\},\\
B_{10}&=\{(10),\,(9,\,1),\,(8,\,2),\,(7,\,3),\,(7,\,2,\,1),\,(6,\,3,\,1)\}
\end{align*}
なので $n(A_{10})=n(B_{10})=6$ で正しい。こんな感じで，小さい $n$ については確かに成り立つようです。
上のように，２つの集合を並べて書いたとき，両者の間に存在する規則性に気が付くでしょうか？
以下では，$A_n$ の要素と $B_n$ の要素を結びつける規則を定義し，それが両者を一対一に対応させることを示します。
まず，$A_n$ の要素から $B_n$ の要素を作り出す規則 $f$ を以下のように定義します：
$(a_1,\,a_2,\,\ldots,\,a_N)\in A_n$ に対して，
\[ n=\textstyle\sum\limits_{k=1}^{N}a_k(2^k-1)\qquad\cdots\cdots\,(\ast 2) \]
が成り立ちます。ここで，等比数列の和の公式から
\[ 2^k-1=1+2+\cdots+2^{k-1} \]
なので，$(\ast 2)$ は，
\begin{align*}
n&=a_1\cdot 2^0\\
&+a_2\cdot 2^0 + a_2\cdot 2^1\\
&+a_3\cdot 2^0 + a_3\cdot 2^1 +a_3\cdot 2^2\\
&+\cdots\cdots\\
&+a_N\cdot 2^0 +a_N\cdot 2^1 +\cdots\cdots +a_N\cdot 2^{N-2} +a_N\cdot 2^{N-1}
\end{align*}
と表されます。上のように配置したとき，斜めに並んでいる項の和を上から順に $b_1$，$b_2$，$\cdots$ とします。すなわち，
\[ b_j=\textstyle\sum\limits_{k=j}^{N}a_k\cdot 2^{k-j},\quad (j=1,\,2,\,\ldots,\,N) \]
とします。このように構成した $(b_1,\,b_2,\,\ldots,\,b_N)$ が $B_n$ の要素になっていることを示します。構成法から，
\[ b_1+b_2+\cdots+b_N=n \]
は明らかです。また，
\begin{align*}
b_j&=\textstyle\sum\limits_{k=j}^{N}a_k\cdot 2^{k-j}=2\textstyle\sum\limits_{k=j}^{N}a_k\cdot 2^{k-(j+1)}\\
&\geqq 2\textstyle\sum\limits_{k=j+1}^{N}a_k\cdot 2^{k-(j+1)}=2b_{j+1}
\end{align*}
なので，「２倍以上離れている」という条件もクリアです！以上の方法で，$A_n$ の要素から $B_n$ の要素を構成する規則を $f$ と名付けておきます。
例えば，$(5,\,1,\,2,\,1,\,0,\,1)\in A_{100}$ に対し，
\[ f((5,\,1,\,2,\,1,\,0,\,1))=(55,\,25,\,12,\,5,\,2,\,1)\in B_{100} \]
ですっ！上のように定義した $f$ が $A_n$ の要素と $B_n$ の要素を一対一に対応させることを示していきます。
まずは，$f:A_n\to B_n$ が単射であることを示します。
$(a_1,\,\ldots,\,a_N),\,(a^\prime_1,\,\ldots,\,a^\prime_M)\in A_n$ が，
\[ f((a_1,\,\ldots,\,a_N))=f((a^\prime_1,\,\ldots,\,a^\prime_M)) \]
を満たしているとします。まず，明らかに $N=M$ です。
\[ f((a_1,\,\ldots,\,a_N))=f((a^\prime_1,\,\ldots,\,a^\prime_N))=(b_1,\,\ldots,\,b_N) \]
とすると，
\[ b_N=a_N=a^\prime_N \]
です。次に
\[ b_{N-1}=a_{N-1}+2a_N=a^\prime_{N-1}+2a^\prime_{N} \]
と，$a_N=a^\prime_N$ より $a_{N-1}=a^\prime_{N-1}$ です。
\begin{align*}
b_{N-2}&=a_{N-2}+2a_{N-1}+2^2a_{N}\\
&=a^\prime_{N-2}+2a^\prime_{N-1}+2^2a^\prime_{N}
\end{align*}
と，$a_N=a^\prime_N$，$a_{N-1}=a^\prime_{N-1}$ より $a_{N-2}=a^\prime_{N-2}$ です。以下同様にして，
\[ (a_1,\,\ldots,\,a_N)=(a^\prime_1,\,\ldots,\,a^\prime_N) \]
だと分かります。すなわち，$f$ が単射であることが示されました！次に，$f$ が全射であることを示します。
$(b_1,\,b_2,\,\ldots,\,b_N)\in B_n$ に対し，$a_k$ を，
\[ \left\{\begin{array}{ll}
a_k=b_k-2b_{k+1} & (k=1,\,2,\,\ldots,\,N-1)\\
a_N=b_N &
\end{array}\right. \]
と定義します。このとき，$a_N\geqq 1$ であり，$B_n$ の要素の各項はそれぞれ「2倍以上離れている」ことから $a_k\geqq 0$ です。$a_k$ をこのように定義すると，
\begin{align*}
\textstyle\sum\limits_{k=1}^{N}a_k(2^k-1)&=\textstyle\sum\limits_{k=1}^{N-1}(b_k-2b_{k+1})(2^k-1)+b_N(2^N-1)\\
&=\textstyle\sum\limits_{k=1}^{N-1}\{b_k(2^k-1)-b_{k+1}(2^{k+1}-1)+b_{k+1}\}+b_N(2^N-1)\\
&=\textstyle\sum\limits_{k=1}^{N-1}b_k(2^k-1)-\textstyle\sum\limits_{k=1}^{N-1}b_{k+1}(2^{k+1}-1)+\textstyle\sum\limits_{k=1}^{N-1}b_{k+1}+b_N(2^N-1)\\
&=\textstyle\sum\limits_{k=1}^{N-1}b_k(2^k-1)-\textstyle\sum\limits_{k=2}^{N}b_{k}(2^{k}-1)+\textstyle\sum\limits_{k=2}^{N}b_{k}+b_N(2^N-1)\\
&=b_1(2^1-1)-b_N(2^N-1)+\textstyle\sum\limits_{k=2}^{N}b_{k}+b_N(2^N-1)\\
&=b_1+b_2+\cdots +b_N=n\end{align*}
より，$(a_1,\,a_2,\,\ldots,\,a_N)\in A_n$ であることが分かります。また，$j=1,\,2,\,\ldots,\,N-1$ に対し，
\begin{align*}
\textstyle\sum\limits_{k=j}^{N}2^{k-j}a_k&=\textstyle\sum\limits_{k=j}^{N-1}2^{k-j}(b_k-2b_{k+1})+2^{N-j}b_N\\
&=\textstyle\sum\limits_{k=j}^{N-1}2^{k-j}b_k-\textstyle\sum\limits_{k=j}^{N-1}2^{k-j+1}b_{k+1}+2^{N-j}b_N\\
&=\textstyle\sum\limits_{k=j}^{N-1}2^{k-j}b_k-\textstyle\sum\limits_{k=j+1}^{N}2^{k-j}b_k+2^{N-j}b_N\\
&=2^0b_j-2^{N-j}b_N+2^{N-j}b_N=b_j
\end{align*}
となります。$a_N=b_N$ とあわせるとこれは，
\[ f((a_1,\,a_2,\,\ldots,\,a_N))=(b_1,\,b_2,\,\ldots,\,b_N) \]
であることを示しています。これにより $f$ が全射であることが示されました！以上の議論によって，$f:A_n\to B_n$ が全単射であることが示されました！！
$f$ によって，$A_n$ の要素と $B_n$ の要素が一対一に対応し，$n(A_n)=n(B_n)$ であることが分かります。
これにて問題解決ですっ！！
『数学ゴールデン』第２巻１発目はいかかでしたか？
高校入試＆新年度の準備等で忙しく、２巻発売からかなり日数が経ってしまいました^^;
２巻掲載の他の問題も、時間を見つけては記事にしていこうと思います！
是非、次の問題もお楽しみに～！！^^♪
コメントを残す