ノリの悪い日記

古今東西の映画、ポピュラー音楽、その他をいまここに交錯させながら随想します。

陥没地帯 (237)

2011 年東大文理共通問題. 要するに連分数に関係した問題である.  (2) は答が黄金比と白銀比に関連している. (3) は有理数の連分数がユークリッド互除法と同値であることを示せばよい.

【問】
実数 x の小数部分を,  0 \leq y < 1 かつ x - y が整数となる実数 y のこととし, これを記号 \langle x \rangle で表す. 実数  a に対して, 無限数列  \{a_n\} の各項  a_n ( n = 1, 2, 3, \cdots) を次のように順次定める.

(\mathrm{i})  a_1 = \langle a\rangle
(\mathrm{ii})
a_n \neq 0 のとき,  \displaystyle{a_{n + 1} = \left\langle \frac{1}{a_n}\right\rangle}
 a_n = 0 のとき,  a_{n + 1} = 0

(1)  a = \sqrt{2} のとき, 数列  \{a_n\} を求めよ.
(2) 任意の自然数 n に対して a_n = a となるような  1/3 以上の実数 a をすべて求めよ.
(3) a が有理数であるとする. a を整数 p と自然数 q を用いて  a = p/q と表すとき, q 以上のすべての自然数 n に対して, a_n = 0 であることを示せ.

【解】
 (1)
 a_1 = \langle \sqrt{2} \rangle =  \sqrt{2}-\lfloor \sqrt{2} \rfloor =\sqrt{2} - 1

 \begin{align}
a_2  &= \left\langle \frac{1}{\sqrt{2} -1} \right\rangle\\
&= \langle \sqrt{2} + 1 \rangle\\
&= \langle \sqrt 2 \rangle\\
&= a_1
\end{align}

したがって,

a_n = \sqrt{2} - 1

(2)
 a_1 = a - \lfloor a \rfloor = a

から,  \lfloor a \rfloor = 0 である. これと問題の条件から,

 \displaystyle{\frac{1}{3} \leq  a  < 1}

となる.  n \geq 2 のとき,  a \neq 0 だから,

 \displaystyle{a_n  = \frac{1}{a} - \left\lfloor \frac{1}{a} \right\rfloor = a}

 \displaystyle{1 < \frac{1}{a} \leq 3}

だから,   \displaystyle{\left\lfloor \frac{1}{a} \right\rfloor} は,  1 または  2 または  3 である.

 \displaystyle{ \left\lfloor \frac{1}{a} \right\rfloor =1}のとき:
 \displaystyle{ \frac{1}{a} - 1  = a} \displaystyle{\frac{1}{3} \leq  a  < 1} を満足する解として,

\displaystyle{ a = \frac{-1 + \sqrt{5}}{2}}

がある.

 \displaystyle{ \left\lfloor \frac{1}{a} \right\rfloor =2}のとき:
 \displaystyle{ \frac{1}{a} - 2  = a} \displaystyle{\frac{1}{3} \leq  a  < 1} を満足する解として,

 a = -1 + \sqrt{2}

がある.

 \displaystyle{ \left\lfloor \frac{1}{a} \right\rfloor =3}のとき:

条件を満足する  a は存在しない.

以上から求める実数 a は, 黄金比の小数部分 (-1 +\sqrt{5})/2 と白銀比の小数部分である  -1 + \sqrt{2} である.

(3)
ユークリッド互除法で,  p q の最大公約数を求めるためには以下のようにする. なお,  p r_0 = q で除した剰余を  r_1 とおいて, 以下帰納的に  r_{i-1} r_i で除した剰余を  r_{i+1} とする.

 \begin{eqnarray}
p &=& \lfloor p/r_0\rfloor r_0 + r_1 \\
r_0 &=& \lfloor r_0 /r_1 \rfloor r_1 + r_2\\
r_1 &=& \lfloor r_1 /r_2 \rfloor r_2 + r_3\\
 &\cdots&
\end{eqnarray}
( r_k = 0 となれば停止し,  n \geq k で,  r_n = 0 とする.)

このとき,  r_0 = q とし,

(\mathrm{i})  b_1 = r_1/r_0
(\mathrm{ii})
 b_{n} \neq 0 のとき,  b_{n+1}= r_{n+1}/r_{n},
 b_{n} = 0 のとき,  b_{n+1} = 0

と,  b_n を定めることにすれば,  \{a_n\} = \{b_n\} であることを以下に帰納法で示す.

 n = 1 のとき,

 p = \lfloor p/r_0\rfloor r_0 + r_1

だから,

 \begin{align} 
b_1 &=r_1 /r_0 \\
       &= p/q- \lfloor p/q\rfloor \\
        &= a_1
\end{align}

となって成立する.

 b_{n} = a_{n} = 0 と仮定すると,  b_{n+1} = a_{n+1} = 0 となって成立する.

 b_{n} = a_{n} \neq 0 と仮定すると,

 r_{n-1}  = \lfloor r_{n-1}/r_n \rfloor r_{n} + r_{n+1}

だから,

 \begin{align}
b_{n+1} &= r_{n+1}/r_{n} \\
&= r_{n-1}/r_{n} - \lfloor r_{n-1}/r_{n} \rfloor\\
&= 1/b_{n} - \lfloor 1/b_{n} \rfloor\\
&=  1/a_{n} - \lfloor 1/a_{n} \rfloor\\
&= a_{n+1}
\end{align}

となって成立する. 以上から,  \{a_n\} = \{b_n\} であることが示せた.

さて, ユークリッド互除法において,

q = r_0 > r_1  > \cdots > r_k  \geq 0

のように, \{r_k\} は,  r_k > 0 である  k に対して真に減少していき, 最後は必ず  0 に収束する. なぜなら, もし,  r_k 0 に到達しないのであれば, 互除法の手続きを無限に続けることができるが, それは  q が有限な自然数であることに矛盾するからである. 実際にはたかだか  q 回の手続きで,  r_q0 となる.  r_q = 0 のとき,  b_q = a_q = 0 となるから, 題意は証明された.
//