FC2ブログ

音楽から生まれた問題

コメントの投稿

管理者にだけ表示を許可する

問2の原作は162ですか?(計算しないでだしてみました)

音Aをたたくのを0、音Bをたたくのを1とする。
また、N回までたたく時の個数を"aN"であらわす。
N=1のときa1=2 {0} {1}
N=2のときa2=4 {00} {01} {10} {11}
N=3のときa3=6 {001} {010} {011} {100} {101} {110}
N=4のときa4=10 {0010} {0100} {0110} {1010} {1100}
           {0011} {0101} {1001} {1011} {1101}
N=5のときa4=16
漸化式つくれればできそうです...

おっと!いきなり正解ですね★
どうやって解いたんでしょう?それと、何故漸化式でできるのか、も説明が欲しいところ^^

>どうやって解いたんでしょう?
Excelです。0と1で8桁の文字列を作って、連続した4つの文字の和が0もしくは4になるを"if()"で表し、5つ全部"TRUE"と表示されないとき数字を表わすように"if()"で表し、"countif()"で数えました。
>何故漸化式でできるのか
前式との関係を表せればできるんじゃないかと・・・。最後に数字を足していくことを考えると、下二桁が同じ数字のときは1個で異なるときは2個になるので。

ぅ~~ん゛ excelじゃあ問題の面白さが分からないままでつまらないですねぇ。。
できれば機械なしで解いていただきたいw
>漸化式のこと
「下二桁が同じ数字のときは1個で異なるときは2個になる」ことは分かりましたが、
そこからどうやって漸化式が作れるのでしょうか?

騒々しいやり方だけども誰にでもわかる方法。
回数がnのとき、
最後が 00で終わる組み合わせの数を a_n
最後が 11で終わる組み合わせの数を b_n
最後が 01で終わる組み合わせの数を c_n
最後が 10で終わる組み合わせの数を d_n
組み合わせの総数を e_n とおく。 (任意のn∈Nに対しておいた)
まず、 0と1の対等性より、
a_n = b_n と c_n = d_n が成立する。
推移関係を調べる。
n+1回目において、
・最後が00であるためには、
 最後(n回目の)が 10の状態から 0をつけるしかないから、
 a_(n+1) = d_n = c_n ・・・?
・最後が 01 であるためには、
最後(n回目の)が 00 の状態から 1をつけるか、
  最後(n回目の)が 10 の状態から 1をつけるか、
  の2通りしかないので、
c_(n+1) = a_n+d_n = a_n+c_n ・・・?
e_nの決め方より、
e_n = a_n+b_n+c_n+d_n  
= 2a_n+2c_nであるから、
 
e_(n+2) = 2a_(n+2)+2c_(n+2)
= 2c_(n+1)+2(a_(n+1)+c_(n+1))
= 2(a_n+c_n)+2(a_(n+1)+c_(n+1))
= e_n+e_(n+1) (?と?をつかって変形した)
以上より、 e_(n+2) = e_(n+1)+e(n) が得られた。

おまけ。
計算機で求める場合は次の簡略式がある。
(興味があるのでしたら、証明すると宜しいです)
α = (1+√5)/2、
s = 1+5^(-1/2)と設定し、
[ ]をfloor関数とし、
t_n を以下のように定めると、
t_n = 1 (nが偶数のとき)、 t_n = 0 (nが奇数のとき)
e_n = [sα^n] + t_n である。
見てのとおり、nが奇数のときは、もっとも単純で
e_n = [s・α^n]   となる。 (偶数のときは +1する)
たとえば、 これを使って関数電卓(PCでも)で計算してみると、
e_99 = [s・α^99] = 708449696358523830150

わたしは情報処理〔数理〕が専門ですが プログラムが正しければ excelで解いた〔もしくは解ける〕で十分〔問題を解くにあたっては〕だと思います。
nが十分に大きいときは、手計算では厳しいですからね。
もちろん機械にも限界がきますが、手計算よりは遥かに現実的です。
ということはこの問題は以下のように解釈できます。
「十分大きいn〔ただし機械で計算可能な範囲で〕に対して、なるべく素早く結果が得られるプログラムまたは計算式を求めよ」
漸化式から一般項が得られますが、さてはて 機械で計算するにあたっては一般項と漸化式 どちらが素早く結果が得られるのでしょうか。
一般項〔無駄があります〕は上のコメントにあるように簡略でき、かなりましになります。
どっちがはやいか
答えは簡略式。

