平成１９年２月４日

[流れ星]

　　　　　第1８５回数学的な応募問題解答

　　　　　　＜解答募集期間：１月１４日〜２月４日

［部分集合の個数］

皆さん、ここに１からｎまでの自然数｛１，２，３，・・・，ｎ｝があり、その中から隣り合う数を含まないようにｓ個の数を取り出した部分集合の個数ｆ（ｎ，ｓ）を考えます。

　例えば、ｎ＝５のときを考えます。

ｓ＝１ならば、｛１｝，｛２｝，｛３｝，｛４｝，｛５｝でｆ（５、１）＝５

ｓ＝２ならば、｛１，３｝，｛１，４｝，｛１，５｝，｛２，４｝，｛２，５｝，｛３，５｝

　　　　　　　　で、ｆ（５、２）＝６

ｓ＝３ならば、｛１，３，５｝でｆ（５、３）＝１　となります。

　ここで問題です。

問題１：ｆ（８、ｓ）（１≦ｓ≦４）の値を求めてください。

問題２：ｎが与えられているとき、題意を満たすｓの範囲をｎで表してください。

問題３：ここで、Ｆ（ｎ）＝ｆ（ｎ，０）＋ｆ（ｎ，１）＋ｆ（ｎ，２）＋・・・＋ｆ（ｎ，ｓ）を

　　　　考えます。ただし、便宜的にｓ＝０のときは、｛φ｝を考えてｆ（ｎ，０）＝１とする。

　　　　Ｆ（ｎ）（１≦ｎ≦８）の値を求めよ。

問題４：一般にｆ（ｎ，ｓ）の値をｎ，ｓで表してください。

問題５：Ｆ（ｎ）の漸化式を導いて、Ｆ（ｎ）をｎで表してください。

＜参考文献１：数学セミナー（日本評論社）９９年２月号エレガントな解答を求む＞

＜参考文献２：順列・組合せと確率（岩波書店）「山本幸一著」＞

NO1「uchinyan」01/14 16時10分受信

「uchinyan」01/14 18時17分受信 更新2/4

第１８５回数学的な応募問題
［部分集合の個数］

いつものように，誘導に従って順番にやってみます。

問題１：
・s = 1
{1}, {2}, {3}, {4}, {5}, {6}, {7}, {8} なので
f(8,1) = 8
・s = 2
{1,3}, {1,4}, {1,5}, {1,6}, {1,7}, {1,8},
{2,4}, {2,5}, {2,6}, {2,7}, {2,8},
{3,5}, {3,6}, {3,7}, {3,8},
{4,6}, {4,7}, {4,8},
{5,7}, {5,8},
{6,8}
なので
f(8,2) = 6 + 5 + 4 + 3 + 2 + 1 = 21
・s = 3
{1,3,5}, {1,3,6}, {1,3,7}, {1,3,8},
{1,4,6}, {1,4,7}, {1,4,8},
{1,5,7}, {1,5,8},
{1,6,8},
{2,4,6}, {2,4,7}, {2,4,8},
{2,5,7}, {2,5,8},
{2,6,8},
{3,5,7}, {3,5,8},
{3,6,8},
{4,6,8}
なので
f(8,3) = 10 + 6 + 3 + 1 = 20
・s = 4
{1,3,5,7}, {1,3,5,8},
{1,3,6,8},
{1,4,6,8},
{2,4,6,8}
なので
f(8,4) = 3 + 1 + 1 = 5

問題２：
最大の s は，1 〜 n を可能な限り一つおきに取ってくる場合なので，
n が偶数ならば，{1,3,5,...,n-3,n-1}, {1,3,5,...,n-3,n} などで s の最大は n/2
n が奇数ならば，{1,3,5,...,n-2,n} だけで s の最大は (n+1)/2
つまり，
n が偶数ならば，1 <= s <= n/2
n が奇数ならば，1 <= s <= (n+1)/2
[ ] をガウス記号とすると，まとめて，
1 <= s <= [(n+1)/2]
とも書けます。

