FC2ブログ

音楽から生まれた問題、解答。

コメントの投稿

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

なるほど~
  n回目から見ていったわけですね。
  検討してみましたが、
  明らかに正しいですね。
  そういえば、10年以上前に(受験生?)、
  そういう問題をやったことがありました。

  漸化式の説明になっていますね
  すばらしい解答をありがとう!
  

私が問題を考えたという証として、
次の結果を伝えておきます。
k連続の場合で、
k<n≦2kの場合は、
E_n = 2^(n-k-1)・(2^(k+1)-(n-k+1))
(e.g. k=3のとき、 n=6とすると、 E_6 = 48
(探索可能範囲がkのオーダーで増えますね)
というかなり良好な式(見かけの問題と、それにともなって、
数論的性質がみえやすくなっていますね)があります。(これは示しました)
(上の解答をみるかぎり、ピエエルさんにとっては、
 これを示すものはまったくの別の問題にみえるかもです)
ではでは。

「追記」
floor_functionを用いるならば、
k<n≦2kの限定を、
2kから一般に拡張できて、
E_n を表す式が求められそうです。
(PCで計算しやすそうな形)
(ちなみに k連続の場合の漸化式を解いても、
 虚数だらけの(形式だけの)実用的ではないものがでてきます)
しかしながら、わたしはその漸化式の成立を示す解答
(たとえば、ピエエルさんによる)が
肝要だとおもっていたので、
あえてそのような一般のE_nをfloorとΣを用いたものを
持ち出しませんでした。
k<n≦2kの場合で、
E_n = 2^(n-k-1)・(2^(k+1)-(n-k+1)) と表せることについてですが、
これは計算もしやすいですね。
良問うpありがとうでした!
このような数学的問題をまた期待しています。
おつかれさまです。

E_n = 2^(n-k-1)・(2^(k+1)-(n-k+1))
・・・なるほど!余事象の考え方から求めるのでしょうか。
気づきませんでした。これは計算しやすいですね!
上祐さんはどんどん新しいことを教えてくだるので、ますます数学が好きになってしまいそうです(笑)。
こんなに深く僕の問題を考えてくださる方がいて、嬉しい限りです^^
数学的な問題は…(今のところ思い当たりませんが(汗))今後もし思いついたら…ですかね;;
こちらこそありがとうございました! おつかれさまです^^

かえで馬鹿だからわからないけど、
googleで、キーワードを(たとえばcururuとか)いろいろいじってみたら、
ここにたどり着いたネ(・∀・)!
しかも、偶然にも知ってる問題(=゚Д゚=)) (解答も)
フィボナッチ数列ってきいたら、
かえでアタック炸裂だネ!
フィボナッチ数列を{F_n}とし、
p∈{primes} とするとき、
p│F_(p-1) となるような
pの必要十分条件を求めよ。
C U (*^ー゚)/~~

か、かえでさん…!! あなたのことはよく存じておりますっっ。
まさかここにコメントしてくださるとは…!!(慌)
かえでさんはフィボナッチ数列がお好きなのでしょうか。
たくさんの性質があるので面白いですもんね^^
僕の出した問題もフィボナッチ数列が出てくるほどですから、結構ありがちな(?その方面ではよく知られた)問題なのかもしれませんね。
その問題は…
フィボナッチ数列の数々の性質もそれほど身についていない僕に、解るレベルなのでしょうか…(汗)、とても不安ですが、出されたからには頑張って考えてみようと思います。
F_pではなくF_(p-1) なんですね…難しそう…。
すみませんが、少し考える余裕(猶予か?)をください;;

ぅぐぐ・・・。
昼休みや自習時間使って考えてみましたが、どうも僕の頭では、これを自力で解くには相当な時間が要りそうです。。
フィボナッチ数列の性質、「割り切れる」が意味するもの、、などについてもっと深い理解が必要なようで…。
練習の足りない僕は、まずアプローチの仕方から躓いています(汗)。
必要条件を洗い出して、それが十分条件になることを示すか、
条件を満たすpから、逆に答えを予想して示すか、、はたまた別の方法があるのでしょうか?^^;;
大変興味のある問題です。もし良かったらまたコメントをください。

