パズル万華鏡

面白いパズルの紹介と解説をします。

フィボナッチ数列を解く問題の考察

 フィボナッチ数列を解く問題の考察を示します。

 

問題の考察

 自然数nに関する命題P(n)に対して、つぎの(A)と(B)を示すことができるとき、自然数1以上のすべての自然数nに対して、命題P(n)は正しいと結論できる。

(A)自然数1において命題P(1)は正しい。

(B)1以上の任意の自然数kに対して、
   自然数nの値が1以上k以下のとき、命題P(n)が正しいならば、
   自然数nの値がk+1のときも命題P(k+1)が正しい。

 (A)と(B)が示されたとき、命題P(n)の正しさはつぎのように考えるとよい。

 まず、(A)が示されているので、nの値が1のとき命題P(1)の正しさがわかる。

つぎに、(B)が示されているので、2のときの命題P(2)の正しさがわかる。

1と2のときの命題の正しさがわかったので、再び(B)を適用すると、3のときの命題P(3)の正しさがわかる。

1,2,3のときの命題の正しさがわかったので、また(B)を適用すると、

4のときの命題P(4)の正しさがわかる。あとは同様。

f:id:isemba:20170809184825j:plain

f:id:isemba:20170809184838j:plain

フィボナッチ数列を解く問題の解1

 フィボナッチ数列を解く問題の解答例を示します。

 

問題の解1

f:id:isemba:20170809184612j:plain

f:id:isemba:20170809184625j:plain

フィボナッチ数列を解く問題

 フィボナッチ数列を解く問題を紹介します。

 

問題

 フィボナッチ数列{f(n)}は、

  f(n)= f(n-1)+ f(n-2) (n≧3)
  f(1)=1, f(2)=2

で定義される。f(n)を求めよ。

f:id:isemba:20170809184353j:plain

f:id:isemba:20170809184404j:plain

入場料金集金問題・考察2

 入場料金集金問題・考察2を示します。

 

考察2

 最初に集金する人について考察する。n個の○すべてについて調べれば、
最初に集金する人(複数の場合もある)を確定することができるが、簡単に一人見つける方法を紹介する。

 n個の○とn個の◎が円形の輪に並べられているとする。

この中から、時計回りに、○と◎が隣接しているものを取り除き、●●に置き換える。

この操作を1個の○と1個の◎が残るまで繰り返す。

ただし、○と◎の間の●は無視する。最後に残った○が最初に集金する位置となる。

同じ例で示す。

f:id:isemba:20170801191618j:plain

f:id:isemba:20170801191628j:plain

入場料金集金問題・考察1

 入場料金集金問題・考察1を示します。

 

考察1

 2以上の偶数2n(n≧1)に関する命題P(2n)に対して、つぎの(A)と(B)を示す
ことができるとき、2以上のすべての偶数2n(n≧1)に対して命題P(2n)は、正しいと結論できる。

(A)n=2において命題P(2)は正しい。

(B)整数k(k≧1)に対して、
  命題P(2k)が正しいならば、命題P(2k+2)が正しい。

f:id:isemba:20170801191435j:plain

f:id:isemba:20170801191449j:plain

入場料金集金問題の解

 入場料金集金問題の解答例を示します。

 

問題の解

 5000円札をもっている人を○、10000円札をもっている人を◎で表す。

図1で、9から始めると失敗するが、図2で、8から始めると成功する。円形の輪の位置を指定するために、1から10を使う。

f:id:isemba:20170801191046j:plain

 nに関する数学的帰納法で証明する。

(A)nの値が 1 のときは、まず、5000円札をもつ人から5000円札を受取る。

つぎに10000円札をもつ人から10000円札を受取り、5000円札を渡せばよい。

したがって、命題は正しい。

(B)nの値がkのとき、命題が正しいと仮定する。

つぎに、nの値がk+1のときも命題が正しいことを示す。

 n=k+1のとき、5000円札をもつ人の隣り(ただし、時計回り)に10000円札をもつ人の組を見つける。そういう組は必ずある。

f:id:isemba:20170801191120j:plain

この2人を除くと 2k 人になるので、仮定から釣り銭に不足することなく集金ができる。

f:id:isemba:20170801191150j:plain

最初に見つけた2人から集金する場合は、5000円札をもつ人から5000円札を受取り、つぎに10000円札をもつ人から10000円札を受取り5000円札を渡せばよい。

 すなわち、nの値がk+1のときも命題は正しい。

(A),(B)より、命題が証明された。

(注意)数学的帰納法では実施できることを示しているだけで、具体的にどの人
    から集金していくかは示していない。

f:id:isemba:20170801191230j:plain

入場料金集金問題

 入場料金集金問題を紹介します。

 

問題

 ある劇場の入場料は5000円とする。5000円札しかもっていないn(≧1)人と、
10000円札しかもっていないn人の合計2n人が劇場前の広場で勝手に円形の輪を作って開場を待っているとする。

 劇場の入口の受付人は、ある適当な人から時計回りに集金すれば、釣り銭に
不足することがないようにできることを示せ。

f:id:isemba:20170801190901j:plain