問題３：
まず，f(n,s) を 1 <= n <= 8, 0 <= s <= [(n+1)/2] を地道に求めておきます。
f(1,0) = 1, f(1,1) = 1
f(2,0) = 1, f(2,1) = 2
f(3,0) = 1, f(3,1) = 3, f(3,2) = 1
f(4,0) = 1, f(4,1) = 4, f(4,2) = 3
f(5,0) = 1, f(5,1) = 5, f(5,2) = 6, f(5,3) = 1
f(6,0) = 1, f(6,1) = 6, f(6,2) = 10, f(6,3) = 4
f(7,0) = 1, f(7,1) = 7, f(7,2) = 15, f(7,3) = 10, f(7,4) = 1
f(8,0) = 1, f(8,1) = 8, f(8,2) = 21, f(8,3) = 20, f(8,4) = 5
そこで，F(n) = f(n,0) + f(n,1) + f(n,2) + ... + f(n,[(n+1)/2]) より，
F(1) = 2, F(2) = 3, F(3) = 5, F(4) = 8, F(5) = 13, F(6) = 21, F(7) = 34, F(8) = 55

問題４：
問題３：から，かなりのことが見てきているようです。
規則性を使って f(n,s) の漸化式を導くことも可能そうですが，直接的に求めてしまいましょう。

f(n,s) は，
　1 〜 n の自然数からなる集合 {1,2,...,n} から
　隣り合う数を含まないように s 個の数を取り出した部分集合の個数
でした。ここで少し発想を変えて，
「隣り合う数を含まない」という条件を，
「隣り合う数をひとまとめにし，取り出した後に邪魔な数を捨てる」と言い換えます。
ただし，対応が一対一になるようにしないといけないので，より厳密には，1 <= k <= n で，
k を取り出すときには k+1 も一緒に取り出し，取り出した後で k+1 を捨てる，とします。
こうすると，k が n の場合以外は，隣り合う数を含まない s 個の数の部分集合が作れ，
逆もいえます。
ただし，n を取り出すときには n+1 を考えられないのでうまくいきません。
しかしこの場合は，どのみち n+1 を捨てるので，最初に n+1 を追加しておいてそれを後で捨てる，
としても問題ありません。
すると，n+1 個から s 個取り出すと考えて，このときに，k, k+1 を組で取り出し k+1 を捨てる，
とした場合の数を考えればいいことになります。
このとき，「捨てる」操作は場合の数には関係しないので，これは，結局，
s 個取り出すときに k, k+1 を組で取り出すので，n+1-s 個から s 個取り出すのと同じです。
つまり，C を組み合わせの場合の数，二項係数，の記号として，(n+1-s)Cs 通りです。
結局，
f(n,s) = (n+1-s)Cs 通り
となります。

実際，これは，問題３：の値と一致しています。