登場ヽ(゚∀゚)ノ パッ☆
まず実験。
{F_n} := {1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, ...... , ...}
F_(p-1)とF_pの値を書き出してみると、
答えが予想できるハズネ
予想: p≡±1 (,mod. 5)
ヒントは次の補題かナ
(a,b)をコンビネーションaCbとする。
[補題]
nが偶数のとき、
2^(n-1)・F_n= n+(n,3)5+(n,5)5^2+(n,7)5^3+......+(n, n-1)5^((n/2)-1)
まずこれを示してみよう。

おぉ~~~★ かえでさん、ヒントありがとうございます!!
確かにp≡±1(mod. 5)でいけそうですね!
>[補題]
最初見たときは正直気が遠くなりそうでした・・・^^;;
数学的帰納法なんかを試そうとして漸化式を変化させたりして、と、長いこと回り道をしていました。情けない・・・orz
[補題の解答]
一般項を表す式の両辺をいったん√5*2^n倍すると右辺は (1+√5)^n-(1-√5)^n
展開して整理すれば 2*{(n,1)√5+(n,3)(√5)^3+(n,5)(√5)^5+......+(n,n-1)^(√5)^(n-1)}
両辺を2√5で割ると 2^(n-1)・F_n = n+(n,3)5+(n,5)5^2+(n,7)5^3+......+(n, n-1)5^{(n/2)-1}
が得られる ・・・(証明終わり)
さて、ここからは整数問題になるのでしょうか・・・。
p≠2は明らか、よってp-1は偶数なので補題の式のnをp-1に置き換えた式が成り立つ・・・。
一応ここまで書けましたが、、それでどうしよう・・・。もう少し考えて見ます^^

うんうん。
次の補題もあげておくネ(=゚Д゚=))
1) pが奇素数のとき、 2^(p-1)≡1 (mod. p) が成立。
2) (p, i) は 任意の i (1≦i<p)に対して、 pで割り切れる。

3) (F_n)^2-(F_(n-1))・(F_(n+1)) = (-1)^(n-1) が成立。

