平成１４年４月３０日
[流れ星]
第９６回数学的な応募問題解答
＜解答募集期間：４月１６日〜４月３０日＞
［授業の担当クラス］
太郎さんが勤務している高校のクラス数は、１年生７クラス、２年生８クラス、３年生８クラスあります。各クラスの授業時間割を編成するとき、なるべく隣のクラスを同じ担当者が待たないほうが、経験上少し編成しやすいのです。
例えば、１学年５クラスのときを考えます。
太郎さんが１クラスだけ担当する場合は ｛１｝、｛２｝、｛３｝、｛４｝、｛５｝の５通りあります。
２クラス担当する場合は ｛１，３｝、｛１，４｝、｛１，５｝、｛２，４｝、｛２，５｝、｛３，５｝の６通り。
３クラス担当する場合は ｛１，３、５｝の１通りしかありません。ここで、問題です。
１学年１からｎまでのクラスがあるとして、この学年からｋ個のクラスを選んで授業担当をします。ただし、時間割編成上隣り合わせのクラスは持たないとします。そこで、このような持ち方の方法をＦ（ｎ，ｋ）通りとします。次の設問に答えてください。
問題１：ｎ＝６のとき、Ｆ（６，１）、Ｆ（６，２）、Ｆ（６，３）を求めよ。
問題２：ｎ＝７のとき、Ｆ（７，１）、Ｆ（７，２）、Ｆ（７，３）、Ｆ（７，４）を求めよ。
問題３：Ｆ（ｎ，１）、Ｆ（ｎ，２）をｎで表せ。
問題４：Ｆ（ｎ，ｋ）をｎとｋで表せ。
問題５：何か漸化式みたいものが発見できたら、教えてください。
ＮＯ１＜Ｈ７Ｋ＞さんから１回目4／17 23:04 受信 更新4/30
はじめまして。ペンネームはまだとくに考えていませんが、とりあえずは「H7K」でお願いします。
1.F(6,1)=6
F(6,2)=10 ( {1,3}{1,4}{1,5}{1,6}{2,4}{2,5}{2,6}{3,5}{3,6}{4,6} )
F(6,3)=4 ( {1,3,5}{1,3,6}{1,4,6}{2,4,6}
2.F(7,1)=7 F(7,2)=5+4+3+2+1=15
F(7,3)=10 ( 135,136,137,146,147,157,246,247,257,357 )
F(7,4)=1 ( 1257のみ )
3.F(n,1)=n F(n,2)=(n-2)+(n-3)+...+1=(n-1)(n-2)/2
4.と5.は現在考え中です。 解けたら、また送ります。
ＮＯ２＜Ｈ７Ｋ＞さんから２回目4／18 00:13 受信 更新4/30
4.を解きました。(風呂の中で考えました)
--- ---
F(n,k)は、「1<=a_1,a_k<=n,a_p+1<a_{p+1},a_p\in Nを満たす{a_p}の場合の数」と一致する。(明らか)
よって、「1<=a_1,a_k<=n,a_p+1<a_{p+1},a_p\in Nを満たす{a_p}の場合の数」(以下Pとする)を求めればよい。
B_p=a_p-1としてb_pを決めると、
Pは「0<=b_1,b_k<=n-k,b_p<b_{p+1},b_p\in Nを満たす{b_p}の場合の数」と等しくなるが、
これは0〜n-kまでの数をkこ順序なしで選ぶやり方と一致する。
よって、P={}_{n+1-k}C_k
よって、F(n,k)={}_{n+1-k}C_k
--- ---
いつも数式なんかはTeXで書くので、ここでもそれを使ってしまいました。
5.はまだ考え中です。
(まだこの問題を見てから1hもたってないのですが...) それでは。
ＮＯ３＜Ｈ７Ｋ＞さんから３回目4／18 16:01 受信 更新4/30
いつもとは違うOSから打っているので、題名が違うかもしれません。
typoをしてしまいました^^; b_p=a_p-1とかいう行があるはずですが、 ここはb_p=a_p-pの間違いです。 ああ、恥ずかしい...
＜水の流れ：コメント＞ ４月18日 22時 発信
問１から問４まで正解です。問５の漸化式は思いつくのでは。「授業の担当クラス」の問題は ２つ隣のクラスまでも許さないとしても考えられます。さらに、３つ、４つ・・・ｄクラスまでと拡張できます
ＮＯ４＜Ｉｇａ＞さんから4／18 21:08 受信 更新4/30
お久しぶりです、Igaです。何となくできそうなのでチャレンジしました。
問題１：ｎ＝６のとき、Ｆ（６，１）、Ｆ（６，２）、Ｆ（６，３）を求めよ。
Ｆ（６，１）＝６ 単にクラス数ですね
Ｆ（６，２）＝１０ ＝６Ｃ２−５
６クラスから２クラスを選び出す組み合わせの数から、隣り合うクラスの組み合わせの数をひきました。
Ｆ（６，３）＝４ とりあえず、６クラスから３クラスを選ぶ組み合わせをすべて書き出し、
隣り合うクラスを含む組み合わせを除いて数えました。
問題２：ｎ＝７のとき、Ｆ（７，１）、Ｆ（７，２）、Ｆ（７，３）、Ｆ（７，４）を求めよ。
ｎ＝６のときと同様にして、とりあえず数えました。
Ｆ（７，１）＝７ Ｆ（７，２）＝１５ Ｆ（７，３）＝１０ Ｆ（７，４）＝１
問題３：Ｆ（ｎ，１）、Ｆ（ｎ，２）をｎで表せ。
Ｆ（ｎ，１）＝ｎ 隣り合うクラスを持つ事を考えなくてよいので、クラス数と同じになります。
＝ｎＣ１
Ｆ（ｎ，２）
ｎクラスから２クラス選ぶ組み合わせの数は ｎＣ２ ＝ｎ（ｎ−１）／２
そのうち、隣り合わせのクラスの組み合わせの数は ｎ−１ ＝ｎ−１Ｃ１
よって、Ｆ（ｎ，２）＝ｎＣ２−ｎ−１Ｃ１
＝ｎ（ｎ−１）／２−（ｎ−１）
＝｛ｎ（ｎ−１）−２（ｎ−１）｝／２
＝（ｎ−１）（ｎ−２）／２
＝ｎ−１Ｃ２
問題４：Ｆ（ｎ，ｋ）をｎとｋで表せ。
問題３に続けて、Ｆ（ｎ，３）を考えました。
ｎクラスから３クラス選ぶ組み合わせの数は ｎＣ３＝ｎ（ｎ−１）（ｎ−２）／６
選ぶ３クラスを｛ａ，ｂ，ｃ｝（ａ＜ｂ＜ｃ）とするとき
ａとｂが隣り合わせになる組み合わせの数は ｎ−１Ｃ２＝（ｎ−１）（ｎ−２）／２
ｂとｃが隣り合わせになる組み合わせの数は ｎ−２Ｃ２＝（ｎ−２）（ｎ−３）／２
よって、Ｆ（ｎ，３）＝ｎＣ３−ｎ−１Ｃ２−ｎ−２Ｃ２
＝ｎ（ｎ−１）（ｎ−２）／６−（ｎ−１）（ｎ−２）／２−（ｎ−２）（ｎ−３）／２
＝｛（ｎ−１）（ｎ−２）（ｎ−３）−３（ｎ−２）（ｎ−３）｝／６
＝（ｎ−２）（ｎ−３）（ｎ−４）／６
＝ｎ−２Ｃ３
同様に考えると式の形から、
Ｆ（ｎ，４）＝ｎＣ４−ｎ−１Ｃ３−ｎ−２Ｃ３−ｎ−３Ｃ３
＝ｎ−３Ｃ４
と予想出来る。ｎ＝７のときで確認してみると、
Ｆ（７，４）＝４Ｃ４＝１
となり、問題２の結果と一致した。
以上より、 Ｆ（ｎ，ｋ）＝ｎ−（ｋ−１）Ｃｋ
という式になると思うのですが、確かめてはいません。
とりあえず、今回はここまで出してみました。
またできそうだったらチャレンジします。
＜水の流れ：コメント＞ ４月18日 22時50分 発信
問題１：正解です。
問題２：正解です
問題３：正解です
問題４：Ｆ（ｎ，ｋ）をｎとｋで表せ。
Ｆ（ｎ，ｋ）＝ｎ−（ｋ−１）Ｃｋ 正解です
問５は組み合わせですから 漸化式は・・・
ＮＯ５＜kachiwagi＞さんから4／19 09:02 受信 更新4/30
問１． 題意より、F(6,1)＝６C１＝６
F(6,2)＝６C2−(６−１) ＝15−5＝10
|
１ |
２ |
3 |
4 |
5 |
6 |
|
○ |
○ |
× |
|
|
|
|
× |
○ |
○ |
|
|
|
|
|
|
○ |
○ |
|
|
|
|
|
|
○ |
○ |
|
|
|
|
|
|
○ |
○ |
上表の○の組み合わせは題意に合わないため除外する。この個数は６−１
F(6,3)＝６C3−(5×4−4) ＝20−20＋4＝4
上表で○が連続する組み合わせは５×４だが二つの欄のように×をつけたものは同じ組み合わせであり、ダブって引いている。この様な例が全部で４個あるのでこれは加えねばならない。因って上記の様になる。
問２． 問１と同様の考え方でF(7,1)＝７C１＝７
F(７,2)＝７C2−(７−１) ＝21−6＝15
F(７,3)＝７C3−(6×5−5) ＝35−30＋5＝10
|
１ |
２ |
3 |
4 |
5 |
6 |
７ |
|
○ |
|
○ |
|
○ |
|
× |
|
○ |
|
○ |
|
|
○ |
|
|
○ |
|
○ |
|
× |
|
○ |
|
○ |
|
|
○ |
|
○ |
|
|
○ |
|
|
○ |
|
|
○ |
|
○ |
|
× |
|
○ |
|
○ |
|
|
○ |
|
○ |
|
○ |
|
|
|
○ |
|
○ |
|
|
○ |
|
|
○ |
|
|
○ |
|
○ |
|
× |
|
○ |
|
○ |
|
○ |
上表より４つめの×を置けるのは４種類あるが、全て同じ組み合わせのため
F(７,4)＝1
問３． 問１，２からF(ｎ,１)＝ｎC１＝ｎ
F(ｎ,2)＝ｎC2−(ｎ−１) ＝(ｎ−１) (ｎ−2)／２＝ｎ−１C2
F(ｎ,3)＝ｎC３−〔(ｎ−１) (ｎ−2)
−(ｎ−１)〕
＝(ｎ−2) (ｎ−3)
(ｎ−4)／6＝ｎ−2C３
問４． 問３よりの類推で
F(ｎ,ｋ)＝ｎ−(ｋ−１)Cｋ
問５． 組み合わせの法則よりｎCｋ＝ｎ−１Cｋ＋ｎ−１Cｋ−１である。
これより
ｎ−(ｋ−１)Cｋ＝ｎ−(ｋ−２)Cｋ＋ｎ−(ｋ−2)Cｋ−１となる。これをF関数で表すと、
F(ｎ,ｋ)＝F(ｎ−１,ｋ) ＋F(ｎ−２,ｋ−１)となる。
この漸化式が求めるものである。
＜水の流れ：コメント＞ ４月20日 18時 発信
正解でした。
こちらは、帰納法での証明まで考えていませんでした。考え方から発見できれば良しとね。
もちろん、キチンと証明する必要がありそうですが。
「授業の担当クラス」の問題は 連続するクラスの間を１クラス、２クラス、・・・、ｄクラスまで
許さないとしても考えられます。
ＮＯ６＜Ｈ７Ｋ＞さんから４回目4／19 19:23 受信 更新4/30
>組合わせ記号で書けますから、問5の漸化式は思いつくのでは。
考えてみます。
>「授業の担当クラス」の問題は 2つ隣のクラスまでも許さないとしても考えられま
>す。 さらに、3つ、4つ・・・dクラスまでと拡張できます。
lこ隣のクラスまで許さない場合は、
{}_{n+l(k-1)}C_k通りになるような気がします。
ＮＯ７＜スモークマン＞さんから１回目4／19 22:50 受信 更新4/30
F(n,k)=(n-2k+3)(n-2k+2)/2
になると思います。
＜水の流れ：コメント＞ ４月20日 18時 発信
ペンネームを「スモークマン」さんとして、ネット上で載せさせていただきます。
さて、解答ですが、
問３で、 Ｆ（ｎ，１）＝ｎ 隣り合うクラスを持つ事を考えなくてよいので、クラス数と同じになります。
ＮＯ８＜スモークマン＞さんから２回目4／21 21:59 受信 更新4/30
すいません考え方が違ってました。
ｋ個のものがあって、その両端と、間のｋ+1個から、ｎ-ｋ個取り出す数から、ｋ個から、ｎ-ｋ個取り出す回数と、2個から
ｎ-ｋ個取り出す回数を引くとよさそうに思いますがいかがでしょうか？
＜水の流れ：コメント＞ ４月22日 記入
「スモークマン」さんから問４について、解答をもらいました。太郎さんは、正しいかどうか判断に迷っています。誰かコメントください。よろしくお願いします。
ＮＯ９＜Ｈ７Ｋ＞さんから５回目4／22 22:20 受信 更新4/30
5.を解きました。
---
選んだ中で、一番番号の大きいクラス(aとする)によって場合分けをする。
◎a=nのとき:
1-(n-2)の中から条件に沿って(r-1)クラス選ぶ→F(n-2,r-1)
◎a=n-1のとき
1-(n-3)の中から条件に沿って(r-1)クラス選ぶ→F(n-3,r-1)
....
◎a=2r-1のとき:
1-(2r-2)の中から条件に沿って(r-1)クラス選ぶ→F(2r-2,r-1)
よって、
F(n,r)=\sum_{k=2r-2}^{n-2}F(k,r-1)
---
＜水の流れ：コメント＞ ４月22日 23時 発信
どこから、どこまで合計するかですが、Ｋの一番小さい和ですが、k=2r-3までではな
いかと悩んでいます。
_F(n,r)=sum_{k=2r-3}から{n-2}F(k,r-1)となりませんか。
ＮＯ10＜Ｈ７Ｋ＞さんから６回目4／23 17:48 受信 更新4/30
◎a=2r-1のとき:
1-(2r-2)の中から条件に沿って(r-1)クラス選ぶ→F(2r-2,r-1)
よって、
F(n,r)=\sum_{k=2r-2}^{n-2}F(k,r-1)
どこから、どこまで合計するかですが、Ｋの一番小さい和ですが、k=2r-3までではな
いかと悩んでいます。
> _F(n,r)=sum_{k=2r-3}から{n-2}F(k,r-1)となりませんか。
すみません、その通りです^^;
#考えてみれば、kの最小値が偶数になることはありえませんね^^;
＜水の流れ：コメント＞ ４月23日 22時 発信
こんにちは。お返事ありがとうございます。
F(n,r)の値はパスカルの三角形の中にありますから、
F(n,r)=sum_{k=2r-3}から{n-2}F(k,r-1)となりませんか。
上のような漸化式が出てきます。 これを発見してもらいたかったことです。感謝しています。
ＮＯ11＜Ｈ７Ｋ＞さんから７回目4／23 22:49 受信 更新4/30
> F(n,r)の値はパスカルの三角形の中にありますから、
確かに考えれば、そうなりますね。
それにしても、パスカルとは...思いつきませんでした。
拡張させたとき(kこ隣まで許さない場合)では、
G(n,r,k)=Σ{i=(k+1)(r-1)-1 to n-(k+1)}G(i,r-1,k)
となると思います。
また機会が有れば、投稿すると思います。これからも、よろしくお願いします。
＜水の流れ：コメント＞ ４月30日 記入
今回 初めて方からの応募があり、本当に感謝しています。応募ありがとうございます。
この問題の一般化は、隣り合う数だけでなく、その１個となり、２個隣の数と、一般にｄ個の隣クラスまで含めないとすることも考えられます。このときの解答は F(ｎ,ｋ)＝ｎ−(ｋ−１)Cｋ と同じ方法で F(ｎ,ｋ)＝ｎ−ｄ(ｋ−１)Cｋ となります。
また、１組のクラスからｎ組までの数を巡回させると、１もｎも隣り合うことになり、これも同時に含めないことになります。
このときの解答は F(ｎ,ｋ)＝｛ｎ−ｋ＋１Cｋ｝―｛ｎ−ｋ―１)Cｋ―２｝ 通りとなります。