問題５：
m = [(n+1)/2] として，F(n) の定義式
F(n) = f(n,0) + f(n,1) + f(n,2) + ... + f(n,s) + ... + f(n,m-1) + f(n,m)
に，問題４：の結果を代入します。
F(n) = (n+1)c0 + nC1 + (n-1)C2 + ... + (n+1-s)Cs + ... + (n-m)C(m-1) + (n+1-m)Cm
ここで，二項係数の性質から，
(n+1)C0 = 1 = nC0
(n+1-s)Cs = (n-s)Cs + (n-s)C(s-1)
ただし，m = [(n+1)/2] だったので，(n+1-m)Cm には注意が必要で，
n が偶数のとき：m = n/2 なので，
(n+1-m)Cm = (n-m)Cm + (n-m)C(m-1)
でOKですが，
n が奇数のとき：m = (n+1)/2 なので，
(n+1-m)Cm = (n-m)C(m-1)
です。m-1 = n-m < m なので (n-m)Cm に意味がないわけです。便宜上，(n-m)Cm = 0 と定義します。
以上のことに注意すると，
F(n)
= nC0 + ((n-1)C1 + (n-1)C0) + ((n-2)C2 + (n-2)C1) + ...
+ ((n-s)Cs + (n-s)C(s-1)) + ...
+ ((n-m+1)C(m-1) + (n-m+1)C(m-2)) + ((n-m)Cm + (n-m)C(m-1))
= (nC0 + (n-1)C1 + (n-2)C2 + ... + (n-s)Cs + ... + (n-m+1)C(m-1) + (n-m)Cm)
+ ((n-1)C0 + (n-1-1)C1 + ... + (n-1-(s-1))C(s-1) + ...
　+ (n-1-(m-2))C(m-2) + (n-1-(m-1))C(m-1))
ここで，
n が偶数のとき：
m = n/2
[((n-1)+1)/2] = [n/2] = n/2 = m
[((n-2)+1)/2] = [(n-1)/2] = n/2 - 1 = m-1
n が奇数のとき：
m = (n+1)/2
[((n-1)+1)/2] = [n/2] = (n-1)/2 = m-1
[((n-2)+1)/2] = [(n-1)/2] = (n-1)/2 = m-1
(n-m)Cm = 0
より，
nC0 + (n-1)C1 + (n-2)C2 + ... + (n-s)Cs + ... + (n-m+1)C(m-1) + (n-m)Cm = F(n-1)
(n-1)C0 + (n-1-1)C1 + ... + (n-1-(s-1))C(s-1) + ... + (n-1-(m-2))C(m-2) + (n-1-(m-1))C(m-1) = F(n-2)
となるので，結局，
F(n) = F(n-1) + F(n-2)
ただし，F(1) = 2，F(2) = 3 です。
これは，便宜上，F(-1) = 1，F(0) = 1 とすれば，二つずれたフィボナッチ数列になっています。
一般項は初期条件に注意して漸化式を解けばよく，詳細は省略しますが，
F(n)
= (5 + 3 * sqrt(5))/10 * ((1 + sqrt(5))/2)^n + (5 - 3 * sqrt(5))/10 * ((1 - sqrt(5))/2)^n
になります。

(感想)
面白い問題だと思います。
ただ，面白いと思うのは皆さん同じようで，偶然だと思いますが，
この解答を書いている2007年1月14日現在出題中の「算数にチャレンジ（ http://www.sansu.org/ ）」の「第５３２回問題（1月11日〜1月17日）」
と，実質同じです！
この解答の公開時には，過去問の第５３２回の過去ログから様々な考え方が見られると思います。
また，http://www.hokuriku.ne.jp/fukiyo/math-mok/obenkyou.htm の「パスカルの三角形」にも，
同様の直感的に分かりやすい議論があります。
なお，実はこの問題は，よく知られた，
　階段を一段ずつ又は一段飛ばしで上る場合，一段飛ばしの回数を決めて、上り方の場合の数を求める問題とも同じになります

＜水の流れコメント：別々の所で、同時に起きることをシンクロナイドと言います。このような現象が起きたのですね。＞

NO2「ｽﾓｰｸﾏﾝ」 01/15 19時00分受信 更新2/4

考え方が同じ問題が算数チャレンジにでてたから・・・(^^)

ここに１からｎまでの自然数｛１，２，３，・・・，ｎ｝があり、その中から隣り合
う数を含まないようにｓ個の数を取り出した部分集合の個数ｆ（ｎ，ｓ）を考えます
。
　例えば、ｎ＝５のときを考えます。
ｓ＝１ならば、｛１｝，｛２｝，｛３｝，｛４｝，｛５｝でｆ（５、１）＝５
ｓ＝２ならば、｛１，３｝，｛１，４｝，｛１，５｝，｛２，４｝，｛２，５｝，｛
３，５｝
　　　　　　　　で、ｆ（５、２）＝６
ｓ＝３ならば、｛１，３，５｝でｆ（５、３）＝１　となります。
　ここで問題です。
問題１：ｆ（８、ｓ）（１≦ｓ≦４）の値を求めてください。

