とぽろじい　～大人の数学自由研究～

高校数学から分かる新しい数学、大学で学ぶ数学を少しずつまとめていくブログです。ゆくゆくは本にまとめたいと思っています。

MENU
トップ > *単発自由研究 > 【整数】床関数(ガウス記号)　「商を3でn回割り続けること」と「3のn乗で割った商を求めること」は同じか？

【整数】床関数(ガウス記号)　「商を3でn回割り続けること」と「3のn乗で割った商を求めること」は同じか？

*単発自由研究 ★高校数学+α ・数列 ・整数

今回はふと気になった疑問を「不等式で定義される関数」を用いて解決しようと思います。

 

具体例と問題提起

 

まず例として200を3で割り続けます。ただし商だけを割り続けます。

200=3\cdot 66+2

66=3\cdot 22

22=3\cdot 7 +1

7=3\cdot 2+1

すると商には 66,22,7,2 という数が現れます。

 

次に200を 3^{n} (n は正の整数) で割ります。

200=3\cdot 66 +2

200=9\cdot 22 +2

200=27\cdot 7 +11

200=81\cdot 2 +38

こちらも商には 66,22,7,2 という数が現れます。

 

余りこそ違いますが、それぞれに登場する商は一致します。

このことは一般的に成り立つのでしょうか。

感覚的には当たり前のような気もしますが、今回は床関数(ガウス記号)を用いて厳密に調べてみようと思います。

 

そこで数列の問題として考えます。

 

一般化

 

問題

 N を正の整数とする。

数列 \{ a_{n} \} , \{ b_{n} \} (n=0,1,2,\dots)を以下のように定義する。

ただし実数 x に対して \lfloor x\rfloor は x を超えない最大の整数を表すこととする。

 

a_{0}=N , a_{n+1}= \left\lfloor \dfrac{a_{n}}{3} \right\rfloor

b_{n}=\left\lfloor \dfrac{N}{3^{n}} \right\rfloor

 

このとき 0 以上の整数 n で常に a_{n}=b_{n} は成り立つか。

 

 

今回は以下の方針でこの問題を解決します。

・「a_{n}=b_{n} ならば a_{n+1}=b_{n+1} 」が正しければOK (数学的帰納法)

・「 \left\lfloor x \right\rfloor=M であること」と「 M\le x\lt M+1 であること」は同値であることを利用(床関数は不等式で定義される)

 

それでは以下、解答です。

解答

ある自然数 n について a_{n}=b_{n}=M が成り立つと仮定します。(M は正の整数)

すると \displaystyle a_{n+1}=\left\lfloor \dfrac{M}{3} \right\rfloor となります。

 

次に b_{n}=M より \displaystyle M\le \frac{N}{3^{n}} \lt M+1 が成り立ちます。(床関数の定義)

これにより

\displaystyle \frac{M}{3}\le \frac{N}{3^{n+1}} \lt \frac{M}{3}+\frac{1}{3}

を得ます。

ここで \displaystyle \left\lfloor\frac{M}{3}\right\rfloor \le \frac{M}{3} \lt \left\lfloor\frac{M}{3}\right\rfloor+1 (床関数の定義)から

\displaystyle \left\lfloor\frac{M}{3}\right\rfloor \le \frac{M}{3}

を得ます。

さらに M=3m+r (r=0,1,2) と書けたとすると

\dfrac{M}{3}+\dfrac{1}{3}=m+\dfrac{r+1}{3}

\displaystyle \left\lfloor\dfrac{M}{3}\right\rfloor +1 =\left\lfloor m+\dfrac{r}{3}\right\rfloor +1 = m+1

となるため

\displaystyle  \dfrac{M}{3}+\dfrac{1}{3} \le  \left\lfloor\dfrac{M}{3}\right\rfloor +1

が成り立ちます。

以上より

\displaystyle \left\lfloor\frac{M}{3}\right\rfloor \le b_{n+1} \lt \left\lfloor\dfrac{M}{3}\right\rfloor +1

となります。

したがって床関数の定義により、a_{n}=b_{n} となります。

(おわり)

 

まとめ

床関数の定義を駆使することで難なく疑問は解決されました。

ちなみに今回は「3で割った余り」で考えましたが「k で割った余り」というように変えても同じように問題解決ができます。

 

今回は床関数の使い方の紹介を「疑問解決」という観点で紹介しました。

最後までお読みいただきありがとうございました。