(>>ひ よ こ さん)
うわぁ、これは結構大変ですね; わざわざありがとうございます!!^^
僕の疑問にそぐう(?)ように書いてくださったみたいで。
そういうアプローチの仕方もありなんですねぇ。ただ、「連続2回まで」だからいいものの、この解き方を「連続3回まで」の場合(原作のほう)に適用するのは骨が折れそうですね(笑)。
[sα^n] + t_n の式について→そんな表し方があるんですね!
ガウス記号に慣れない僕には戸惑いを隠せない形です(苦笑)。 証明もちょt(ry
僕が用意していた答えはこちらでした。(一般項ですね。)
α=(1+√5)/2 , β=(1-√5)/2 として、 場合の数は 2/√5 * {α^(n+1) - β^(n+1)}
(漸化式からフィボナッチ数列を連想すればあとは簡単ですね。
e_1=2 , e_2=4 なので、この数列は、フィボナッチ数列の初項をとって(nをn+1にして)全体を2倍したものと同じということになります。 )
ひ よ こ さんには易しすぎませんでしたか?;;
でもコメント助かりました。どうもありがとうございます^^

(>>上祐さん)
ん~む、なるほど。簡略式というのはプログラムで便利なものなんですね。
情報処理には詳しくない僕のことなので当然、「なるべく素早く結果を出す」ことは全く考えておらず、一般項しか用意していませんでしたが、
簡略式の方がより現実的(?)な答えなのですね。
勉強になりました^^ありがとうございます^^

>問題をご覧の皆さんへ
まだ、すっきりとした解法はありますので是非考えてみてください。
もちろん、問1の答えも受付中♪

一般項に無駄があるというのは βに無駄があるのですね。
β^n→0 ですから
おおざっぱにいうとβはいらないんですね。
0でいいのです。
そこで微調整のために例の関数を導入するわけです。
〔'ほぼ'正確な値がほしいのなら、それすら要りませんが〕
いわゆる床関数(floor_function)〔ガウス記号という呼び方はグローバルにみると、あまり使われていません〕は微調整のためにあるのです。

なるほど。
一般項が終着点だとばかり思っていた僕にはとても新鮮な話ですね。

一般項が終着点だと思ってしまうのは、
おそらく(というか確実?)受験数学の結果でしょうか。
(そういう問題が多いからでしょうね)
たとえば、 フィボナッチ数列の一般項がありますよね。
{Fn}:= {1, 1, 2, 3, 5, 8, 13, 21, .......}  とおいておきます。
これの第8項は 見てのとおり 21 ですが、
一般項に n=8 を代入するわかりますが、
21(整数値)になることがなかなかわかりませんよね。
しかも 21を得るまでの計算が結構面倒ですよね。
こういう点からみると、漸化式そのもののほうが価値があるとおもいませんか。
第50項求めよ(計算機なしで)といわれて、
一般項にn=50代入しませんよね。(死にます)
逆に、一般項に価値があると思えるのは、
大小関係がわかりやすい(場合によりますがね)ということでしょうか。
F_n = (1/√5) * {α^(n+1) - β^(n+1)}  で、
βはほとんどゴミですので、
Fn ≒ (1/√5) * (α^(n+1))  というように
漸化式のときより大きさが明確ですよね。
1.61 < α < 1.62  ですから、
たとえば、 (1.6)^n と F_n どっちが大きいかっていわれたら、
十分大きいnに対しては、 F_nのほうが大きいとわかりますね。
話がかわりますが、
この問題のk連続(まで許す)の場合までに
一般化できるような解答はもっていますか?
私も考えてみたのですが、
k連続の場合では、おそらく、
E_(n+k) = E_(n+k-1)+E_(n+k-2)+・・・+E(n+1)+E(n)
が成立することが予想できるとおもうのですが、
力不足で、この成立を示すことはできませんでした。
この漸化式を得られるような解答を、
もしよければ、〔持っているのならば〕教えてほしいです。
ではでは。

>>一般項が終着点と思ってしまうのは
まさにその通りだと思います。漸化式があったらほとんどの場合は一般項出させますからね^^;;
いやぁ、 n=50の例は面白いくらい納得できました。
一般項、漸化式、簡略式、、、目的によってそれぞれが活かされてくるんですね・・・奥が深い…!
本当、色々ありがとうございます^^
条件をk回連続までの場合にすると、おっしゃるとおり、
E_(n+k) = E_(n+k-1)+E_(n+k-2)+・・・+E(n+1)+E(n) が成立しますね。
もともとこれが言いたくてこの問題を出したようなものです^^
数学的な知識は必要なく、ちょっと違った視点で見るとわかるものです。
条件を逆手に取ることがポイントですね。
できれば誰か解かった人が、書いてくれることを期待したいですねぇ。。

解答もっているんですね。
よろしければ書いてくれませんか。
そんなにすぐその漸化式の成立が証明できるというのは
興味深いとおもいまして。
こじつけ的説明が思い浮かびません。
私の予想ですと、
それをここに書いてくれる人は他にいないかと。
(ほとんど期待できないと思います)
解答に興味がある人は私以外にもいると思いますし。
どうでしょうか。
解答うp期待してます。
プロフィール

ピエエル

Author:ピエエル
お越し頂きありがとうございます。
IT・通信系の特許を書く会社員になりました。二年目で修行中。
綴る内容はパズル,脳トレ,吹奏楽,合唱,特許などなど…興味のあるカテゴリからどうぞ、ゆっくりごらんください。
パズル・クイズは特に説明のないものは自作です。

コメントはマナーさえ守ればどなたでも気楽に書いてOKです。
(パスワードは各自の編集用。記入はご自由に。)

※2009年9月22日にCURURUというところから引っ越してきました。

カテゴリ
最新コメント
最新トラックバック
月別アーカイブ
FC2カウンター
検索フォーム
RSSリンクの表示
リンク
ブロとも申請フォーム

この人とブロともになる

QRコード
QRコード