Colloquium

NO.1672　　階段の昇り方　　2007.4.30　　水の流れ

第１９０回数学的な応募問題

皆さん、今年の京都大学の入試問題で、興味深い問題を見つけました。一部改題して紹介します。

1歩で1段または２段のいずれかで階段を昇るとき、1歩で２段昇ることは疲れるから連続して昇らないものとする。 ｎ段の階段を昇る昇り方の総数をａ_ｎ通りとする。ここから設問します。

設問１：ａ_１　，ａ_２　，ａ_３　，ａ_４　を求めてください。

設問２：ａ_１５　を求めてください。

設問３：漸化式を発見してください。

設問４：漸化式を利用して、ａ_１５　を求めてください。

設問５：ａ_ｎ　はｎで簡単には表せませんが、考察をしてみてください。

注：この記事に関する投稿の掲載は、２００７年５月２１日以降とします。

NO.1671　　整数解の個数(2)　　2007.4.30　　夜ふかしのつらいおじさん

問１
１から１０までの数の中から異なる３つの数を組合わせればよいので
　　　₁₀Ｃ₃＝１２０通り
問２
１から１０までの数の中から重複を許して３つの数を組合わせればよいので
　　　₁₀Ｈ₃＝２２０通り
問３
x₁、x₂、x₃は最低でも１なので、残り７の割り振りを考えて
　　　₃Ｈ₇＝３６通り
問４
各変数は０でもよいので
　　　₃Ｈ₁₀＝６６通り
問５
答は、132通りです。 とても難しいので具体的に書き出していきます。 ６桁の数とみなして小さい順に書き出します。 x_k には k 以上の数が入りかつ k は x(k-1) に入った数以上でなければなりません。

●まず、x₁=1、x₂=2、x₃=3 の場合です。

x1	x2	x3	x4	x5	x6
1	2	3	4	5	6
1	2	3	4	6	6
1	2	3	5	5	6
1	2	3	5	6	6
1	2	3	6	6	6

この5つを、(123[4**])と表します。
左の「123」は共通、右の「4**」は残り3桁を4以上の数で埋めるという感じです。
場合の数を、次のように表すことにします。
　　　N(123[4**])=5　･･･　(1)

次は、x₃=4 ですが、まとめて、(124[4**]) と表せます。
　　　N(124[4**])=5　･･･　(2)

次は、x₃=5 です。

x1	x2	x3	x4	x5	x6
1	2	5	5	5	6
1	2	5	5	6	6
1	2	5	6	6	6

この3つを、(125[5**])と表します。
　　　N(125[5**])=3　･･･　(3)

次は、x₃=6 です。

x1	x2	x3	x4	x5	x6
1	2	6	6	6	6

これを、（126[6--])と表します。
　　　N(126[6--])=1　･･･　(4)

以上をまとめて、(12[3***]) となりますが、(1)から(4)より
　　　N（12[3***]）=N(123[4**])+N(124[4**])+N(125[5**])+N(126[6--]) =5+5+3+1=14　・・・　(5)

次に、x₂=3 の場合ですが、これは(13[3***])とまとめられ(5)より
　　　N（13[3***]）=14　･･･　(6)

次に、x₂=4 の場合ですが、これは(14[4***])です。

x1	x2	x3	x4	x5	x6
1	4	4	4	5	6
1	4	4	4	6	6
1	4	4	5	5	6
1	4	4	5	6	6
1	4	4	6	6	6
1	4	5	5	5	6
1	4	5	5	6	6
1	4	5	6	6	6
1	4	6	6	6	6

　　　N(14[4***])=9　･･･　(7)

次に、x₂=5 の場合ですが、これは(15[5***])です。

x1	x2	x3	x4	x5	x6
1	5	5	5	5	6
1	5	5	5	6	6
1	5	5	6	6	6
1	5	6	6	6	6

　　　N(15[5***])=4　･･･　(8)

