本記事の内容
本記事は『数学セミナー』(日本評論社)に掲載されている”エレガントな解答をもとむ”に出題されいている問題を1時間で解けるか、という挑戦をする記事です。
本記事を読むにあたり、前提知識は基本的に必要ありませんが、以前紹介した記事の内容を使う場合はその旨を記述することにします。
今回も「エレガントな解答をもとむ selections」に掲載されいている問題です。
前回の問題については以下の記事を御覧ください！
問題を明示します。
自然数\(N\)に対して、集合\(S_N\)を
数学セミナー編集部編（2001）『エレガントな解答をもとむ selections』日本評論社 p24-p25.
$$
S_N=\left\{ 2^n\middle|1\leq n\leq N\right\}
$$
で定義します。\(m\)を自然数とし、\(S_N\)から任意に1つの数を選ぶという試行を\(m\)回繰り返し行い、その結果選ばれた数\(x_1,\cdots,x_m\)を掛けてできる数\(x_1\cdots x_m\)を十進数で表したとき、その最高位の数字が\(1\)である確率を\(p_{m,N}\)とします。たとえば、\(m=2\)、\(N=3\)のとき、この試行によって得られるペアは\(9\)通りあり、それらは
\begin{eqnarray}
&&(2,2),\ (2,2^2),\ (2,2^3),\ (2^2,2),\ (2^2,2^2),\\
&&(2^2,2^3),\ (2^3,2),\ (2^3,2^2),\ (2^3,2^3)
\end{eqnarray}
なので、掛けてできる数は
$$
4,8,16,8,16,32,16,32,64
$$
となります。これらのうち最高位の数字が\(1\)のものは3つ、したがって、
$$
p_{2,3}=\frac{3}{9}=\frac{1}{3}
$$
となります。では、問題です。\(m\)を固定したとき、
$$
\lim_{N\to\infty}p_{m,N}
$$
を求めてください。
チャレンジの結果…？
チャレンジの結果…解けませんでした…
手も足も出ないという感じではありませんでしたが、一般の\(m\)についてはできませんでした。
最近結果が振るわず少々悲しいです。
筆者の解答(解けていないのであまり意味はありませんが…)
いきなり\(S_N\)から\(m\)回自然数を取り出すというのは難しそうですし、なんなら取り出す回数に対する数学的帰納法でできたりしないかな？と思い、まずは\(m=1\)の場合を考えてみました。
\(N\in\mathbb{N}\)、\(n\in\mathbb{N}\)は\(1\leq n\leq N\)を満たすとします。
そして、\(2^n\)を十進数表記したとき、最高の位が\(1\)であるような自然数の個数を\(K(1,N)\)と書くことにします。
「\(2^n\)の最高の位が\(1\)である」という条件を言い換える必要がありそうです。
例えば、\(16\)だったらば、\(10<16<20\)を満たします。
つまり、2桁の自然数\(x\)の最高の位が\(1\)であるということは、\(10\leq x<20\)を満たすということになります。
今、\(2^n\)の形をしている自然数を考えているわけですので、\(2^n=10\)を満たすような\(n\in\mathbb{N}\)は存在しません。
故に、2桁の場合は\(10<x<20\)ということになります。
ということは、
$$
(\exists k\in\mathbb{N})\ {\rm s.t.}\ 10^k<2^n<2\cdot10^k
$$
ということが条件の言い換えになっているわけです。
ここで、\(k\)の正体は桁数です。
今の不等式を変形して、\(n\)の条件を見てみます。
\begin{eqnarray}
10^k<2^n<2\cdot10^k&\Longleftrightarrow&k\log_210<n<\log_22\cdot10^k\\
&\Longleftrightarrow&k\log_22\cdot5<n<\log_22+k\log_210\\
&\Longleftrightarrow&k\left(\log_22+\log_25\right)<n<1+k\left( \log_22+\log_25\right)\\
&\Longleftrightarrow&k\left(1+\log_25\right)<n<1+k\left( 1+\log_25\right)\\
\end{eqnarray}
となるから、
$$
n=\left[k\left(1+\log_25 \right) \right]+1
$$
となるわけです。
ただし、\(\left[ \cdot\right]\)はガウス記号です。
つまり、
$$
1\leq \left[k\left(1+\log_25 \right) \right]+1\leq N
$$
を満たすような\(\left[k\left(1+\log_25 \right) \right]+1\)の個数がわかればOKです。
しかしながら、これは結局、上記の不等式を満たす\(k\in\mathbb{N}\)の個数です。
故に、上記の不等式を\(k\)について解けば、\(K(1,m)\)は
$$
K(1,m)=\left[ \frac{N}{1+\log_25}\right]
$$
となります。
求めたい極限は
$$
\lim_{N\to\infty}p_{1,N}=\lim_{N\to\infty}\frac{K(1,m)}{N}=\lim_{N\to\infty}\frac{1}{N}\left[ \frac{N}{1+\log_25}\right]=\frac{1}{1+\log_25}
$$
となります。
では、\(m\geq2\)のときです。
困りました。
一応力技でできそうなところまでペンを進めてみることにしました。
\(m\leq N\leq mN\)を満たすような自然数\(n\)を
$$
n=n_1+\cdots+n_m
$$
のように\(m\)個の自然数の和として表現するときのパターンの数を\(l(n,m,N)\)と書いたとします。
なぜこんな事を考えるのかというと、\(S_N\)から自然数を\(m\)かい選び、それらを掛け算するので、掛け算した後の数は\(2^{n_1+\cdots+n_m}\)の形をしているためです。
また、\(2^n\)を十進数表記したときの最高の位が\(1\)であるようなものの個数を\(L(m,N)\)と書きます。
そして\(\displaystyle a_k=\left[ \frac{k}{1+\log_25}\right]+1\)と定めます。
すると、
$$
\(L(m,N)\)=\sum_{m\leq a_k\leq mN}l(n,m,N
$$
が成り立ちます。
つまり、\(l(n,m,N\)がわかれば\(L(m,N)\)がわかり、そして\(p_{m,N}\)もわかる、という寸法です。
しかしながらこれ以上何かを得ることができずにタイムアップでした。
投稿されたエレガントな解答
今回は大長編です。
本問の答えは、\(m\)が何であっても
$$
\lim_{N\to\infty}p_{m,N}=\log_{10}2\tag{1}
$$
です。（中略）
\(N\)を任意の自然数とします。このとき、\(1\leq n\leq N\)を満たす自然数\(n\)の中で、\(2^n\)を十進数で表したときに、その最高位の数字が\(1\)であるものの個数\(Q_{1,N}\)を求めます。
（中略）
$$
Q_{1,N}=\left[ N\log_{10}2\right].\tag{2}
$$方法２：\(2^n\)の最高位の数字が\(1\)であることと、\(2^n\)の桁数が\(2^{n-1}\)の桁数よりも(1桁)大きいこととは同値。よって、\(Q_{1,N}\)は\(2^N\)の桁数に等しく、それは(2)で与えれれます(この方法は筆者の頭にはなく、なるほどと思った次第です)。
\(m=1\)の場合は\(p_{1,N}=Q_{1,N}/N\)なので、(2)から直ちに(1)が導かれます。一様分布論をご存知の方々は、この結論を「\(\theta\)を無理数とするとき、\(n\theta\ (n=1,2,\cdots)\)の小数部分からなる数列は\((0,1)\)区間に(一応分布するだけではなく)一様に分布する」という結果から導いていました。
（中略）
では、\(m\geq2\)の場合に進みましょう。\(m\leq n\leq mN\)を満たす自然数\(n\)を
$$
n=n_1+\cdots+n_m\quad (1\leq n_1,\cdots,n_m\leq N)\tag{3}
$$
の形に表す総数を\(c_{m,n}^{(n)}\)とします。また、(3)の形の数\(n\)(重複を込めて\(N^m\)個ある)の中で、\(2^n\)を十進数で表したときに、その最高位の数字が\(1\)であるものの個数を\(Q_{m,N}\)とします。このとき、\(p_{m,N}=Q_{m,N}/N^m\)です。簡単のため、\(\lambda=\log_{10}2\)とおきます。そして、自然数\(k\)に対して\(\lambda_k=\left[ k/\lambda\right]+1\)と定義し、これを一般項とする数列を\(\Lambda\)とします。すると、上記より
$$
Q_{m,N}=\sum_{m\leq \lambda_k\leq mN}c_{m,n}^{(\lambda_k)}.
$$
よって、書く\(c_{m,n}^{(n)}\)が求まれば、原理的には\(Q_{m,N}\)が、したがって、\(p_{m,N}\)が求まることになります。（中略）
同士に従って、\(m=2\)の場合の証明を述べます。この場合、\(c_{2,n}^{(n)}\)の値は
$$
c_{2,n}^{(n)}=
\begin{cases}
n-1,&2\leq n\leq N+1,\\
2N+1-n,&N+1< n\leq 2N.
\end{cases}
$$
これより、
$$
Q_{2,N}=\sum_{2\leq \lambda_k\leq 2N}c_{2,n}^{(\lambda_k)}=\sum_{2\leq \lambda_k\leq N+1}\left( \lambda_k-1\right)+\sum_{N+1\leq \lambda_k\leq 2N}\left( 2N+1-\lambda_k\right).
$$
数列\(\Lambda\)は、交差\(\lambda^{-1}\)の等差数列が少し酔っぱらったような数列なので、右辺の計算を十分な精度で行うことができます。それを見通しよく行うために、ランダウの\(O-\)記号を導入しましょう。自然数\(N\)の関数\(f(N)\)について、\(N\)の正値関数\(g(N)\)および正定数\(C\)があって
$$
\left| f(N)\right|\leq Cg(N)\quad (N=1,2,\cdots)
$$
が成り立つとき、\(f(N)=O\left( g(N)\right)\)と表します。さて、\(2\leq \lambda_k\leq 2N\)を満たす\(\lambda_k\)を順番に並べたものが、
$$
\lambda_1<\cdots<\lambda_u<N+1<\lambda_{u+1}<\cdots<\lambda_{u+v}
$$
となったとします。すると、ランダウの記号を使えば、
$$
u=N\lambda+O(1),\quad v=N\lambda+O(1)
$$
かつ
$$
c_{2,n}^{(\lambda_k)}+c_{2,n}^{(\lambda_{u+k})}=N+O(1)\quad (1\leq k\leq \min(u,v))
$$
と書けることがわかります。これより、
$$
Q_{2,N}=\left( N\lambda+O(1)\right)\left( N+O(1)\right)+O(N)=N^2\lambda+O(N)
$$
を導くことができて、要望の結果が得られます。
この方法を任意の\(m\)に対して行われた方は、解答を寄せられた皆さんの中にはいらっしゃいませんでした\(\cdots\)が、出題者の中には若干1名いらっしゃいました(?)。何を隠そう、筆者が最初にトライした方法がこれなのです。なせばなんとかなることもある、というわけで、それを簡単に紹介しましょう。まず、（中略）氏が示唆された方法で\(c_{m,n}^{(n)}\)を具体的に求めます。
$$
(x+x^2+\cdots+x^N)^m=\sum_{n=m}^{mN}c_{m,n}^{(n)}x^n
$$
および
\begin{eqnarray}
(x+x^2+\cdots+x^N)^m&=&x^m(1-x^N)^m(1-x)^{-m}\\
&=&x^m\sum_{i=0}^m(-1)^i
\begin{pmatrix}
m \\ i
\end{pmatrix}
x^{iN}\sum_{j=0}^\infty
\begin{pmatrix}j+m-1 \\ m-1\end{pmatrix}x^j
\end{eqnarray}
より、\(x^n\)の係数を較べて
$$
c_{m,n}^{(n)}=\sum_{i=0}^{\left[(n-m)/N \right]}(-1)^i\begin{pmatrix}
m \\ i
\end{pmatrix}\begin{pmatrix}n-iN-1 \\ m-1\end{pmatrix}\quad (m\leq n\leq mN).
$$
これより、
\begin{eqnarray}
p_{m,N}&=&\sum_{m\leq \lambda_k\leq mN}\frac{1}{N^m}\sum_{i=0}^{\left[(\lambda_k-m)/N \right]}(-1)^i\begin{pmatrix}m \\ i
\end{pmatrix}\begin{pmatrix}\lambda_k-iN-1 \\ m-1\end{pmatrix}\\
&=&\sum_{i=0}^{m-1}(-1)^i\begin{pmatrix}m \\ i\end{pmatrix}\frac{1}{N^m}\sum_{m+iN\leq \lambda_k\leq mN}\begin{pmatrix}\lambda_k-iN-1 \\ m-1\end{pmatrix}.
\end{eqnarray}
ここで、各\(i\ (0\leq i\leq m-1)\)について
$$
p_{m,N}=\frac{1}{N^m}\sum_{m+iN\leq \lambda_k\leq mN}\begin{pmatrix}\lambda_k-iN-1 \\ m-1\end{pmatrix}
$$
とおきます。このとき、
\begin{eqnarray}
p_{m,N}&=&\frac{1}{N^m}\sum_{m+iN\leq \lambda_k\leq mN}\left\{ \frac{(\lambda_k-iN)^{m-1}}{(m-1)!}+O\left( N^{m-2}\right)\right\}\\
&=&\frac{1}{(m-1)!}\frac{1}{N}\sum_{m+iN\leq \lambda_k\leq mN}\left( \frac{\lambda_k}{N}-i\right)^{m-1}+O\left( N^{-1}\right)
\end{eqnarray}
かつ
$$
\frac{k}{N\lambda}<\frac{\lambda_k}{N}<\frac{k+1}{N\lambda}
$$
より、
\begin{eqnarray}
\lim_{N\to\infty}p_{m,N}(i)&=&\frac{\lambda}{(m-1)!}\lim_{N\to\infty}\frac{1}{N\lambda}\sum_{m/N+i\leq \lambda_k/N\leq m}\left( \frac{\lambda_k}{N}-i\right)^{m-1}\\
&=&\frac{\lambda}{(m-1)!}\int_i^m(x-i)^{m-1}dx
\end{eqnarray}
となることを定積分の定義に従って示すことができます。よって
$$
\lim_{N\to\infty}p_{m,N}=\frac{\lambda}{(m-1)!}\sum_{i=0}^{m-1}(-1)^i\begin{pmatrix} m\\ i\end{pmatrix}\int_i^m(x-i)^{m-1}dx.
$$
一方、
$$
N^m=\sum_{n=m}^{mN}c_{m,n}^{(n)}=\sum_{i=0}^{m-1}(-1)^i\begin{pmatrix} m\\ i\end{pmatrix}\sum_{n=m+iN}^{mN}\begin{pmatrix}n-iN-1 \\ m-1\end{pmatrix}
$$
より、上記と同様の議論で
$$
1=\frac{1}{(m-1)!}\sum_{i=0}^{m-1}(-1)^i\begin{pmatrix} m\\ i\end{pmatrix}\int_i^m(x-i)^{m-1}dx
$$
を示すことができて、(1)に到達します。次の方法では、\(c_{m,n}^{(n)}\)の具体的な値を使いません。以下、（中略）氏に従って(記号も含めて)述べます。
$$
F_{m,N}(x)=(x+x^2+\cdots+x^N)^m
$$
とおきます。このとき、
\begin{eqnarray}
F_{m,N}(x)&=&F_{m-1,N}(x)(x+x^2+\cdots+x^N)\\
&=&\sum_{k=m-1}^{(m-1)N}c_{m-1,n}^{(k)}(x^{k+1}+x^{k+2}+\cdots+x^{k+N})
\end{eqnarray}
に注意します。ただし、\(c_{0,n}^{(0)}\equiv1\)と定めます。\(x^{k+1}+x^{k+2}+\cdots+x^{k+N}\)の各項の指数\(k+1,\cdots,k+N\)の中で、\(\lambda\)の元となるものの個数を\(J_k\)とすると、上式より
$$
Q_{m,N}=\sum_{k=m-1}^{(m-1)N}c_{m-1,n}^{(k)}J_k.
$$
ここで、(2)を用いると、
$$
N\lambda-1<J_k<N\lambda+1\quad (k=0,1,2,\cdots).\tag{4}
$$
よって、
$$
(N\lambda-1)\sum_{k=m-1}^{(m-1)N}c_{m-1,n}^{(k)}<Q_{m,N}<\left( N\lambda+1\right)\sum_{k=m-1}^{(m-1)N}c_{m-1,n}^{(k)}.
$$
また、
$$
\sum_{k=m-1}^{(m-1)N}c_{m-1,n}^{(k)}=F_{m-1,N}(1)=N^{m-1}.
$$
両辺を\(N^m\)で割って
$$
\lambda-\frac{1}{N}<p_{m,N}<\lambda+\frac{1}{N}
$$
となり、所望の結果の精密化が得られます。（中略）
さて、上記の方法は次のように要約できます。すなわち、(3)の形の数全体(重複を込めて\(N^m\)個ある)を、\(m-1\leq k\leq (m-1)N\)を満たす各自然数\(k\)毎に\(c_{m-1,n}^{(n)}\)解重複して現れる数列\(k+1,\cdots,k+N\)に分けて、\(Q_{m,N}\)の評価(5)を導いた、と。このアイデアをもう一歩押し進めて、\(k+1,\cdots,k+N\)の形の数列が重複を込めて\(N^{m-1}\)個あると考えると、(4)から直ちに(5)を導くことができます。
（中略）
上記の解答で本質的だったのは、(4)が任意の\(k\)に対して一様に成り立つことでした。最後に、この状況を一般化することで、本問の位置付けを明確にしたいと思います。今、\(2^n\)の最高位の数字が\(1\)のとき\(a_n=1\)、そうではないとき\(a_n=0\)として数列\(a_n\ (n=1,2,\cdots)\)を定義すると、(4)を
数学セミナー編集部編（2001）『エレガントな解答をもとむ selections』日本評論社 p212-p218.
$$
\left| \frac{1}{N}\sum_{n=1}^Na_{k+n}^-\lambda\right|<\frac{1}{N}\quad (k=0,1,2,\cdots)\tag{6}
$$
と書き直すことができます。逆に、実数列\(a_n\ (n=1,2,\cdots)\)が、ある実数\(\lambda\)について(6)を満たすならば、任意の自然数\(m\)に対して
$$
\lim_{N\to\infty}\frac{1}{N^m}\sum_{n_1=1}^N\cdots\sum_{n_m=1}^Na_{n_1+\cdots+n_m}=\lambda\tag{7}
$$
が成り立つことがわかります。(6)を弱めた「任意の\(\varepsilon>0\)に対してある自然数\(N_1\)があって、\(N_1\)以上のすべての自然数\(N\)について
$$
\left| \frac{1}{N}\sum_{n=1}^Na_{k+n}^-\lambda\right|<\varepsilon\tag{8}
$$
が成り立つ」という条件の下でも同じ結論が得られますね。さらに調べてみると、実は、\(k=0\)に対してのみの条件から上の条件そのもの(\(k\)についての一様性が大切)が従うことを示せるのです。それを実行してみましょう。\(1\)より小さい正数\(\varepsilon\)を任意に取ります。
$$
S_N=\frac{1}{N}\sum_{n=1}^Na_n
$$
とおくと、\(k=0\)についての条件より、ある自然数\(N_0\)があって、
$$
\left| S_N-\lambda\right|<\delta:=\frac{\varepsilon}{2M+1}
$$
が\(N_0\)以上のすべての自然数\(N\)に対して成り立ちます。ただし、\(M\)は、\(\left| S_N\right|<M\)がすべての自然数\(N\)に対して成り立つような\(m\)以上の正定数です。ここで、\(N_0/\delta\)より大きい自然数を1つとって\(N_1\)とします(\(N_0/N_1<\delta\))。以下で、\(N_1\)以上の任意の自然数\(N\)に対して、(8)が成り立つことを示しましょう。
$$
\frac{1}{N}\sum_{n=1}^Na_{k+n}=\frac{k+N}{N}S_{k+N}-\frac{k}{N}S_k=S_{k+N}+\frac{k}{N}\left( S_{k+N}-S_k\right)
$$
に注意すると、
$$
T_N(k):=\left| \frac{1}{N}\sum_{n=1}^Na_{k+n}^-\lambda\right|\leq \left| S_{k+N}-\lambda\right|+\frac{k}{N}\left( \left| S_{k+N}\right|+\left| S_k\right|\right)
$$
より、\(k\leq N_0\)のとき
$$
T_N(k)<\delta+\frac{N_0}{N_1}(M+M)<(2M+1)\delta=\varepsilon.
$$
また、
$$
T_N(k)\leq \left| S_{k+N}-\lambda\right|+\frac{k}{N}\left( \left| S_k+N-\lambda\right|+\left| \lambda-S_k\right|\right)
$$
より、\(N_0<k\leq (m-1)N\)のとき
$$
T_N(k)<\delta+\frac{(m-1)N}{N}(\delta+\delta)=(2m-1)\delta<\varepsilon.
$$
すなわち、(8)が成り立ちます。かくして、
$$
\lim_{N\to\infty}\frac{1}{N}\sum_{n=1}^Na_n=\lambda
$$
が成り立てば(7)も成り立つ、という数列の一般的性質が確立し、本問がその一例を与えることが判明した次第です。
読者の皆様への挑戦状！
来週の日曜日に挑戦します！
\(xyz-\)空間内の同一平面上にない\(4\)点\({\rm P_1},\cdots,{\rm P_4}\)が与えられたとき、この\(4\)点をとおる曲線の方程式をひとつ与えて下さい。また、その方程式を使って、\({\rm P_1}=(1,0,0),\ {\rm P_2}=(0,1,0),\ {\rm P_3}=(0,0,1),\ {\rm P_4}=(0,0,0)\)の場合にその曲線のグラフを描いてください。
数学セミナー編集部編（2001）『エレガントな解答をもとむ selections』日本評論社 p25.
もちろん、そのような曲線は無数にありますが、できるだけ方程式が美的なもの、簡単なもの、あるいはおもしろいものを捜してください。また、曲線は閉曲線(楕円のように輪になって閉じたもの)でも開曲線(放物線のように無限遠まで伸びていくもの)でもよく、4点は順に並んでいなくてもよいことにします。ただし双曲線2つの曲線に分解できるような曲線(可約曲線)は、好ましくありません。
前回の問題は【１時間チャレンジシリーズ】挑戦㉜を御覧ください！
結
いかがでしたか？
今回は数セミの「エレガントな解答をもとむ」に挑戦してみる、という記事でした。
読者の皆様も是非一度挑戦してみて下さい！
そして、「読者の皆様への挑戦状」にも是非挑戦していただき、解答をコメントで教えて下さい！
質問、コメントなどお待ちしております！
どんな些細なことでも構いませんし、この記事に限らず、「定理〇〇の△△が分からない！」などいただければお答えします！
お問い合わせの内容にもよりますが、ご質問はおおよそ一週間ほどでお答えします。
(難しかったらもう少しかかるかもしれませんが…)
Twitterでもリプ、DM問わず質問、コメントを大募集しております！
他の「エレガントな解答をもとむ」の問題に挑戦してみたい方はぜひ以下の書籍をお買い求め下さい！
コメントをする