Colloquium

NO.218
Weekend Mathematicsコロキウム室/NO.218

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

第190回数学的な応募問題

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

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

設問1:a ,a ,a ,a を求めてください。

設問2:a15 を求めてください。

設問3:漸化式を発見してください。

設問4:漸化式を利用して、a15 を求めてください。

設問5:a はnで簡単には表せませんが、考察をしてみてください。

注:この記事に関する投稿の掲載は、2007年5月21日以降とします。

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

問1
1から10までの数の中から異なる3つの数を組合わせればよいので
   103=120通り
問2
1から10までの数の中から重複を許して3つの数を組合わせればよいので
   103=220通り
問3
x1、x2、x3は最低でも1なので、残り7の割り振りを考えて
   37=36通り
問4
各変数は0でもよいので
   310=66通り
問5
答は、132通りです。 とても難しいので具体的に書き出していきます。 6桁の数とみなして小さい順に書き出します。 xk には k 以上の数が入りかつ k は x(k-1) に入った数以上でなければなりません。

●まず、x1=1、x2=2、x3=3 の場合です。
x1x2x3x4x5x6
123456
123466
123556
123566
123666

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

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

次は、x3=5 です。
x1x2x3x4x5x6
125556
125566
125666

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

次は、x3=6 です。
x1x2x3x4x5x6
126666

これを、(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)

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

次に、x2=4 の場合ですが、これは(14[4***])です。
x1x2x3x4x5x6
144456
144466
144556
144566
144666
145556
145566
145666
146666

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

次に、x2=5 の場合ですが、これは(15[5***])です。
x1x2x3x4x5x6
155556
155566
155666
156666

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

次に、x2=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)

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

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

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

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

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

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

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

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

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

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

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

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

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

●次に、x1=6 の場合です。
 x2=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  水の流れ

第189回数学的な応募問題

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

問題1:1≦x<x<x≦10を満たす整数解の組は何組か。

問題2:1≦x≦x≦x≦10を満たす整数解の組は何組か。

問題3:x+x+x=10を満たす自然数解の組は何組か。

問題4:x+x+x=10を満たす負でない整数解の組は何組か。

問題5:1≦x≦x≦x≦x≦x≦x≦6
かつ 1≦x,2≦x,3≦x,4≦x,5≦x,6≦x  を満たす整数解の組は何組か。

注:この記事に関する投稿の掲載は、2007年4月30日以降とします。

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

問1
線分を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(22)=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(23)=7-{f(2)+f(22)}=7-(1+2)=4
pを素数,mを自然数とすると、

   f(pm)=(pm-1)-{f(p)+f(p2)+f(p3)+・・・+f(pm-1)} ・・・ (う)

(い),(う)の結果をよく考えると、 f(k)は、(k-1)からkの約数(1とk以外)の関数fの値を引くと求まります。
例えば、f(72)は、72=23×32なので
(1+2+22+23)×(1+3+32)=(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)}

問2
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

問3
問1でf(8)までは求めています。
f(9)は問2よりf(9)=6
f(10)=f(2×5)=9-{f(2)+f(5)}=9-(1+4)=4
f(11)=10
f(12)=f(22×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(24)=15-{f(2)+f(22)+f(23)}=15-(1+2+4)=8
f(17)=16
f(18)=f(2×32)=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

問4
ファレイ数列(だそうです)

問5
(1)数列{Fn}の項の分母の最大はnです。
Fnの任意の隣り合う2項b/a,d/cを選ぶと、b/a<(b+d)/(a+c)<d/cです。
ここで(b+d)/(a+c)が約分されて(あるいは約分されずに)分母のa+cがn+1より小さくなると、 Fnに含まれなければならなくなります。
すると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)個の{Fn}の項があることを示しています。
b/aとd/cとが隣り合うためには、m=1です。

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


戻る