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

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

MENU

【問題】剰余で作った漸化式と極限「空き瓶交換でどれだけ飲めるか問題の一般化」

「酒屋さんに空き瓶を3本持って行ったら新しいもの1本と交換してもらえます。最初に100本買った場合、この空き瓶交換を繰り返せば合計何本飲めるでしょうか?」

この算数で題材となる話を一般化し、「漸化式」や「極限」からアプローチしていこうと思います。

 

 

 

問題

 

問題

m2 以上の整数、a を正の整数とする。

商店Sでは瓶入りジュースAを販売している。この商店ではジュースAの空き瓶を m 本持って行くと新品のジュースA 1 本と交換してもらえる。

 

最初に新品のジュースAを a 本買った場合、交換して手に入れたものも含めジュースAを合計何本飲めるか。

ただし、

・何度も交換することは可能とする。

・空き瓶はジュースAを飲む以外の手段では手に入れられないとする。

 

方針

飲み干す→空き瓶を交換する→飲み干す→…の繰り返しを考えます。

交換で手に入る新品のジュースの本数はおおよそ 1/m ぐらいになりますので、いつかは尽きることが予想できます。

そこでこのことを漸化式を用いてきっちり立式していきます。 

 n 回目の交換で新品のジュースを a_{n} 本手に入れたとすれば、数列\{ a_{n} \} について無限級数を考えれば収束(これも示します)し、その和が求めるべき答えとなります。

ただし a_{n+1}=\dfrac{a_{n} }{m} は一般には成り立ちません。

そこで m で割った余りまで目を向ける必要が出てきます。

 

解答1(漸化式の利用)

a_{0}=a , r_{0}=0 とし、以下次の要領で数列 \{ a_{n} \}\{ r_{n} \} ( n=0,1,2,3,\dots )を定めます。

 \displaystyle a_{n+1}=\lfloor  \frac{a_{n}+r_{n}}{m} \rfloor  …①

 a_{n}+r_{n}=ma_{n+1}+r_{n+1} …②

(実数 x に対して  \lfloor x \rfloor x を超えない最大の整数を表すこととします。)

すると「毎回空き瓶を可能な限り交換してもらう」という動きにした場合、

a_{n}n 回目の交換で入手できる新品のジュースの空き瓶の本数

r_{n} は n 回目の交換で使われなかった空き瓶の本数

に対応していることが分かります。*1

このことから、と言ってもいいですし①,②からと言っても良いですがすぐに次のことが分かります。

a_{n}0 以上の整数。

r_{n}0 以上 m-1 以下の整数。

 r_{n+1} は①,②から「 a_{n}+r_{n}m で割った余り」とも表現できます。

 

さて、いくつかのステップに分けて答えを導き出したいと思います。

 

 

Step1 収束の確認 

準備として b_{n}=a_{n}+r_{n} ( n=0,1,2,3,\dots ) を用意します。

すると等式②から

b_{n}=b_{n+1}+(m-1)a_{n+1}

すなわち

b_{n}-b_{n+1}=(m-1)a_{n+1}

を得ます。

 m \ge 2a_{n+1}\ge 0 から

b_{n} \ge b_{n+1} (等号は a_{n+1}=0 のときに限り成り立つ)

となります。

そこで任意の正の整数 n について a_{n} \gt 0 と仮定すると

b_{n} \gt b_{n+1} 

を得て  \{ b_{n} \} は単調に減少する整数の数列となりますが

 b_{a+1} \le b_{0}-(a+1) \lt 0

となってしまい

a_{n} \ge 0 , r_{n} \ge 0 であることに矛盾します。

したがってある正の整数 k について a_{k}=0 となります。

さらにこのような  k を1つ選ぶと①と r_{k}\le m-1 から

 \displaystyle a_{k+1}=\lfloor  \frac{r_{k}}{m} \rfloor =0 

となるので

a_{k}=a_{k+1}=a_{k+2}=\cdots=0 

が成立します。

さらに②から

r_{k}=r_{k+1}=r_{k+2}=\cdots=r 

と書けます。

 

また、

b_{n}=a_{n}+r_{n} 

から

b_{k}=b_{k+1}=b_{k+2}=\cdots=r 

も得られます。 

 

以上により