えぇっ! こんなに使うんですか!?(・.・;)
(1)(2)が解るとグンと近づけそうですね。
(3)も何やら良い雰囲気をかもし出している・・・w(今度こそ漸化式の出番でしょうか。)
こんな性質もあるんですかー…フィボナッチ数列って面白いなぁ…!!
すみません、なんだか教えてもらっちゃっていて(;´ `A``
でもかえでさん優しくて嬉しいです(^^  頑張ってみます♪

やさしくないッて(〃▽〃)キャッ
証明のヒントね(≡゚∀゚≡)
2) 一般に (n, r) = (n/r)・(n-1, r-1)が成立していること
1) 2=1+1 と 2)を使う
3) 計算あるのみ
 ファイトォ*:.。..。.:*・゚(n‘∀‘)η゚・*:.。..。.:*!!!☆

(2)
(p,i)= p・(p-1,i-1)/i が成立、また(p,i) , (p-1,i-1)は整数である
ここでpは素数かつp>iよりpはiで割り切れない
したがって(p,i)はpを因数に持つ(pで割り切れる) ・・・(証明終わり)
(3)漸化式を使ってみました。
(F_n)^2-(F_(n-1))・(F_(n+1))
=(F_n)^2-(F_(n-1))・(F_n + F_(n-1))
=(F_(n-2) + F_(n-1))^2 - (F_(n-2) + F_(n-1) + F_(n-1))
=(F_(n-2))^2 - (F_(n-1))・(F_(n-2) - F_(n-1))
=(F_(n-2))^2 - (F_(n-1))・((F_(n-2))
これより、nが偶数のとき
左辺=(F_(n-2))^2 - (F_(n-1))・((F_(n-3))=......=(F_2)^2 - (F_1)・(F_3) = 1-2 = -1
nが奇数のとき 左辺=......=(F_3)^2 - (F_2)・(F_4) = 4-3 = 1
ゆえに
(F_n)^2-(F_(n-1))・(F_(n+1)) = (-1)^(n-1) がいえる ・・・(証明終わり)
(1)なるほど!
2^p = (1+1)^p
=1 + (p,1) + (p,2) + (p,3) +.......+(p,p) ≡2 (mod. p)
pと2は互いに素なので (2^p)/2 ≡2/2 (mod .p)
よって2^(p-1)≡1 (mod .p) ・・・(証明終わり)
(1)につまづいていたせいでその先もうまくいかないなと感じていましたが、
modの感覚がちょっとですがつかめてきたのでいけるかもしれません!数学楽しい★

↑・・・と豪語したものの、意外とヒント同士をうまくかみ合わせることが出来なくて、
そして p≡±1 (mod. 5) につなげる過程も見えてきません・・・orz
・・・今どの段階まで来ているのか不安になってきました(笑;)
まだまだ知っておくべきことってあるんでしょうか・・・?

必要な補題はまだあるネ!
といっても、これで必要なのはもうないと思う ミ l v l) ノ
(4) 奇素数pに対して、
    aをpと互いに素な正整数として、
x^2≡a (mod. p)を満たす整数xが存在するとき、
(a/p)= +1,
    存在しないとき、
(a/p)= -1
  と書くとすれば、
    a^((p-1)/2)・(a/p) ≡ -(p-1)! (mod p) が成立する。
(5) (p-1)! ≡ -1 (mod. p) が成立する。
(6) a^((p-1)/2) ≡ (a/p) (mod p) が成立する。
(7) [GaussのLemma]
m, 2m, 3m, 4m, ......, ((p-1)/2)m の中で、
pを法とする最小の正の剰余が p/2より大きいような
    数の個数を μとすると、
    (m/p) = (-1)^μ  が成立する。
(8) p≡ ±1 (mod.10) ⇒ (5/p) = +1
p≡ ±3 (mod.10) ⇒ (5/p) = -1
が成立する。
証明 ファイトォ*:.。..。.:*・゚(n‘∀‘)η゚・*:.。..。.:*!!!☆
(今までにあげた補題はどれもあっちの世界では常識なので、
 証明できたものは、以後、常識として使っていいと思うネ"c(-。-,,)c)

嗚呼っ「あっちの世界」・・・!! スゴいですねぇ、憧れます。。
自分がいかに数学のほんの一部分しか知らないかを思い知らされますね。
かえでさんのお蔭で、そこに少しでも近づこうとすることが出来ていてすごく嬉しいです。
補題・・・あとこれがわかれば・・・解けるんですね!わくわくしてきましたw
今度は合同式の性質(?)オンパレードですね。
(a/p)という概念も初めて聞きます(←致命的?)・・・これは苦戦必至ですね(汗)。
気長に待っていてくださると嬉しいです(^^:;

(4)の証明は厳しいかもだから、
ヒント出すネ ヘ(^-^ヘ)(/^-^)/
(4')
E = {kx: a∈N (1≦k<p) } とする。
このとき、次が成立する。
α∈E ⇒ ∃1β∈E α・β≡a (mod p)
∃1 というのは、存在が唯一ということです。
まずこの(4)’を示してみてください。

どこまでも手のかかる奴でホント申し訳ないんですが、(汗)
(4')は言葉でいうとこんな感じになるのでしょうか?(お恥ずかしい)
「自然数aと奇素数pについてx^2≡a (mod. p)を満たす整数xの、倍数
 x,2x,3x,......,(p-1)x のうち、どの倍数(mx)をとっても、
 それぞれの倍数に対して、mx・nxが法pに関してaと合同になるようなnxが、
 1≦n≦p-1の範囲でただ一つ存在する」
これなら「m,2m,3m,......,(p-1)mをpで割った余りは全て異なる」ことを示せばいいのかなぁ、、なんて思ったり。。
あと、これを使って(4)を示すんですよね。
その後、(5)と組み合わせて(6)を示す…っていうプロセスでいいのでしょうか?
(余談)図書館で「ガウス整数論」借りてみました^^
「自分が受験生じゃなかったらこの世界に没頭していられるのになあ!」ってつくづく思うんですよね。。

◆ブログをご覧のみさなんへ◆
コメントにあるフィボナッチ数列の問題については解決・終了いたしました。
プロフィール

ピエエル

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

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

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

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

この人とブロともになる

QRコード
QRコード