アットランダム≒ブリコラージュ

14805：15段の階段を1,2段ずつ上る...ただし、2段連続はしないときの上り方は？

問題14805・・・http://www.sansuu.net/daigaku/daigakuq/daigaku009q.htm より 引用 Orz〜

１歩で１段または２段のいずれかで階段を昇るとき、１歩で２段昇ることは連続しないものとする。１５段の階段を昇る昇り方は何通りあるか。 

(京都大学２００７年理系乙)

解答

・わたしの...

2段:o, 1段:x

oxoxoxoxo...6H1=6C1=6

oxoxoxo...5H4=8C4=70

oxoxo...4H7=10C3=120

oxo...3H10=12C2=66

o...2H13=14C1=14

xxxxxxxxxxxxxxx...1

so...

6+70+120+66+14+1=277

たぶん...漸化式で考えるんだろうけど...よく分からず...^^;

・鍵コメT様からのもの Orz〜

漸化式なら，次のようになります．

n段の昇り方をf(n)通りとする．
n+3段は，
・はじめに1段昇るf(n+2)通り，
・はじめに2段昇り次に1段昇るf(n)通り
が可能．
よって，f(n+3)=f(n+2)+f(n).
f(1)=1,f(2)=2,f(3)=3を元に，
f(4)=4,f(5)=6,f(6)=9,f(7)=13,f(8)=19,f(9)=28,f(10)=41,
f(11)=60,f(12)=88,f(13)=129,f(14)=189,f(15)=277. 

*巧い発想ねぇ♪

14804：pは素数, (p^n)! はpで何回割れる？...パズル ^^

問題14804・・・http://www.sansuu.net/daigaku/daigakuq/daigaku007q.htm より 引用 Orz〜

ｐを素数、ｎを正の整数とするとき、（ｐⁿ）！はｐで何回割り切れるか。

(京都大学０９年理系甲第５問・文系第５問)

解答

・わたしの...

p^n=p^(n-1)*p

so...

p^(n-1)個のpの倍数があり...pでp^(n-1)回割れる...

p^n...1+2+...+n回割れるが、上で1回カウントされているので...

けっきょく...

n(n+1)/2-n=n(n-1)/2

so...

n(n-1)/2+p^(n-1) 回

になるはずね ^^

↑

嘘でしたわ...^^; Orz...

↓

・鍵コメT様からのもの Orz〜

「1+2+…+n回」というのが変です．

1〜p^nのうちにはpの倍数はp^(n-1)個あり，
それ以外のものは掛けても掛けなくてもpで割り切れる回数には影響なし．
つまり，
(p^n)!=p*2p*3p*…*(p^n)*(pで割り切れない整数)
=p*2p*3p*…*(p^(n-1))p*(pで割り切れない整数)
=(p^(p^(n-1)))*(p^(n-1))!*(pで割り切れない整数).…[*]

(p^n)!がpで割り切れる回数をa[n]とすると，[*]より，
a[n]=p^(n-1)+a[n-1]が成り立ち，
a[n]=p^(n-1)+p^(n-2)+p^(n-3)+…+p+1=(p^n-1)/(p-1). 

*なるほどでっす♪

14803：1000〜9999までの2種類の数字で表される数の個数...

問題14803・・・http://www.sansuu.net/daigaku/daigakuq/daigaku006q.htm より 引用 Orz〜

（１）1000 から9999 までの４桁の自然数のうち、1000 や 1212 のようにちょうど２種類の数字から成り立っているものの個数を求めよ。

（２）ｎ桁の自然数のうち、ちょうど２種類の数字から成り立っているものの個数を求めよ。

(北海道大学０２年前期理系・文系)

解答

・わたしの...

(1)

9C2*(2^4-2)+9*(2^3-1)

=36*(2^4-2)+9*(2^3-1)

=(72+9)*(2^3-1)

=81*7

=567

or

10C2*(2^4-2)-9*(2^3-1)

