kasama

フィボナッチ数列？

湘南　　 10月6日（木） 0:17:21　　 　　38424

cyclone

１枚のとき１通り ２枚のとき２通り ３枚のとき３通り ４枚のとき５通り ５枚のとき８通り ここまでやって勘でフィボナッチ数列

10月6日（木） 0:19:06　　 　　38425

タロタロ

差が１、で成り立たせるには隣り合う２つを入れ替えるしかない。 というところで、ペアの個数で場合分けして数え上げてしまいました。 よく考えたらフィボナッチ数列でしたね。 14段の階段を1段か2段で登るのと同じ。 ところで、つい先程50才になりました。

10月6日（木） 0:21:01　　 　　38426

ちゃーみー

1番に1 → 1 枚減った状態 1番に2 → 2番に1 → 2 枚減った状態 ということで，フィボナッチですね。 #38426 おめでとうございます！

10月6日（木） 0:23:54　　 　　38428

Ｍさん

私もものすごい計算で５枚までのパターンを調べて フィボナッチかなあと思って送りました。

第２グループ　　 10月6日（木） 0:26:03　　 HomePage:受付中　　38429

小学六年生

なんとなく（？）で解きました。【１】→1通り【２】→２通り【３】→３通り【４】→５通り　となったので、素直にフィボナッチ数列として受け取りました。どなたか、なぜなのか教えていただけませんか。すみません。いつもフィボナッチ数列がよく分からない・・・

地底世界　　 10月6日（木） 0:27:48　　 　　38430

かかか！

また20分オーバー… タロタロさんと同じでペアの個数で場合分け。 1+8Ｃ2＋9Ｃ4＋10Ｃ6＋…みたいな式が延々と続き 610。フィボナッチがあったとは…

10月6日（木） 0:28:42　　 　　38431

Ｍｒ.ダンディ

皆さんと同じように　フィボナッチ数列となることに気が付いたのですが、時間がかかりすぎました。 #38426 おめでとうございます。

10月6日（木） 0:34:39　　 　　38432

しぶやん

はじめ、何故か完全順列などを考えてしまい、フィボナッチ数列に気づくまでに時間がかかってしまいました。 例えば、カードが5枚のとき ・5のカードが5の箱に入っている場合→1〜4のカードのみを考えれば良い ・5のカードと4のカードを入れ替えた場合→1〜3のカードのみを考えれば良い 以上より、カードが5枚の場合は、カードが4枚の場合とカードが3枚の場合を合計すれば良いことになります。このようにしてフィボナッチ数列に気づきました。

10月6日（木） 0:41:46　　 　　38433

abcba@jugglermoka

1差で箱に入れる時は必ず隣同士と入れ替えになる。結局はペアが7〜0この場合を足しました。皆様と同じ解法だと思います。

10月6日（木） 0:44:07　　 　　38434

ゴンとも

十進basicで羅列させました。 for a=1 to 2 for b=1 to 3 if b=a then goto 130 for c=2 to 4 if c=a or c=b then goto 120 for d=3 to 5 if d=a or d=b or d=c then goto 110 for e=4 to 6 if e=a or e=b or e=c or e=d then goto 100 for f=5 to 7 if f=a or f=b or f=c or f=d or f=e then goto 90 for g=6 to 8 if g=a or g=b or g=c or g=d or g=e or g=f then goto 80 for h=7 to 9 if h=a or h=b or h=c or h=d or h=e or h=f or h=g then goto 70 for i=8 to 10 if i=a or i=b or i=c or i=d or i=e or i=f or i=g or i=h then goto 60 for j=9 to 11 if j=a or j=b or j=c or j=d or j=e or j=f or j=g or j=h or j=i then goto 50 for k=10 to 12 if k=a or k=b or k=c or k=d or k=e or k=f or k=g or k=h or k=i or k=j then goto 40 for l=11 to 13 if l=a or l=b or l=c or l=d or l=e or l=f or l=g or l=h or l=i or l=j or l=k then goto 30 for m=12 to 14 if m=a or m=b or m=c or m=d or m=e or m=f or m=g or m=h or m=i or m=j or m=k or m=l then goto 20 for n=13 to 14 if n=a or n=b or n=c or n=d or n=e or n=f or n=g or n=h or n=i or n=j or n=k or n=l or n=m then goto 10 print a;b;c;d;e;f;g;h;i;j;k;l;m;n 10 next n 20 next m 30 next l 40 next k 50 next j 60 next i 70 next h 80 next g 90 next f 100 next e 110 next d 120 next c 130 next b 140 next a end f9押して610通りを羅列！