0 の場合、2H4=5C1=5
010の場合、3H2=4C2=6
01010の場合、4H0=3C3=1
同様に、
f(8,1)=2H7=8C1=8
f(8,2)=3H5=7C2=21
f(8,3)=4H3=6C3=20
f(8,4)=5H1=5C4=5

問題２：ｎが与えられているとき、題意を満たすｓの範囲をｎで表してください。

明らかに、n が偶数の時、1 <= n <= n/2
　　　　　n が奇数の時、1 <= n <= (n+1)/2

問題３：ここで、Ｆ（ｎ）＝ｆ（ｎ，０）＋ｆ（ｎ，１）＋ｆ（ｎ，２）＋・・・＋
ｆ（ｎ，ｓ）を
　　　　考えます。ただし、便宜的にｓ＝０のときは、｛φ｝を考えてｆ（ｎ，０）
＝１とする。
　　　　Ｆ（ｎ）（１≦ｎ≦８）の値を求めよ。

f(1,0)+f(1,1)=1+2H0=1+1C1=2
f(2,0)+f(2,1)=1+2H1=1+2C1=3
f(3,0)+f(3,1)+f(3,2)=1+2H2+3H0=1+3C1+2C2=1+3+1=5
f(4,0)+f(4,1)+f(4,2)=1+2H3+3H1=1+4C1+3C2=1+4+3=8
f(5,0)+f(5,1)+f(5,2)+f(5,3)=1+2H4+3H2+4H0=1+5C1+4C2+3C3=1+5+6+1=13
f(6,0)+f(6,1)+f(6,2)+f(6,3)=1;2H5+3H3+4H1=1+6C1+5C2+4C3=1+6+10+4=21
f(7,0)+f(7,1)+f(7,2)+f(7,3)+f(7,4)=1+2H6+3H4+4H2+5H0=1+7C1+6C2+5C3+4C4=1+7+15+10+1=34
f(8,0)+f(8,1)+f(8,2)+f(8,3)+f(8,4)=1+2H7+3H5+4H3+5H1=1+8C1+7C2+6C3+5C4=1+8+21+20+5=55

問題４：一般にｆ（ｎ，ｓ）の値をｎ，ｓで表してください。

f(n,s)=(s+1)H(n-s-1)=(n-1)Cs

問題５：Ｆ（ｎ）の漸化式を導いて、Ｆ（ｎ）をｎで表してください。