\displaystyle \sum_{n=0}^{\infty} a_{n} は収束すること、特に  \displaystyle\lim _{ n\to \infty}a_{n}=0 となること、

 \displaystyle\lim_{n \to \infty} r_{n}=\displaystyle\lim_{n \to \infty} b_{n}=r

が分かります。

 

なお、ここで出てきた r ですが、

r=0 と仮定すると

ある正の整数 k について a_{k}=r_{k}=0 となるため、②により a_{k-1}+r_{k-1}=0 すなわち a_{k-1}=r_{k-1}=0 を得ますが、これを繰り返すと  a=a_{0}=0 となってしまいます。

したがって  1\le r \le m-1 となります。

 

 

Step2 極限値を漸化式から計算

 \displaystyle S=\sum_{n=0}^{\infty} a_{n} とおきます。

Step1の途中で出てきた等式 b_{n}-b_{n+1}=(m-1)a_{n+1} について、Step1の結果より

 \displaystyle \sum_{n=0}^{\infty} (b_{n}-b_{n+1}) =(m-1) \sum_{n=0}^{\infty} a_{n+1}

を得ます。

左辺を計算することで

 b_{0}-r=(m-1)(S-a) 

となりますが

 b_{0}=a_{0}+r_{0}=a

から

a-r=(m-1)(S-a)

が成り立ち、これを整理することで

\displaystyle S=\frac{ma-r}{m-1}

となります。

 

Step3 rの決定

 

これで求めたい「合計何本飲めるか」を表す S を計算できたように思えますが、r が計算できていません。そこで次のように考えます。

定義から S は正の整数です。

しかし一般に正の整数 l について \displaystyle \frac{ma-l}{m-1}l の値によっては正の整数にはなってくれません。

そこで Step1 で調べたように  1\le r \le m-1 であることを使います。

 ma-1,ma-2,\dots , ma-(m-1) は連続する m-1 個の整数なので、この中で m-1 の倍数は  1 個に限られます。

つまり ma-r ma-1,ma-2,\dots , ma-(m-1) の中で m-1 の倍数であるもの(言い換えれば \displaystyle \frac{ma-l}{m-1} が整数となるもの )と一致することになります。

したがって \displaystyle S=\lfloor \frac{ma-1}{m-1} \rfloor と書くことが出来ます。 

 

(答え) \displaystyle S=\lfloor \frac{ma-1}{m-1} \rfloor  

 

(例)

m=3 , a=1000 のとき

 \displaystyle S= \lfloor \frac{3000-1}{2} \rfloor =1499

より3本の空き瓶を新品1本に交換してもらえる場合は1000本最初に買うと合計1499本飲めることになります。

 

解答2(算数的な解法)

ここまで、数列や漸化式、極限といった高校数学の道具をガンガン使いましたが「算数的な有名な解法」も一応ありますので紹介します。解答1でひねり出した答えの形がヒントになっています。(おそらく"ググってみる"とこちらの方がヒットすると思います。)

まず、最初に買った a 本を飲んでできる空き瓶を次のように分けます。

①1本だけ除外します。

②残り a-1 本を m-1 本ずつまとめていきます。

③余った r 本は放置します。

 

流れとしては①を起爆剤にして

②の空き瓶に合流させます。すると m 本のまとまりができるので、これを新品に交換すると新たに空き瓶1本に生まれ変わります。

これを①と同様に起爆剤にして次の m-1 本のまとめた空き瓶に合流させます。

以降、これを繰り返すと②でまとめたときの"組"数だけ新品交換ができることが分かります。

つまり a-1m-1 で割った余り \displaystyle \lfloor \frac{a-1}{m-1} \rfloor 本だけ新品交換できたことになります。

つまり  S= a+ \displaystyle \lfloor \frac{a-1}{m-1} \rfloor =\displaystyle \lfloor \frac{ma-1}{m-1} \rfloor となります。

 

まとめ

解法1では漸化式や極限という大道具を用いて「空き瓶問題」を解いてみました。

解法2まで見てしまうと、印象が変わってしまいますが、結果的に「○○で割った商や余りで作られた漸化式」の無限級数を計算できたという成果があったので、これはこれで良いのでは?と思っています。

 

今回は以上になります。最後までお読みいただきありがとうございました。

それでは次回もどうぞよろしくお願いします。

 

 

*1:この部分が分かりにくい場合は a_{n}=11 r_{n}=2 なので試してみましょう。