豊川市　　 10月6日（木） 0:54:35　　 MAIL:fttnm528@ybb.ne.jp 　　38435

スモークマン

やっと気づけましたぁ...^^;... １箱の1個入ってる場合にはすぐ気づけたのですが... 漸化式で考えました!! f(14)=f(7)^2+f(6)^2=21^2+13^2=610 f(7)=f(3)^2+2*f(2)*f(3)=3^2+2*2*3=21 f(6)=f(3)^2+f(2)^2=3^2+2^2=13 ♪

金光＠岡山　　 10月6日（木） 1:18:19　　 　　38436

あめい

ｎ個の場合、「ｎ−１個の時にｎをくっつける方法」と「ｎとｎ−１を入れ替えてｎ−２個の時にくっつける方法」の２パターンがあるので（ｎ個の場合）＝（ｎ−１個の場合）＋（ｎ−２個の場合）とフィボナッチ数列になりました。問題を見て数列かなとやっとすぐ浮かぶようになり、続けていてやっと頭のサビも落ちてきたかなと自己満足しています。もっともこの後の足し算で間違えてしまい、ここに３回目で入れたのですが・・・

10月6日（木） 5:45:50　　 　　38437

uchinyan

はい，こんにちは。さて，今回の問題は．．． これは，算チャレとしては標準的かなぁ。こんな感じで。 (解法1) 1 〜 n のカードと n 個の箱の場合を a(n) 通りとします。 n のカードは n-1 又は n の箱に入れることだけができます。 n の箱に入れたときには，残りが 1 〜 n-1 のカードと n-1 個の箱なので a(n-1) 通り，で， n-1 の箱に入れたときには，n の箱には n-1 しか入らないので，残りが 1 〜 n-2 のカードと n-2 個の箱になって a(n-2) 通り，です。 つまり，a(n) = a(n-1) + a(n-2) になります。ただし，a(2) = 2，a(1) = 1，です。 求めるのは a(14) なので， a(1) = 1，a(2) = 2，a(3) = 3，a(4) = 5，a(5) = 8，a(6) = 13，a(7) = 21，a(8) = 34，a(9) = 55，a(10) = 89， a(11) = 144，a(12) = 233，a(13) = 377，a(14) = 610 そこで，610 通り，になります。 (解法2) 例えば，8 のカードを考えます。このカードは 7，8，9 の箱にだけ入れることができます。 8 のカードが 8 の箱に入った場合は，問題ありません。 8 のカードが 7 の箱に入った場合は，8 の箱には 7 か 9 のカードが入りますが， もし 8 の箱に 9 のカードが入ったとすると， 7 のカードは 6 の箱に，6 のカードは 5 の箱に，．．．2 のカードは 1 の箱に，入るしかなく，1 のカードの入る箱がありません。 そこで，8 の箱には 7 のカードが入るしかありえません。 8 のカードが 9 の箱に入った場合も同様で，8 の箱には 9 のカードが入るしかありえません。 他のカードでも同様なので，結局，カードは同じ番号の箱に入るか，隣同士の番号とクロスして入るか，のいずれかになります。 そこで，場合の数は，番号が同じとクロスとを並べる場合の数に等しくなります。 全体でカードは 14 枚なので，番号が (同じ，クロス) の回数は， (14,0)，(12,1)，(10,2)，(8,3)，(6,4)，(4,5)，(2,6)，(0,7) これより，求める場合の数は，それぞれを並べる場合の数の和になって， 14C0 + 13C1 + 12C2 + 11C3 + 10C4 + 9C5 + 8C6 + 7C7 = 1 + 13 + 66 + 165 + 210 + 126 + 28 + 1 = 610 通り になります。