次に、x₂=6 の場合ですが、これは(16[6---])です。
　　　N(16[6---])=1　･･･　(9)

以上(5)から(9)より、
　　　N(1[2****])=N(12[3***])+N(13[3***])+N(14[4***])+N(15[5***])+N(16[6---]) 　=14+14+9+5+1=42　･･･　(10)

●次に、x₁=2 の場合です。
これは、(2[2****]) なので、(10)より
　　　N(2[2****])=42　･･･　(11)

●次に、x₁=3 の場合です。
　x₂=3 のときは、(33[3***]) なので、(6)より
　　　N(33[3***])=14　･･･　(12)

　x₂=4 のときは、(34[4***])なので、(7)より
　　　N(34[4***])=9　･･･　(13)

　x₂=5 のときは、(35[5***])なので、(8)より
　　　N(35[5***])=4　･･･　(14)

　x₂=6 のときは、(36[6---])なので、(9)より
　　　N(36[6---])=1　･･･　(15)

以上(12)から(15)より、
　　　N(3[3****])=14+9+4+1=28　･･･　(16)

●次に、x₁=4 の場合です。
　x₂=4 のときは、(44[4***])なので、(7)より
　　　N(44[4***])=9　･･･　(17)

　x₂=5 のときは、(45[5***])なので、(8)より
　　　N(45[5***])=4　･･･　(18)

　x₂=6 のときは、(46[6---])なので、(9)より
　　　N(46[6---])=1　･･･　(19)

以上(17)から(19)より、
　　　N(4[4****])=9+4+1=14　･･･　(20)

●次に、x₁=5 の場合です。
　x₂=5 のときは、(55[5***])なので、(8)より
　　　N(55[5***])=4　･･･　(21)

　x₂=6 のときは、(56[6---])なので、(9)より
　　　N(56[6---])=1　･･･　(22)

以上(21)から(22)より、
　　　N(5[5****])=4+1=5　･･･　(23)

●次に、x₁=6 の場合です。
　x₂=6 のときは、(6[6----])なので、明らかに
　　　N(6[6----])=1　･･･　(24)

◎以上(10)、(11)、(16)、(20)、(23)、(24)より、
　　　N([1*****])=42+42+28+14+5+1=132

NO.1670　　整数解の個数　　2007.4.9　　水の流れ

第１８９回数学的な応募問題

皆さん、大学入試問題の中で、整数解の個数を数える問題があります。

問題１：１≦ｘ_１＜ｘ_２＜ｘ_３≦１０を満たす整数解の組は何組か。

問題２：１≦ｘ_１≦ｘ_２≦ｘ_３≦１０を満たす整数解の組は何組か。

問題３：ｘ_１＋ｘ_２＋ｘ_３＝１０を満たす自然数解の組は何組か。

問題４：ｘ_１＋ｘ_２＋ｘ_３＝１０を満たす負でない整数解の組は何組か。

問題５：１≦ｘ_１≦ｘ_２≦ｘ_３≦ｘ_４≦ｘ_５≦ｘ_６≦６
かつ　１≦ｘ_１，２≦ｘ_２，３≦ｘ_３，４≦ｘ_４，５≦ｘ_５，６≦ｘ_６　 を満たす整数解の組は何組か。

注：この記事に関する投稿の掲載は、２００７年４月３０日以降とします。

NO.1669　　線分のｎ等分点(2)　　2007.4.9　　夜ふかしのつらいおじさん

問１
線分をk等分するためには線分上に(k-1)個の点をとる必要があります。
関数f(k)をk等分点にマークしたときに新しく増える分点の個数とします。
f(2)=1，F(3)=2は明らかです。

　　　pを素数とすると、f(p)=p-1　・・・　（あ）