=45*(2^4-2)-9*(2^3-1)

=(90-9)*(2^3-1)

=81*7

=567

(2)

9C2*(2^n-2)+9*(2^(n-1)-1)

=36*(2^n-2)+9*(2^(n-1)-1)

=72*(2^(n-1)-1)+9*(2^(n-1)-1)

=81*(2^(n-1)-1) 

ね ^^

14802：場合の数...2n枚の白いカードと2枚の黒いカードを1列に並べるとき、白いカードが偶数枚ずつ連続するような並び方...

問題14802・・・http://www.sansuu.net/daigaku/daigakuq/daigaku004q.htm より 引用 Orz〜

ｎは自然数とする。２ｎ枚の白いカードと２枚の黒いカードを横１列に並べる。白いカードが偶数枚ずつ連続するような並べ方は何通りあるか。ただし、同じ色のカードは互いに区別しないものとする。

(神戸大学９９年後期文系)

解答

・わたしの...

2の塊がn個...

その間のn-1箇所と両端のn+1

から重複許して2箇所選ぶ...

(n-1)H2=nC2=n(n-1)/2 通り　ね ^^

↑

間違ってました...^^; Orz...

↓

・鍵コメT様からのもの Orz〜

(n+1)H2=(n+2)C2=(n+2)(n+1)/2(通り)です．

*でしたわ...散漫荼羅になってる...^^;;

14801：証明...どの３点も同一直線上にない赤と青との点がそれぞれn点ずつある。異なる色の2点を結ぶn本の線分が交わらないに出来る...

問題14801(友人問)

平面上に赤い点と青い点がn点ずつある。どの3点をとっても、同一直線上には並んでない。赤い点と青い点それぞれ1点ずつ組にして、n組を作り、組の赤い点と青い点をそれぞれ結んだn本の線分がどれも交差しないように出来ることを示せ。

解答

・わたしの...

お互いの距離は等しいか異なる...

互いに一番近い相手と結べば交わらない...

ですよね ^^

・鍵コメT様からのご指摘ぃ〜Orz〜

例えば「赤(0,0),(5,-4)，青(1,1),(-4,5)」として，
(0,0)を最も近い(1,1)と結ぶと，2本の線分は交差してしまいます．

*うむむむ...^^;

再考...ばい!!

・再考...

とりあえず、ある点から、違う色の点を交互に結んで行き、最初の点に戻るルートを作る...線分は2n本...

交差してたら、その線を消す...

消しても、どちらの点ももう１本は違う色の点と結ばれている...

交差してる点を全て消せば...残ってる線分は...違う色の点で結ばれている...回路になってるとすれば、1個飛ばしに線分を消す...

奇数個残らないことが言えればこれで言えてるはず...?

いまいちだなぁ...^^;

・鍵コメT様からのもの Orz〜

次のようにできそうです．

赤い点をR1,R2,…,Rnとし，青い点をB1,B2,…,Bnとする．
R1と結ぶ点はn通り，その後R2と結ぶ点はn-1通り，…となり，
n組の作り方はn!通り．特に，これが有限通りであることに注意する．
すると，n本の線分長の和が最小になる組の作り方が存在する．
この作り方(1通りに定まるとは限らない．最小となる作り方の1つに着目)
で，2線分Ra-BbとRc-Bdが点Pで交わっていると仮定する．
三角形RaBdPにおいてRaBd<RaP+BdP，三角形RcBbPにおいてRcBb<RcP+BbPより，
RaBd+RcBb<RaP+BdP+RcP+BbP=RaBb+RcBdとなる．
これは，Ra-BbとRc-Bdに変えてRa-BdとRc-Bcを組にすることで線分長の和が
小さくなることを意味し，和が最小となる組を作ったことに矛盾．
よって，仮定は誤りであり，
線分長の和が最小になる組では線分は交わらない．

*これも一種の鳩の巣原理ですかね ^^♪