ネコの住む家　　 10月6日（木） 11:05:58　　 MAIL:uchi@sco.bekkoame.ne.jp 　　38438

uchinyan

掲示板を読みました。 #38426，#38431，#38434，#38438の(解法2) カードの番号と箱の番号の差が 1 で可能なのは，同じ番号に入れるか，隣り合う二つを入れ替えるしかない， ということに着目して可能な場合を調べて解く解法。 #38428，？#38432，#38433，#38437，#38438の(解法1) カード 1 が箱 1 に入るのは一つ減った状況，カード 1 が箱 2 に入るのはカード 2 が箱 1 に入るしかないので二つ減った状況， ということから漸化式を導いて解く解法。漸化式はフィボナッチ数列のものになります。 #38436 まず，与えられた条件から，全体の場合の数は， カード 1 〜 7 が箱 1 〜 7 に入り，カード 8 〜 14 が箱 8 〜 14 に入る場合か， カード 1 〜 6 が箱 1 〜 6 に入り，カード 7 が箱 8 に入り，カード 8 が箱 7 に入り，カード 9 〜 14 が箱 9 〜 14 に入る場合，のいずれか， に着目し，以下，カード 1 〜 7 で箱 1 〜 7，カード 1 〜 6 で箱 1 〜 6，なども同様に考えて，漸化式を導いて解く解法。 ただ，恐らく，考えの途中では，#38426などの着目点も使っていると思われます。 ちょっと面白い解法です。 #38424，#38425，#38429，#38430 ある程度調べるなどして，フィボナッチ数列かな，と予想して解く解法。 #38435 プログラムによる解法。

ネコの住む家　　 10月6日（木） 11:50:55　　 MAIL:uchi@sco.bekkoame.ne.jp 　　38439

???

Option Explicit Dim a(14) As Integer Sub Macro1() Cells(1, 1).Value = 0 Call saiki(1) Range("A1").Select End Sub Sub saiki(ByVal n As Integer) Dim j As Integer a(n) = Application.max(1, n - 1) While a(n) <= Application.Min(n + 1, 14) If onaji(n) = 0 Then If n < 14 Then Call saiki(n + 1) Else Cells(1, 1).Value = Cells(1, 1).Value + 1 For j = 1 To 14 Cells(Cells(1, 1).Value, j + 1) = a(j) Next j Range("B" & Cells(1, 1).Value).Select End If End If a(n) = a(n) + 1 Wend End Sub Private Function onaji(ByVal n As Integer) As Integer Dim j As Integer onaji = 0 j = 1 While onaji = 0 And j < n If a(j) = a(n) Then onaji = 1 Else j = j + 1 End If Wend End Function

10月6日（木） 13:56:10　　 　　38440

ｐｐｐ

いつも面白い問題をありがとうございます。 「過去問」の図を表示させてもらうことは可能でしょうか

10月6日（木） 14:09:31　　 　　38441

あみー

リンクがよく切れてるんですよね、なぜか。 過去に道順の問題で同じ傾向の問題があったような気がしますね。

10月6日（木） 15:11:20　　 　　38442

imai

フィボナッチ数列になるみたいですね。

10月6日（木） 15:46:31　　 　　38443

ハラギャーテイ

数字の数を増やしながらプログラムで計算したらフィボナッチ数列が出てきた。 考えたらわかりそうだが、最近、歳のせいで何をやるのも面倒になってきた。

山口市　　 10月6日（木） 18:09:32　　 HomePage:制御工学にチャレンジ　　38444

せ

場合の数は苦手です。 隣り合う箱どうしのみ交換可能から 箱とカードの番号がすべて一致→１２ヶ所一致→１０ヶ所一致・・・・２ヶ所一致→すべて不一致の全パターンを数え上げました。 フィボナッチ数列とは・・・

10月6日（木） 19:05:31　　 　　38445

aibo

できた。 これは数列ですね。 1、2、3、5、8、13、21、34、55、89、144、233、377、610 全くわからなかったので、 箱を１つの場合から考えて数え上げていくと規則を発見しました。 この規則を発見したときは歓喜でした。 解けて嬉しい。