f(4)は、{1/4，2/4，3/4}の点をマークしていくわけですが、
2/4=1/2は既にマークされています。
f(4)=f(2²)=3-f(2)=3-1=2です。
f(5)=4も明らかです。
f(6)は、{1/6，2/6，3/6，4/6，5/6}の点をマークしていくわけですが、
2/6=1/3，3/6=1/2，4/6=2/3は既にマークされています。
f(6)=f(2×3)=5-f(2)-f(3)=5-1-2=2

　　　p，qを素数とすると、f(pq)=(pq-1)-{f(p)+f(q)}　・・・　（い）

f(7)=6も明らかです。
f(8)は、{1/8，2/8，3/8，4/8，5/8，6/8，7/8}の点をマークしていくわけですが、
2/8=1/4，4/8=1/2，6/8=3/4は既にマークされています。
f(8)=f(2³)=7-{f(2)+f(2²)}=7-(1+2)=4
pを素数，mを自然数とすると、

　　　f(p^m)=(p^m-1)-{f(p)+f(p²)+f(p³)+・・・+f(p^m-1)}　・・・　（う）

（い）,（う）の結果をよく考えると、 f(k)は、(k-1)からkの約数（1とk以外）の関数fの値を引くと求まります。
例えば、f(72)は、72=2³×3²なので
(1+2+2²+2³)×(1+3+3²)=(1+2+4+8)+(3+6+12+24)+(9+18+36+72)より

　　　f(72)=71-{f(2)+f(4)+f(8)+・・・+f(18)+f(36)}

問２

f(2007)	=f(32×223)
	=2006-{f(3)+f(32)+f(223)+f(3×223)}
	=2006-{2+8-f(3)+222+668-f(3)-f(223)}
	=2006-(2+8-2+222+668-2-222)
	=2006-674
	=1332

問３
問１でf(8)までは求めています。
f(9)は問２よりf(9)=6
f(10)=f(2×5)=9-{f(2)+f(5)}=9-(1+4)=4
f(11)=10
f(12)=f(2²×3)=11-{f(2)+f(4)+f(3)+f(6)}=11-(1+2+2+2)=11-7=4
f(13)=12
f(14)=f(2×7)=13-{f(2)+f(7)}=13-(1+6)=6
f(15)=f(3×5)=14-{f(3)+f(5)}=14-(2+4)=8
f(16)=f(2⁴)=15-{f(2)+f(2²)+f(2³)}=15-(1+2+4)=8
f(17)=16
f(18)=f(2×3²)=17-{f(3)+f(9)+f(2)+f(6)}=17-(2+6+1+2)=17-11=6

f(19)=18
よって

	f(2)+f(3)+f(4)+f(5)+f(6)+f(7)+f(8)+f(9)+f(10)+f(11)+f(12)+f(13)+f(14)+f(15)+f(16)+f(17)+f(18)+f(19)
=	1+2+2+4+2+6+4+6+4+10+4+12+6+8+8+16+6+18
=	119

問４
ファレイ数列（だそうです）

問５
(1)数列{F_n}の項の分母の最大はnです。
F_nの任意の隣り合う2項b/a，d/cを選ぶと、b/a＜(b+d)/(a+c)＜d/cです。
ここで(b+d)/(a+c)が約分されて（あるいは約分されずに）分母のa+cがn+1より小さくなると、 Ｆ_nに含まれなければならなくなります。
するとb/aとd/cとが隣り合うことに反します。
だからa+c≧n+1になります。

(2)ad-bc=mとおいてみます。
両辺をacで割り整理すると、
　　　d/c=b/a+m/ac
これは、b/aとd/cの間に(m-1)個の{Ｆ_n}の項があることを示しています。
b/aとd/cとが隣り合うためには、m=1です。

(3){Ｆ_n+1}の項の分母の最大は、n+1です。
また(1)よりa+c≧n+1です。
b/a＜q/p＜d/cを満たすF_n+1の項q/p=(b+d)/(a+c)が存在するためにはp=a+c=n+1しかありえません。