F(1)=2
F(2)=3
F(3)=5
F(4)=8
F(5)=13
F(6)=21
F(7)=34
F(8)=55
から、F(n)=F(n-1)+F(n-2)
フィボナッチ数列　
これ以上分かりません。。。(^^;

NO3「kashiwagi｣01/16 08時53分受信 更新2/4

185回

　面倒なので大勢を把握するためにもざっと計算してみました。

問1.上表に示します。

問2.これはｓの値に注意すると、奇数と偶数に分ければよいので、

�@ ｓが奇数：0≦ｓ≦（ｎ+1）/2

�A ｓが偶数：0≦ｓ≦ｎ/2

問3. 等の値を代入して地道に計算すると、以下の様になる。

F(1)＝2

F(2)＝3

F(3)＝5

F(4)＝8

F(5)＝13　

F(6)＝21

F(7)＝34

F(8)＝55 要するにフィボナッチ数列になっているのですね（感嘆しました）

問4.上表のｎ＝8に注目すると、ｓの値との関係から、（ｎ+1-ｓCｓ）であることが分かる。

問5.　F（ｎ）＝F（ｎ-1）+F（ｎ-2）の関係から各々の項を代入し、

ｎCｒ　＝ｎ-1Cｒ　+　ｎ-1Cｒ-1などの関係を使用して整理すると、

　　F（ｎ）＝ｎ+1C0　+　ｎC1　+ｎ-1C2　+　ｎ-2C3　+　ｎ-3C4　+　・・・・・　　となることが分かる。

＜コメント：明けましておめでとうございます。本年も宜しくご指導方お願い申し上げます。 正月休みで少々ボケ気味の頭に血流を通わせて下さった今回の問題も非常に 興味深く取り組ませて頂きました。 しかし、この様なところまでフィボナッチ数列が出てくるとは・・・・、感嘆以外の 何ものでもありません。この様な問題を何をヒントに考案なされるの でしょうか・・・・？正にアイデアの宝庫をお持ちなのでしょうね。羨ましいの一語に尽きます。＞　

＜水の流れ：恐縮します。よく数学の本を読んでいます。また、印象に残った問題の解答をよく記憶しようとしています。＞

NO4「Toru」　 01/17 13時32分受信 更新2/4

問題１{1} {2} {3} {4} {5} {6} {7} {8}で　f(8,1)=8

      {1,3}{1,4}{1,5}{1,6}{1,7}{1,8}
      {2,4}{2,5}{2,6}{2,7}{2,8}
      {3,5}{3,6}{3,7}{3,8}
      {4,6}{4,7}{4,8}
      {5,7}{5,8}
      {6,8}    でf(8,2)=21

      {1,3,5}{1,3,6}{1,3,7}{1,3,8}{1,4,6}{1,4,7}{1,4,8}{1,5,7}{1,5,8}{1,6,8}
      {2,4,6}{2,4,7}{2,4,8}{2,5,7}{2,5,8}{2,6,8}
      {3,5,7}{3,5,8}{3,6,8}
      {4,6,8}     でf(8,3)=20

      {1,3,5,7}{1,3,5,8}{13,6,8}{1,4,6,8}
      {2,4,6,8}   でf(8,4)=5

問題２　nが偶数の時　s=1,2,3,----,n/2
        nが奇数の時　s=1,2,3,----,(n+1)/2
　　　　
        あるいは　s≦(n+1)/2 （sは自然数）

問題３　F(1)=f(1,0)+f(1,1)=1+1=2
        F(2)=f(2,0)+f(2,1) =1+2=3
        F(3)=f(3,0)+f(3,1)+f(3,2)=1+3+1=5
        F(4)=f(4,0)+f(4,1)+f(4,2)=1+4+3=8
        F(5)=f(5,0)+f(5,1)+f(5,2)+f(5,3)=1+5+6+1=13
        F(6)=f(6,0)+f(6,1)+f(6,2)+f(6,3)=1+6+10+4=21
        F(7)=f(7,0)+f(7,1)+f(7,2)+f(7,3)+f(7,4)=1+7+15+10+1=34
        F(8)=f(8,0)+f(8,1)+f(8,2)+f(8,3)+f(8,4)=1+8+21+20+5=55

問題４　s≧1の時、s個の黒石と(n-s)個の白石を黒石が隣り合わせにならないように
１列に並べると考える。まず黒石を並べ、黒石の間の(s-1)箇所に白石をおいて、残
りの(n-2s+1)個の白石を黒石の間あるいは両端の(s+1)箇所のどこかに置くと考える
と　n-2s+1≧0よりs≦(n+1)/2で
f(n,s)=(s+1)H(n-2s+1)=(n-s+1)C(n-2s+1)=(n-s+1)Cs　
（これはs=0でも一応ok (n+1)C0=1 ）

　条件に合うように並べた後、右端に白石を１つ追加し、黒石の右隣の白石を全て取
り除いて、n-s+1 個の並び（うち黒がs個）を作ると考えると、これは逆方向も可能
で１：１に対応するため、(n-s+1)Cs通りと考えることもできそうです。

問題5  F(n) を白黒合わせてn個の石を、黒石が隣り合わせにならないように並べる
場合の数と考えると
　n番目が黒の時(n-1)番目は白でF(n-2)　とおり,
  n番目が白の時はF(n-1)とおりだから　F(n)=F(n-1)+F(n-2)　F(1)=2,F(2)=3
これはフィボナッチ数列（の第３項から）で p=(1+√5)/2,q=(1-√5)/2として
F(n)=(p^(n+2)-q^(n+2))/(p-q)