10月7日（金） 1:12:33　　 HomePage:aibo　　38446

あみー

これ，差が２まで許すと酷い問題になりますね…。 どうすっかなあ。

10月9日（日） 16:58:29　　 　　38447

スモークマン

#38447 途中までは出せるんだけど...f(7) の計算の方法が急にわからなくなったり...^^;;...? f(1)=1 f(2)=2 f(3)=3!=6 f(4)=f(2)^2+2*f(3)-2=14 f(5)=f(2)^2+f(3)+2*f(2)*f(3)-3=31 f(6)=f(3)^2+f(2)^2+f(4)+2*f(3)*f(2)-5=73 f(7)=??? 1,2,6,14,31,73,172,400,...ってな数列になるようですね...^^;...v オンライン整数列大事典 より... A002524Number of permutations of length n within distance 2 of a fixed permutation. (Formerly M1600 N0626)

金光＠岡山　　 10月9日（日） 23:27:13　　 　　38448

uchinyan

#38447，#38448 確かに面倒にはなりますが，漸化式は割と容易に作れますね。 カード 1 〜 n，箱 1 〜 n として，カード i を箱 j に入れるのを i -> j などと書き， n -> n を a(n) 通り，n -> n-1 を b(n) 通り，n -> n-2 を c(n) 通り，全体を s(n) 通り，とすれば， a(n) = (n->n) = s(n-1) b(n) = (n->n-1, n-1->n) + (n->n-1, n-2->n) = s(n-2) + (s(n-2) - c(n-2)) = 2 * s(n-2) - c(n-2) c(n) = (n->n-2, n-1->n, n-2->n-1) + (n->n-2, n-1->n, n-3->n-1) + (n->n-2, n-2->n, n-1->n-1) + (n->n-2, n-2->n, n-3->n-1) = s(n-3) + (s(n-3) - c(n-3)) + s(n-3) + s(n-4) = 3 * s(n-3) + s(n-4) - c(n-3) s(n) = a(n) + b(n) + c(n) ただし， a(1) = 1, b(1) = 0, c(1) = 0, s(1) = 1 a(2) = 1, b(2) = 1, c(2) = 0, s(2) = 2 a(3) = 2, b(3) = 2, c(3) = 2, s(3) = 6 a(4) = 6, b(4) = 4, c(4) = 4, s(4) = 14 です。ここまでは，一部漸化式を使いながらも，結局は，地道に数えます。後は上記の漸化式で， a(5) = 14, b(5) = 10, c(5) = 7, s(5) = 31 a(6) = 31, b(6) = 24, c(6) = 18, s(6) = 73 a(7) = 73, b(7) = 55, c(7) = 44, s(7) = 172 a(8) = 172, b(8) = 128, c(8) = 100, s(8) = 400 a(9) = 400, b(9) = 300, c(9) = 232, s(9) = 932 a(10) = 932, b(10) = 700, c(10) = 545, s(10) = 2177 a(11) = 2177, b(11) = 1632, c(11) = 1272, s(11) = 5081 a(12) = 5081, b(12) = 3809, c(12) = 2964, s(12) = 11854 a(13) = 11854, b(13) = 8890, c(13) = 6918, s(13) = 27662 a(14) = 27662, b(14) = 20744, c(14) = 16148, s(14) = 64554 a(15) = 64554, b(15) = 48406, c(15) = 37679, s(15) = 150639 ．．． なお，差が m の場合も考えたくなりますが，一般にこの方で解くのはかなり難しそうです。

ネコの住む家　　 10月10日（月） 15:25:28　　 　　38449

しょーた

フィボナッチ数列になるんですか！？ 私は地道に樹形図を描いて調べました。 １〜14番のカードがどの番号の箱に入るかを樹形図で表します。 すると１番上の段が１−２−３−４−５−６−７−８−９−１０−１１−１２−１３−１４となり、ここからさかのぼってカードの番号以外の番号の箱に入るパターンを数え上げます。 こちらも興味深い規則性が得られます。

10月12日（水） 21:35:38　　 　　38450