マスターオブ整数
■ このスレッドは過去ログ倉庫に格納されています
10
ペル方程式
(x n, yn)は全てペル方程式の解となる。
逆にペル方程式の自然数解は(x n,yn)が全てである。
xを消去→不等式評価。
無限降下法。yは負になることはない。従っていつかはy=0になる。この時x= 1。
x1>0を示しておくことが必要。
※全て(1,0)に帰着する。
10・ 1
(1)実際に計算する。
(2)絶対値が増加することを示す。
10・ 2
(1)積に分解する。場合分け。
(2)帰納法。
− 1にすると nが奇数の場合のみ満たす。
10・3
(1)ブラーマグプタの恒等式。
(2)a= 2として漸化式を作る。うまい値を代入する必要があるトリッキーな問題。 2箇所のうち1箇所だけ文字を消去する。
恒等式の利用。自然数の増加列であるから全て異なる。
nに 1から代入していくと n= 4が当てはまる。 第3部
1 1
1と同じテーマ。
互いに素。格子点。端点。
面積の最小値。
1 1・ 1
(1)背理法でもできる。
(2)平行四辺形の面積二等分。
1 1・2
ピックの定理。面積=内部 +周/ 2 − 1
1 1・3
格子点を結ぶ三角形の面積は有理数、
正三角形の面積は無理数になる。
1 1・ 4
正多角形の1つの内角をθとすると
sinθが無理数の時、存在しない。
五角形全体を考える必要が無く、三角形について考えるだけで良い。
別解。正五角形の中に平行四辺形ができるので格子点を内部に含むことになる。これが無限に続くので矛盾。 第3部
1 2
書きづらいが実際に図を書く。
反射は折り返して直進させる。
繰り返しの構造。
交点を間違えないように数える。
1 2・ 1
(1) iを i + 1に変えても変わらない不変量である。
(2) (1)が利用できる。オイラー関数、互いに素。
1 2・ 2
dが0かどうかで場合分け。回転角をθとしてパラメーターにする。内角を設定する。
問題を見れば自然に分かる。 第3部
1 3
前問と似ている。
互いに素。偶数と奇数。
MOD mで余りが全て異なる。奇数と偶数で場合分け。
証明すべきことを定式化できるかどうかが鍵。
1 3・ 1
折り返しの連続。
有理数と無理数。
1 3・ 2
減少数列ではないが二項ずつ取ると減少している。
実験が大事。無限降下法。背理法。
有理数の話を整数の話にする。分母を払う。繰り返しの構造。いつかは0になる。 第3部
1 4
背理法。
かなり特殊。行列式。
1 4・ 1
ユークリッドの互除法。
例題と同じ解法でも解ける。
オイラー関数。中央項。奇数。 第3部
1 5
MOD 3。
分母を払って矛盾を導く。
分母が揃うしかないことに注意する。
1 5・ 1
幾何学的な意味。xが有理数でyも有理数になる。
これが重要。
無限個存在する。 第3部
16
重要問題。桁の移動。漸化式。実験。
16・ 1
帰納法。最小のものは二進数。
16・ 2
二進数で鮮やかに解ける。振動する。 第3部
17
ガウス記号。
bを自分で用意するところがポイント。
レイリーの定理。
17・ 1
的確に設定する。数え間違いをしない。
17・ 2
的確に設定する。互いに素。[1/α]は整数、がポイント。
絞れるので虱潰し。 第3部
18
(1)偶奇で 4通りなので部屋割り論法・鳩の巣原理により成り立つ。
(2)偶奇で8通りなので最低9個でダブる。
18・ 1
S 0とS kを設定する。
S 0からS nまで n + 1個あるのでそれらのどれか2つは必ずMOD nで一致する。
18・ 2
(1)差を因数分解するとどちらもp未満になるのでpで割り切れない。
(2)余りの中に kがあるかないかで場合分けをする。
ある場合はうまい値を代入することで解決する。
ない場合。あまりは k + 1個で 0〜p− 1= 2 kの中にある。
k室用意して 0〜 2 kまで2人ずつ入れると、k + 1個のあまりは全てが一人で入ることはできない。
部屋割り論法・鳩の巣原理。
2 k + 1=pでOK。
終わり。 好意的なレスありがとうございます。
もう誰も見ていないと思うので勝手に続けます。
マスターオブ整数・第2部を読む。
基本事項のまとめではなくて発展事項の解説なので初めは読むのがつらいと思う。必ずしも読む必要はない。
一回で見開き2ページくらいずつ読むと案外読み終わるかも知れない。あと作業を実際やりながら読むのは極めて重要。整数問題は実験→規則性が大事。
素因数分解は整数で最も重要な論点。エラトステネスの篩。素因数分解の一意性。√ nまで調べれば十分。
素数には最大値はない+素数は無限個あることの証明が書いてある。
約数の個数の公式。約数の総和の公式。 マスターオブ整数・第2部を読む。p 57
n!に含まれる素因数の個数の公式(中学入試)
図にすると、縦に数えるか横に数えるか問題。
素因数分解してある数の最大公約数と最小公倍数の拾い出し方。小さい指数を拾っていけば最大公約数、大きい方を拾っていけば最小公倍数になる。
公式 A B=G L、L=G a b。
平方数の約数の個数は奇数個。重要。
非平方数の約数の個数は偶数個。
どちらも約数の総積(総乗)の公式は同じ。 マスターオブ整数・第2部を読む。p 58
素因数分解が終わって次のテーマに移る。
倍数の周期性。最小公倍数ごとに繰り返す。重要。
倍数の対称性。一列に並べると左右対称になる。重要。
※倍数というより、公差の異なる複数の等差数列と言った方がいい。 マスターオブ整数・第2部を読む。p 59
オイラー関数。 n以下の自然数でnと互いに素な数の個数。これは便利。
感覚的な理解。イメージ。
2で割り切らない中の、3で割り切れない中の、とやっていく。
中国剰余定理。
どの2つも互いに素という仮定。一周期の中にただ一つ存在する。
百五減算は覚えやすいし便利。 マスターオブ整数・第2部を読む。p 6 0、 6 1
合同式に入る。余りの計算は余りだけでやって良いということ。
※ここで言う計算とは足し算・引き算・掛け算のことで割り算は含まれない。
無限個ある整数を有限個に類別する。
円環的イメージ。
類。代表値。剰余類の法。
負の剰余も考えると便利。計算上、別に矛盾しない。
答えの時は普通の余りで答える。
合同式を使った計算の意味。別に合同式を使わなくても内容は同じ。
しかし簡潔に表現できるので楽だから使う。
便利だが間違って使わないように注意する。
自信がなかったら使わないで普通にやる方がいい。
しかし推論に役立つので食わず嫌いは勿体ない。 マスターオブ整数・第2部を読む。p 6 2
よく入試の元ネタになっている重要な性質。
互いに素。両方ともが素数である必要はない。
証明 1は普通。証明2は難しい。 マスターオブ整数・第2部を読む。p 6 3
pを素数、k<pとすると逆元が必ず存在する。
互いに素。
これが合同式における割り算に相当する。
1とp− 1は自分だけで、他はペアでを組む。
ウィルソンの定理・・・p− 1以外はペアを組むので積が1になる。逆元がポイント。
フェルマーの小定理・・・pと互いに素であるa、すなわちpの倍数以外のaについて成り立つ。
k^ iがMOD pで全て異なり、 0以外を覆う時、kをMOD pにおける原始根という。MOD 7で3は原始根である。
具体例があるので分かりやすい。 マスターオブ整数・第2部を読む。p 64
ユークリッドの互除法の解説。原理。
大きい長方形から小さい正方形を取れるだけ取り除いていくと最後に最大公約数の正方形が分かる。 マスターオブ整数・第2部を読む。p 65
このページは今までのまとめになっている。
非常に面白い。
a x + b y= 1 (aとbは互いに素) の図形的意味。
不定方程式と合同式とユークリッドの互除法と逆元とフェルマーの小定理が全て結びつく。最高。 マスターオブ整数・第2部を読む。p 6 6
格子点。ここでもax+b y= 1が活躍する。
基本定理を明確にしておく(2つある)。
内部に格子点がある場合は4個に分割される。
辺上に格子点がある場合は3個に分割される。
面積が2以上だと平行線で面積1にできる。
その時格子点は辺上に2個または内部に 1個。
最小平行四辺形の面積は 1、最小三角形の面積は 1/2。 マスターオブ整数・第2部を読む。p 6 7
ピックの定理。
面積=(周上の格子点/2) + (内部の格子点)−1。
証明。
面積 n /2の多角形についてnに関する帰納法で証明する。
i≦kなる全てのiについて成り立つと仮定する。
適当な折れ線で2つに分ける。
折れ線の両端を除いた格子点の数がポイント。
※辺同士の交差があるとピックの定理は使えない事に注意。 >>43
スクリーンショットで一応保存しておいてるで! マスターオブ整数・第2部を読む。p 68
ファレー数列。
(1,0)と(1,1)から始めて、隣り合うベクトルを足して
x成分が n以下のもののみ残す。
すると出来上がるものは全て既約分数であり、
全ての (任意の)既約分数を生成できる。
性質 2をまず示す。次に性質 1を示す。後半の証明がポイント。性質 3は格子点の整数論の基本定理を利用する。
第2部終わり。 今日も失礼します。
第4部は第 3部よりも難しいけど別に続きって訳でもない。
1部と2部はリンクしているが、1部と3部の関係は不明。決して1部が基礎問題、3部が入試対策、4部がそれより上って訳でもないと思う。
1
次数下げ。部分分数分解がポイント。
互いに素な分母を持つ分数同士の和は整数にならない。
それぞれが整数になる条件を求める。
分子 0の場合は無条件でOK。
2
f (i)=2i− 1 MOD 5 1
f^ n (i)=iのなるよつな最小のi。
フェルマーの小定理。あとは虱潰し。8回。
漸化式風。5 1を 3と 1 7に分解する。よくある手法。
3
数列の漸化式。MOD nで2つの漸化式が1つになる。重要手法。
1つに決まるので確かめて終わり。 第4部
4
平方数が否かを初めに決定する。重要手法。
互いに素。素数の設定の仕方。
分母と分子が互いに素のパターンは多い。
5
オイラー関数。分数を作る。
Σφ (a i)=a p=k。
6
ガウス記号。xy=k。
縦に数える
=上+下+線分上 (線分上は[√k])
≡[√k] MOD 2。 第4部
7
(1)部屋割り論法。
(2) 1 0と nは互いに素。
8
フィボナッチ数列
(1)帰納法。
(2)合同式。MOD amで、
(3)帰納法。2変数。注1は重要。
注2は難しいが有用。これを使うと(2) (3)は自明になる。
9
素因数分解。素因数ごとにそれぞれ分けて考える。 第4部
1 0
一般解を求める。
必要条件で絞って十分条件を確認する。1 7組。
1 1
(1)互除法。
(2)背理法。平方数なので kは素数 1個ずつ。
連続5整数なので5以上は含むとしたら1つの項だけ。
Nが平方数である事に反するので矛盾。
(3)部屋割り論法。
自然数の平方数の差の最小値は 3。
1と4を含むためには n= 1。
120は平方数ではない。
1 2
(1) 2の冪のとき。例のパターンに帰着される。
不等式評価が難しい。
(2)奇素数の時。これも不等式評価が難しい。
逆元の時と同じ流れ。実験で規則性を掴む。 第4部
13
フェルマーの小定理。mod10。mod9。
不等式評価。
14
分母を払う。
m≧ 20として虱潰し。
15
(m, n)=1の時, (mn, m+n)=1。(mn, m^2+n^2)=1。重要。
(1)分母と分子が互いに素。
(2)最大公約数を設定する。
左辺も右辺も既約分数なので比べられる。パズル。 第4部
16
有理数αは整数。
m+knの形だと必ずnで割り切れる。重要。
連続n整数なのでmodnでmと一致するものが必ずある。
というかこの手のタイプは必ず含まれるようにできている。
17
素数生成多項式は存在しない。興味深い問題。
平行移動する。f(x+1)=g(x)と置く。
g(0)=定数項は素数となる。g(kp)も素数かつ pで割り切れるのでg(kp)= p。これはx = 0, p , 2 p , 3 p ,…に対して全て pになるということを意味する。無限の解を持つ事になって不合理。素数。合成数。
18
m , nからa ,bに主役を変える。重要。
a ,bは奇数なのでdは奇数。
m , nは偶数なので 約数は2dの倍数になる。
平方数ならば奇数になるか4の倍数になる。重要。
2の倍数(かつ4の倍数にならない)なので矛盾。
第4部終わり。 今日も失礼します。最後まで完走してしまうかもしれない。
昨日も書いたけどやっぱり第1部は独特の位置付けだ。それだけで完結している印象がある。それは研究問題の存在。
第1部研究問題
1
(1)連続する奇数の和で表す(すると中央項は90の約数になる)
90の奇数の約数は6個ある。
和の中には負の数を含むものがあるがそれは綺麗にキャンセルされる。
例:(-1+0+1)+2+3+…+13=2+3+…+13。
従って6通りになる。
(2)(1)と同様に考えると、
連続する奇数の和で表す場合の数は奇数の約数の個数を数えればよく (b+1)(c+1)通りとなる。
別解では偶奇性を使う。重要。大小が決まるので個数が求まる。
2 全てmod8で考えると解ける。
(1)mod8で考えると8で割ると2余る。
(2)mod8で考えると8で割ると4余る。
(3)因数分解する。mod8で考えると余りは
2, 2, 2, 4, 2となるので、指数は1+1+1+2+1=6。 第1部・研究問題
3
公式L=Gabを使ってLを消去する。
すると文字式が因数分解される。1300を素因数分解する。
(文字は因数分解・整数は素因数分解、
といういつものパターン)
(1)場合分けして虱潰し、の基本技法。簡単。
(2)見つけるだけ。
4
継子立てという問題。1個置きにどんどん取り除いていく。2^n個だけ残った後は 余り2^0, 余り2^1, …という具合に綺麗に消えていく。なぜならば常に偶数個あるから。その場合、最後に残るのは2^n。
この問題では1996からスタートするので、
972個取り除いて1024個から再スタートと考える。
972番目は1943なので、1945から始めて1944で終わる。
一つおきではなくて二つおきとか三つおきとかでも同様に出来る。 第1部・研究問題
5
(1)オイラー関数φ(60)=60×1/2×2/3×4/5=16。
(2)17i, 17jを考える。(i,j は60の約数でi< j)。
0<1≦j-i≦59<60であるから、17(j-i)≡0 mod60ではない。
よって{17i}≡{i} mod60。
17^(φ(60))×Πi≡Πi mod60。∴ 17^(φ(60))≡ 1 mod60。
オイラーの定理。(a, n)=1の時, a^(φ(n))≡ 1 mod nの証明。
6
n!+k (k=2,3,4…,15)。nは13以上の整数ならば良い。 第1部・研究問題
7
(1)ユークリッドの互除法により、
(4x+9y, 3x+7y)=(x+2y, 3x+7y)=(x+2y, y)=(x, y)=1。
よって既約分数である。
(2)最も手数が多くなる数列はフィボナッチ数列になる。
r(k)=p(k)×r(k+1)+r(k+2) (k=1〜n)。
rとpは全て正の整数(1以上)だがr(n+2)=0, p(n)≧2である。
重要。aを最小にすると回数は最大になる。
r(n+1)≧1, r(n)≧2, となるので、
r(n+1)=1、r(n)=2、r(n-1)=3
a(2)=1、a(3)=2、…と対応して
1,1,2,3,5,8,13,21,34,55,89,144,233,377,610,987,1597より、r(1)=987, r(2)=610とすると、r(n)=2よりn=14。
8
mod4とmod8を併用すると良い。難しい。
(mod4だけでは荒すぎて無理)
n≡i mod4とn^2≡i mod8で A(0,0)かB(1,1)か
C(2,4)かD(3,1)。
xとyの差が2であると仮定して矛盾を導く。
(1)AとCの時。zはBかDになる。
どちらの場合でも0+4+1= 5になり矛盾。
(2)BとDの時。
zはAかBかCかDになることに注意する。
1+1+0=2 または 1+1+1=3 または 1+1+4=6
または 1+1+1=3となり、矛盾。 第1部・研究問題
10
(1)公式ab=17×23=391
(2)公式ab-a-b=391-17-23=351
11
素因数分解=因数分解を使うパターン。
(p-q)(p+q)=2^6×7^3
偶奇が一致するから2^4×7^3を分配する。
平方数ではないので約数の個数は偶数個。
平方数ではないので大小は決定する(上と同じ内容)。
5×4/2=10。
12
gについて解くとg=2,3が分かる。なかなか気づかない。ここは難しい。
その後は場合分けして簡単。
13
分数式が整数になる条件は
分子=0または|分子|≧|分母|が必要。最重要。
(1)グラフを描いて必要条件を出す。個別に確かめて十分条件
(2)(1)のkが必要条件になっている。個別に確かめて十分条件 第1部・研究問題
14
(a^2+b^2)(c^2+d^2)=(ac+bd)^2+(ad-bc)^2 ∈F。
15
繰り返しの構造を見抜く(知っておく)のがポイント。
(1)フェルマーの小定理より、n=6の倍数で十分。
下から調べるとnは3の倍数。
(2)フェルマーの小定理より、n=12の倍数で十分。
下から調べるとnは3の倍数。
16
(1)「分銅を使う・使わない」二進法の問題。
2^0から2^6までの7個あれば1〜127まで測れる。
2^0〜2^(n-1)までで1〜(2^n- 1)。
(2)「分銅を右に使う・左に使う・使わない」三進法の問題。
3^0から3^4までの5個を使うと1〜121まで測れる。
実験すると分かる。
3^0〜3^(n-1)までで1〜(3^n- 1)/2。(右と左があるので対称性より2で割る)
(1)(2)は同じ天秤の問題だが原理が異なる。(2)に注意。 第1部・研究問題
9
覆面算。ア〜オの和をp、カ〜ケの和をqとする。
実験をすると「p-q=15-9×繰り下がりの回数」が導ける。
p+q=45。繰り下がりがあることが分かるので、
p =21、q=24に決まる。
これで繰り下がりが二回あることが分かる。重要。
繰り下がりが二回あるパターンは全部で6通りある。虱潰しをして答えはそのうちの1通り。並び替えがあるので答えは2通りある。
研究問題終わり。 今日も失礼します。
第1部はいわゆる 1行問題。1日1セクションずつ16日で終わればいいという感じ。
§1
1(1)約数の総和の公式。(2)オイラー関数。
(3)(約数の個数/2)乗。
2(1)約数が偶数個⇔非平方数。(2)1×6と2×3で比べる。
3偶数回ひっくり返す⇔約数の個数が偶数⇔非平方数。
4約数の逆数の和をn倍すると約数の和になる。重要。
§2
1既約分数の分母を素因数分解した時に
素因数が2と5だけなら割り切れる。有限小数になる。
それ以外があると割り切れない。循環小数になる。重要。
分母が2^m×5^nになった時 大きい方が3になれば良い。7通り。それに3を掛けたものもOKなので14通り。
2(1)なるべく√の外に出してから平方数条件で文字を置く。(2)も同様。
3素因数分解。「最低何個各素因数を持つことが必要か」とやっていけばできる。
4前問と同様。
5(1)(2)ともに第2部の解説通り。1とも関係がある。 第1部
§3
1(1)L(24,33)を掛けると整数になる。G(175,140)で割ると最小に出来る。
2縦:横が2:1になれば良い。縦20個、横7個でOK。
3(1)AB=GLとL=Gabで解ける。(2)は公式は無い。虱潰しだが間違いやすいので20個全部書いてから消していくのが良いかも。G=1かつL=18。
4(1)(2)2個なので公式でOK。第2部との関連。
§4
1(1)(2)規則性。最小公倍数。切れ目にも注意。
2(1)(2)規則性。最小公倍数。ブロックごとに足さずに、最初と最後をダイナミックに足すのが上手い解法。
3(1)(2)mod10での規則性。余りの数列は繰り返す。
4この数列は60項で 1周期になる。規則性。
別解。mod10で15項ずつ同じ数が連続する。規則性。7倍されるので1,7,9,1を繰り返す。
5余りの数列は繰り返す。規則性。 第1部
§5
1(1)オイラー関数φ(504)(2)規則性。第2部。
2オイラー関数φ(140)。
3オイラー関数φ(k)に対して2Σφ(k) (2≦k≦10) +φ(1)。
4オイラー関数φ(600)/2。
§6
1(1)(2)中国剰余定理。
2中国剰余定理。
3modで。
4mod8、mod3、mod5。中国剰余定理。
5百五減算。第2部。中国剰余定理。 第1部
§7
1西暦≡昭和 mod昭和。
2ユークリッドの互除法。
3文字式でもユークリッドの互除法。
「5の倍数であって10の倍数ではない数」という点に注意。※20の約数の中の5の倍数は5,10,20がある。
4 ax+by=1の解法。ユークリッドの互除法。2と同じ。
5点と直線の距離。第3部に類題がある。格子点の整数論。
6(1)(2)文字式でもユークリッドの互除法。3と同じ。
§8
1mod6。小さい順に並べた時に前の数の2倍以上になっているので 2数の差は全て異なる。
2mod11。
3 (1)6m±1と置ける。重要。(2)因数分解。場合分け。
4mod100。xと(x-1)は連続する2数なので互いに素である。従ってどちらかが25の倍数になる。重要。虱潰し。
(2)は(1)を調べる。
5mod3とmod4で調べる。それぞれ2通り。
中国剰余定理により、mod12で4通り。 第1部
§9
11の倍数の判定法の証明。
1 aとdはすぐに決まる。bも絞られる。
2 11の倍数の判定法。
3 9の倍数の判定法。小数でも関係なし。
4 4の倍数なので下二桁は76に決まる。あとは9の倍数にすれば良い。加える個数で場合分けをする。
5 A≡0 mod 9より、B≡0 mod 9 同様にC≡0 mod 9。
あとは不等式評価で絞る。
A<10^150(=151桁)より、A≦9×150=1350
B≦9×3=27。C=9。
6 9の倍数かつ11の倍数。分けると簡単。
7 1998=2×9×111。偶数なので2,4,6,8が必要条件。
2,4,8は9と互いに素なので9個未満では9の倍数にならない。確かめると不適。666,666,666÷111÷2=
6,006,006÷2=3,003,003≡0 mod 9でOK。
666÷111÷2=3と666,666÷111÷2=3,003を確かめると不適。
§10
1 互いに素なので全てOK。
2 (1)(2)特殊解を見つけて係数を逆にする。
3 解法は同様。パラメーターの変域を調べる。
4 点と直線の距離。ユークリッドの互除法。
5 中国剰余定理。立式後は今までと同様。
6 Aが11の倍数と仮定するとBが11の倍数であることが示せる。逆にBが11の倍数と仮定するとAが11の倍数であることが示せる。係数行列式≡0 mod11ならばこうなる。 第1部
§11
1 因数分解。全て書き出すのが安全。
2 因数分解。自然数条件で絞る。
3 因数分解。自然数条件で絞る。
4 完全数の問題。因数分解。
5 オイラー関数。因数分解。
6 zを消去して因数分解。8:15:17のピタゴラス数。
§12
1 足すとxが5の倍数と分かる。xが5と決まる。ら
2 zを分離するとzが7の倍数と分かる。zが7に決まる。
yを分離するとyが5の倍数と分かる。yが5か10に決まる。
三文字の場合、一個だけ分離すると手早い。
3 最も小さいxの範囲が決まる。x=2,3。あとは虱潰し。
4 左辺は4次式なので因数分解ではなくて不等式評価。
5 y+z≦2xより、y+z=x+1に決まる。重要。
z+xをyで割ると商は1または2。zは6の約数と分かる。
6 非負整数をパラメーターに取ると殆どの項が0になる。
普通にはxyz≦4から絞る。
7 左の不等式からc>1になること、右の不等式からc≧3にはならないことが分かる。それらからc= 2に決まる。難しい。最小のcに当たりを付ける。 第1部
§13
1 因数分解。片方が±1。
2 mod5とmod8でOK。
3 計算するだけ。結果は覚えておく。
4 (1)連続する2つの偶数の片方は4の倍数になる。
(2)文字で置いて計算すると連続3整数の積になるので6で割り切れる。
5 帰納法、または与式=Σ計算^4、または通分して2,3,5で割り切れることを示す。
6 nCrはr!の倍数より、連続n整数の積はn!で割り切れる。
§14
1 4abを平方数にすれば良い。
2 (1)yとzの連立方程式にする。(1)を利用すると(2)が解ける。
3 平方数の前まで足せばピタゴラス数になる。
4 Σk^3=55^2。
5
6 (1)背理法mod 3。(2)背理法mod8。(3)背理法mod5。 第1部
§15
1 (1)mod13。(2)mod14。
2 mod 2とmod 3で1111≡1になることを利用。
3 フェルマーの小定理より、a^6≡1 mod7、
a^2≡1 mod3、a≡1 mod2。aが2,3,7と互いに素な場合。
どの場合でもa^7≡a mod42。これは互いに素でなくても成り立つ。
4 (1)適当にxに当てはめて右辺に1を作る。(2)因数分解。(3)3と13に分ける。中国剰余定理。
5 mod 4。
6 p≡0,1,2 mod 3。場合分けをして調べると矛盾が見つかる。
§16
1 142857のどこかから始めて繰り返す。
2 フェルマーの小定理より、10^16≡1 mod17。
10^8+1。同様に、10^6≡1 mod7。10^3+1。
3 前問を使う。
1/17=588235294117647/9999999999999999
1111111111111111は17の倍数。
4 2^5〜2^6-1まで32から63まで、32個。
5 1211212→10100101→165→2〜165で164個。
先頭に1をつけておく。そうしないと繰り上がりが出来ない。
6 100=64+32+4→1100100→729+243+9=981。 第1部
§3 AB=GL。大小関係を設定すれば機械的に証明出来る。
§11(1)p^2q=28。(2)2^(p-1)(2^p-1)偶数の完全数。
奇数の完全数は発見されていない。
§12 カーティスの定理。
§15帰納法。 第1部
§14
5 合同な三角形を作る補助点Pを取るのがポイント。
あとは相似な三角形を見つける。直角三角形が多く見つかる。△CGHに三平方の定理。連比。
正方形を菱形に変えるとピタゴラス数がアイゼンシュタイン数に変わる。合同な三角形。
余弦定理。相似な三角形。連比。 続けて書きます。質問とかあったらどうぞ。
マスターオブ場合の数
第4部
1
a>b+cとa<b+cは同数。最大数で場合分け。
a=b+cを調べる。20個あるので、答えは50個。
注も重要。
2
一つの切れ目に着目すると、 ABとBAの 2通りに対して
8C4 個あるから9×2×8C4。
(9×2×8C4 + 10C5)/10C5=5+1=6。
別解。5/9 ×9+1=6。
3
母関数。指数を素因数の個数に対応させる。
1,2,3,4,5,6→0+1+1+2+1+2→1+3x+2x^2。重要。
(2x^2+3x+1)^5=(x+1)^5(2x+1)^5
10×32+5×80+1×80=800。 場合の数
第4部
だいたい3問ずつでワンテーマって感じですか
4
同じものを含む順列の母関数。
実際に多項式を展開して800。
5
重複組合せの母関数。
nH4=n+3C4=(n+3)(n+2)(n+1)n/24。
6
これも展開すると49。 場合の数
第4部
7
三列に並べる。
8
偶数を2つに分けていくといつかは奇数だけになる。
同じ数があれば足していくといつかは全て異なる数になる。
9
全部並べて書いてから考える。
枠を作って中に入っているものを数えていく。 場合の数
第4部
10
(1)帰納法→部分積分法。(2)∫とΣの入れ替え。
11
階差数列を表す関数になっている。第4階差。
12
畳み込みの公式。二項定理。19C7と等しい。
50388。 場合の数
第4部
13
対応を考える。カタラン数cn。
14
カタラン数c(n-2)
15
カタラン数cn
16
22C5
17
(1)全射818520。包除原理。
(2)スターリング数10S4=34105。
18
最初に交わった所から入れ替えるという手法。
(10C5)^2-(10C4)^2=252^2-210^2=462×42=19404。
カタラン数の公式を導く時に用いる手法。 第1部
§1
1 6×6の表を作る。
2
(1)3回とも偶数。
(2)2回だけ偶数、1回は奇数。偶数のうち少なくとも1回は4。
別解。表を利用できる。
別解。母関数を利用できる。x^2+2x+3。
3樹形図の利用。
別解。経路の問題の考え方の利用。書き込み方式。
カタラン数でないこともわかる。c4+c3になる。
4(1)樹形図の利用。対等性の利用。
(2) 0とそれ以外に分ける。
5
(1)樹形図の利用。(2)(1)の部分的利用。
(3)偶数かつ3の倍数を調べる。
研究問題
1。10a+5b+c=100。
2。 2本目の当たりの位置で場合分け。
3。個数で場合分け。32, 311, 221に分かれる。
(2)それぞれに対して調べる。最後が多い。
母関数の利用。
(2)「前と違う色」を入れていけば良い。これは可能である。 第1部
§2
1(1)小さい順に並べる。
別解。スターリング数と同じ考え方。
(2)3の個数で場合分け。
2正方形の一辺の長さで場合分け。斜めの場合は内接する正方形を考える。別解。全部書いても十分。
3(1)直径。別解。直角の頂点から先に選んでも良い。
(2)正三角形のダブりに注意する。
4。3の倍数の条件に合わせてまず選んでおく。
漏れなくダブりなく。
研究問題
表を書く。公式がある。 第1部
§3
1(1)隣り合う→一纏めにして後でn!を掛ける。
(2)全体から隣合わないものを引く。余事象。
2。10C3。
3。(1)それぞれの組合せを掛ける。
(2)全体から男子だけを引く。余事象。
4。包除原理。簡単。
5。最短経路。平面。9C3。書き込み方式。
6。最短経路。立体。8C4×4C2。8!/4!2!2!。
7。重複組合せ。3H7。
自然数の個数に帰着させても良い。やや遅い。
最短経路としても解ける。9C2。重要。
研究問題。9H5=13C5。等しい場合もあることに注意。
まずは重複組合せで全部求める。次に同じ数字が何個あるかで場合分け。1+4×3+7×6より、1+4+7=12。 第1部
§4
1。約数の個数の公式。
2。6C2×5C2。
3。右下がりに点を取れば背反な場合分けになる。
場合分けに気付ければ計算は容易。
苦しいが書き込み方式の別解もある。
4。7×2^5。偶数だとOに、奇数だとGにいるがどちらでも選択肢は一通りしかない。
放射線の本数で場合分け。本数は戻ってくるので偶数である。7C2×2+7C4×4+7C6×6=
別解。環状線のうち、5本を通るか通らないかの2択。
5。6×6×6×2×2=864。難。
研究問題。適当な数字を一つ決めて内側から消去していくのを逆回しにすると常に外側から消去していることになる。一対一に対応するので、2^9=512。
別解。Σ9C(i-1)=Σ9Ci=2^9=512。
漸化式を作る。a(n+1)=2anより、2^9=512。 場合の数
第2部
1
整理して数える。樹形図。
基準を決めて整理すること。
6×6の表を作る。
1。5通り。2。12通り。小さい順に書く。
8通り。漏れなくダブりなく。 2
漏れを防ぐ。ダブりを防ぐ。
排反。全ての場合を排反に場合分けする。
6通り。11通り。ダブりがある。
3
6通り。
4
交わりと結び。または。かつ。
全体集合。補集合。余事象の利用。
ド・モルガンの法則。分配法則。
全体を1、補集合を1- sなどとすると説明がつく。
和の法則。積の法則。余事象。補集合。
56通り。55通り。包含と排除の原理。
撹乱順列。
5
順列は順序を付けて並べる。
組合せは順序を気にしない。
5P3=60。7C3=35。4C3=4。 6
数列の母関数。
7
35通り。書き込み方式。パスカルの三角形。
漸化公式。平行等式。吸収等式。
公式の作り方。
8
重複順列。6^r。64通り。 第2部
同じ物を含む順列。7!/2!2!3!=210。
重複組合せ。3H5=7C5=21。
9c2=36。3H10=12C10=66。
分割数。公式は無い。115, 124, 133, 223の4通り。
3!=6。公式または重複度。 第2部
一対一の写像。単射。
上への写像。全射。
上への一対一写像。全単射。置換。
3241576。60。単射。243-96+3=150。全射。
ベン図で考える場合は否定命題にしておく。
増加写像の個数。4H6=84。
撹乱順列。0,1, 2, 9, 44, 265, 1854。 第2部
順列。重複順列。n^m。順列nPm。全射の個数。
組合せ。重複組合せnHm。組合せnCm。
上への写像は不定方程式の解の個数(n-1)C(m-1)
スターリング数。全射。6S3=90。
別解。(729-192+3)/6=90。
全射の個数をn!で割るとスターリング数になる。
写像の個数はΣS。全射はスターリング数。
単射は1か0。
全射は分割数。全射は分割数p。単射は1か0。
写像の個数はΣp。 第2部
n-1試合。
5→4+3。最後で場合分け。
5→4+3。最初で場合分け。式はこの場合同じになった。
フィボナッチ数列になる。1,2,3,5,8。
視覚化する、抽象化する。
地図の塗り分けは不可能。
カタラン数。n×nのマス目で、対角線よりも一個上の線を引いてそれに接触しないような場合の数を数える。
2nCn-2nC(n-1)。2nCnをn+1で割る。
c5=42。252/6=42。
グラフ。置換。
正四面体は下が正三角形、上は一点。
立方体は下が大正方形、上は小正方形。
正八面体は下が大正三角形、上が小正三角形。逆向き。暗記。
国は点、国境は辺。グラフ。
置換3154276は、1352, 67, 4と考える。ループ。
母関数。
(1+x)^nは組合せnCk。
(Σx^k)^nは重複組合せnHk。3H4=15。 第0部
原始的な数え方しか出来ない。
12日。6C3/2=10。
4。3。
D=1の場合を考えれば十分。
5×4×3×3×3×3=1620。
漏れなくダブりなく。排反。
どこで初めてその状態になるか。
6+5×6=36。それぞれ1箇所だけ赤玉が入れない所があることを見抜く。
対等性を用いる。30+120=150。
底辺に着目する。(4+3)×5=35。
頂点に着目する。(5+2)×5=35。 第0部
基準を明確にしなかったことが原因。
27+3=30。
3個連続を直接数える。42-6=36でも良い。
6×13C3-7=6×286-7=1709。
赤3個は1通り。赤1個は27通り。赤2個は9通り
37通り。
自分の手を動かして具体化していく。
実験をすること。
一般化につながる規則性を見出すことができる。
手作りということ。ダブルカウントの見本市。
排反がどれほど重要か。対等性。単に学ぶまたは単に鑑賞するという姿勢でも良い。 第1部
§5
1。000〜999まで。3000/10=300。
別解。100+100+100=300。対等性。
2。3回目までは任意で4回目は一通りだから216。
3。二位か三位なので、7!×2/3=3360。余事象でも。
4。グラフを使う。意外と少ない。2×6=12。
5。36+12=48。2で割って24。
研究問題。7より大きいカードが後から出て来なければ良い。7以上の数字の中で最後に出ることになり1/7。 第1部
§6
1。7!/2!2!3!=210。
2。210。
3。210/2!=105。
別解。7C3×4C2×3/3!=35×6×3/6=105。
4。115, 124, 133, 223。21+105+70+105=301。
スターリング数7S3。
5。重複順列を考えて3^5=243。243-3=240。
240/6=40。40+1=41。
研究問題。13の次は1と考える。13C3/13=22。 第1部
§7
1。47。
2。10000/103=9708。調整して9709。
有り得ないのは291個。全て異なるから。
別解。実際に調べると34,35が無い。97あまり9
291個。
3。6×10=60。
4。上向きは普通に21+15+10+6+3+1=56。
下向きは対応を考えて15+6+1=22。78個。
別解。下向きも地道に数えられる。
上向きをいっぺんに。8C3=56。
発展問題。線が引いてない場合。
21+15×2+10×3+6×4+3×5+1×6=126。
別解。あと2本増やして対応を考える。9C4=126。
5。縦横2本ずつの線と対応する。それに2つの道順が対応するから2×8C2×8C2=2×28×28=784×2=1568。
研究問題。8×8に増やして対角線上の格子点から選ぶと長方形と対応するから、9C4=126。
別解。8C4+8C3=70+56=126。重要公式が確認された。 第1部
§8
1。7C2=21。3H5=21。
別解。xを固定して場合分け。
2。1≦x<<y<<z≦10⇔1≦x<y-1<z-2≦8。8C3=56。
xを固定して場合分け。
3。黒→その間に白。8C4=70。
4。a=15-xなどとおく。a+b+c=15。a≧0。
よって3H15=136。
別解。xの値で場合分け。
研究問題。跳ばす個数は8になるから、
7C3=35。それぞれを先頭に見ていき、ダブりを考えると、35×12/4=105。
別解。7C3×12/4=105。
1を選ぶ場合は35。1を選ばない場合は
2≦x<<y<<z<<w≦12⇔2≦x<y-1<z-2<w-3≦9。
8C4=70。よって105。 第1部
§9
1。1+Σk=(n^2+n+2)/2。
別解。1+交点の個数+直線の本数。
1+nC2+n。
別解。漸化式。a(n+1)=a(n)+n+1。
2。35+27-1=61。442個。
10×5=50個。
3。円周上の4点→内部に交点が1個、
外部に交点が2個。
(1)10C4×2=420。(2)210。
(3) 1+交点の個数+直線の本数=211+10C2=256。
4。四角形一個と黒点が一個対応する。
8C4=70個。ベクトル。頂点からは7個のベクトル、
黒点からは4個のベクトルが出ている。
総数は336個。よって168個。
研究問題。k枚目の平面との各平面の交線はk-1本あり、問1と同じ状況になる。計算すると(k^2-k+2)/2。
1+Σf=1+n+n(n+1)(n-1)/6=(n^3+5n+6)/6。
関連問題。2A+B=4×nC2。B=2nと決まる。
A=n(n-1)-n=n^2-2n。A+B=n^2本。 第1部
§10
1。acb+adb-acdb=3×120+210×3-3×3×21=
360+630-189=801。
2。6^6-2×5^6+4^6=46656-31250+4096=19502。
3。6^6-3×5^6+3×4^6-3^6=
46656-46875+12288-729=11340。
4。(1)5^5-4^5=3125-1024=2101。
(2)4^5-2×3^5+2^5=1024-486+32=570。
5。ループは120通り。
(1)120-4!×2!=72。
(2)120-2×4!×2!+3!×2!×2!=48。
別解。(1)3!×4×3=72。(2)2!×2!×3×2=24。72-24=48。
研究問題。撹乱順列。0,1,2,9,44,265。
包除原理。
1×6!-6×5!+15×4!-20×3!+15×2!-6×1!+1×0!
=720-720+360-120+30-6+1=265。
360-120+30-6+1=265。 第1部
§11
1。全てに通じる考え方。9C3=84。
4の約数は1,2,4。約数倍数関係に注意。
90°タイプは無い。
180°タイプ。2倍。360°タイプ。4倍。
84=4+80→2+20=22。
2。9C3=84。9の約数は1,3,9。
120°タイプ3倍。360°タイプ9倍。40°タイプは無い。
84=3+81→1+9=10。
別解。黒三連続は1。黒二連続は5。
一個空きは3。二個空きは1。よって10。
別解。3H6=28→1+27→1+9=10。
3。8C4=70。8の約数は1,2,4,8。
2と4の約数倍数関係に注意。
360°タイプ。8倍。180°タイプ。4倍。
90°タイプ。2倍。45°タイプは無い。
2+4+64→1+1+8=10。
4。8!/2!2!4!=420。
1,2,4,8。約数倍数関係に注意。
360°タイプ。8倍。
180°タイプ。4倍。
90°タイプは無い。45°タイプは無い。
420=12+408→3+51=54。
研究問題。6×4=24通り。8!/24=1680。 第1部
§12
1。アイ。書き込み方式。18。55。
別解。フィボナッチ数列。
1,2,3,5,8,13,21,34,55。
2。グラフ。124。
3。グラフ。183。
4。グラフ。60/3^5=20/81。
別解。漸化式。a(n+1)=3b(n)。
b(n+1)=a(n)+2b(n)。
10362160
01272061
60/243=20/81。
3と4が同じになる理由。cnをbn、gnをanとみなせば同じになる。
5。グラフ。1^2×6+2^2×3+5^2×3=93。
研究問題。グラフ。場合分け→実際に調べる。
6+6+4+6+6+4+4+4+4=44。 第1部
§13
1。a(n)=a(n-1)+a(n-2)。1,2,3,5,8,13,21,34,55,89。
別解。2段をk回、1段を(10-2k)回とする。
合計(10-k)回上る。(10-k)Ck=1+9+28+35+15+1=89。
2。○a(n-1)、×○a(n-2)。144。
別解。×がk個の時、○は(10-k)個。(11-k)Ck
=1+10+36+56+35+6=144。
解釈の仕方。11段の階段の上り方と同じフィボナッチ数列。
3。全部でanとし、ABの時をbnとする。
AA+AB+BA→a(n)=a(n-1)+2b(n)。
b(n)=a(n-2)+b(n-1)。漸化式を2つ作る。
a(n)-a(n-1)=2a(n-2)+a(n-1)-a(n-2)
a(n)=2a(n-1)+a(n-2)。3,7, 17, 41, 99, 239。
別解。p(n)=p(n-1)+2q(n-1)、q(n)=p(n-1)+q(n-1)
p1=1、q1=1より、239。
137174199
125122970
4。a(n)+a(n-1)=3×2^(n-1)。
a8=384-a7=384-192+a6=192+96-a5
=288-48+a4=240+24-a3=264-12+a2=252+6=258。
別解。a(n)=a(n-1)+2a(n-2)。a2=6、a3=6より、
6,6,18,30,66,126,258。
5。スターリング数の漸化式。
4S2=7。(n+1)Sr=nS(r-1)+r×nSr。
1,1,1,1,1,1,1
0,1,3,7,15,31,63
0,0,1,6,25,90,301
0,0,0,1,10,65,350。
研究問題。ハノイの塔。
AからCにn個。→AからBに最大を渡す。
→CからBにn個。
a(n+1)=2(n)+1。1,3,7,15,31,63。 第1部
§14
1。(1)8!/2!2!2!2!4!=105。105^2=11025。
別解。8C2×6C2×4C2×2C2/4!=28×15×6/24=105。
(2)ループ。上下が逆になるが結局8本が8人の円順列に対応して、7!=5040。
別解。7×6×5×4×3×2×1=5040。
2。
7人のループ。6!/2=360。裏返したら同じになるものがある。
3人のループと4人のループ。7C3×2!/2×3!/2
=105。足して465。
0-7, 1-6, 2-5, 3-4。
3。
一個ループと三個ループ。
3と1で6を作る。
3+3。6C3/2×2×2=40。
3+1+1+1。6C3×2=40。
1+1+1+1+1+1。1。合わせて81。
4攪乱順列。モンモールの問題。ラベルの張り替え。
求める場合は一個ループが無い場合の順列である。ら
・n+2が二個ループに所属している時。
誰と二個ループを作るかでn+1通り、そのそれぞれに対してa(n)通りあるから、(n+1)a(n)通り。
・n+2が三個以上のループに所属している時。
自分以外のn+1個でa(n+1)通り。そのそれぞれに対して自分が入る場所はn+1通りあるから(n+1)a(n+1)。
0,1,2,9,44,265,1854,14833。
研究問題。シャッフル。
01020304050607080910111213141516
01030507091113150204060810121416
01050913020610140307111504081216
01090210031104120513061407150816
01020304050607080910111213141516
1
2359
471310
611
8151412
16
1個、4個、4個、2個、4個、1個。
4回のシャッフル。 第3部
1・1
(1)7C2=21。(2)Σ7Ci=2^7-2=126。2^(n-1)-2。
1・2
2^(n-1)通り。
1・3
2^9=512。
1・4チャンピオンの問題。
※※5△△4×3=12。
※※※5△4×3=12。
132, 213, 231,
※※※※5。3×2+3×1+2=11。よって35。5f3。
(n+1)fk=nf(k-1)+n×nfk。
1・5モンモールの問題。攪乱順列。
0,1,2,9,44。 攪乱順列fは1個だけ置けない場所がある
gは一個だけ好きにおいてもよく、他は置けない場所が一個だけある。
2・1
7!/2 ×2+4×7!/2!2!=5040+5040=10080。
注。8!/2!2!=10080。
2・2
7!-6!/2!×2=5040-720=4320。
2・3
(1)10C6=210。別解10C6=210。別解10C4=210。
(2)0または1にして7C4=35。
2・4
3×2^6=192。2^3=8。192-8=184。
2・5
(1)3^5=243。(2)cの前はcというルール。
2^5+2^4+2^3+2^2+2^1+2^0=63。
どこで初めて出るかで場合分け。
27+27+27-3+27-6=99。
6×3=18。99+99-18=180。243-180=63。
2・6
aaaaaa・aaaabb・aaabbb・aabbcc
n+n(n-1)×15+n(n-1)/2 ×20+n(n-1)(n-2)/6 ×15×6
n+15n^2-15n+10n^2-10n+15n^3-45n^2+30n
n(15n^2-20n+6)。 第3部
3・1
1000+900+810+729=3439。
別解。10^4-9^4=10000-6561=3439。
3・2
(1)まずは区別する。5!=120。3×4×4!=288。
408/2!=204。
(2)まずは区別する。2:3×4!=72。
それ以外は3×5!=360。
432/2!=216。
3・3
k=2の時。24/72=1/3。
k=7の時。k=2の時と一対一に対応する。
12×7!/9! ×2=24/72=1/3。
k=4の時。42×4!/9×8×7×6=24/72=1/3。
別解。どの場合も余りが0,1,2であるものが同数ある。
以前やった手法。1つずつ大きくしていく。
kと3が互いに素ならば同数になる。
この仮定を満たせば常に1/3になる。
3・4
8進法で764。戻すと、875。
01234567→01235678と読み替える。 第3部
4・1
(1)(2n+3)C3×2nCn/(2n+3)=(n+1)×(2n+1)!/3(n!)^2
(2)(2k+1)×2kCk/(2k+1)
+{(6k+3)C3×6kC3k -(2k+1)×2kCk}/(6k+3)
={(6k+3)C3×6kC3k -2(2k+1)×2kCk}/(6k+3)
4・2ネックレス
(1)9C1×8C2=252。252/9=28。別解。8C2=28。
(2)左右対称なものは4つ。28=4+24→4+12=16。
4・3立方体の色塗り
(1)5×3!=30。別解。6!/24=30。
(2)5×3!/2=15。別解。6×4!/24=
(3)4C2=6。 4・3
別解。(1)重複度は6×4=24。720/24=30。
(2)重複度は6×4=24。(5×1×4!+5×4×3×1×2+5×4×3×2)/24=15。
置き方を固定する。
(3)重複度は2×2+2×4=12。
(4×3×2+4×3×2+4×3×2)/12=6。
第3部
5・1
(1)6C4=15。
(2)Aを8以下、Bを3以上とすると、
10C4-8C4-8C4+6C4=210-70×2+15=85。
5・2
(1)1≦x<y-(n-1)<z-(2n-2)≦n+2。(n+2)(n+1)n/6。
(2)Aをy-x>n、Bをz-y>nとする。
3nC3-2nC3×2+nC3=n^2(2n-1)。
5・3
(1)M^4-(M-1)^4=4M^3-6M^2+4M-1。
(2)12k^2+2。
5・4
(1)偶奇性。nC2×2=n(n-1)。
(2)(1)のようにならない組を選べば良いから、
{2nC3-n(n-1)}/2。同じにならないものは偶数個あるから2で割る。n(n-1)(4n-5)/6。
別解。原題の誘導。i-k個を2個ペアにしてΣする。最後は余ったn-Kを加えると(n-k)^2。i-k-1を2個ペアにしてΣすると(n-k)(n-k-1)。合わせてkをΣするとn(n-1)(4n-5)/6。 第3部
6・1
(1)3Hn=(n+2)(n+1)/2。
(2)3つ等しい。1組。2つ等しい。3m組。
全て異なる(3m+1)(6m+1)-1-9m=18m^2
∴3m^2+3m+1。一般論は無理。分割数の総和。
6・2
x+y+z+w=n。4Hn=(n+3)(n+2)(n+1)/6。
6・3
隣り合わないという条件は1〜11-n。
f(n)=(11-n)Cn。代入して行くと、
1, 10, 36, 56, 35, 6, 0, …よりn= 3。
6・4
(1)111, 120→1+6=7通り。nC1+nC2=n(n+1)/2。
(2)Σx(i)=r (x=0,1,2)。y=2-xと置くとy=0,1,2。
Σy= 2n-r。よってnAr=nA(2n-r)。
(3)ΣnAi=3^n (i=0〜 2n)。nAn=3^n-2×nAi (i=0〜n-1)より、奇数である。
6・5
x1=0をf0、x1≠0をf1とする。
f0(k,n)=f(k-1,n)。
f1(k,n)=g(k,n)。
∴f(k,n)=f0(k,n)+f1(k,n)=g(k,n)+f(k-1,n)。
nを固定すると、2a(k)=a(k-1)+(n+k-1)C(k-1)。 第3部
7・ 1
(1)4^6=4096。重複順列。
(2)4C3×(3C3×3^6-3C2×2^6+3C1×1^6)
=4×540=2160。
7・ 2重複組合せ。
(1)4H6=84。(2)4C3×5C2=40。
7・ 3
(1)8C2=28。
(2)x+y+z=6。a+x=6。0≦x≦5。3H6-3=25。
7・4本は区別。人は区別。組は区別しない。
(1)12C3×9C4×5C5=220×126=27720。
(2)12C4×8C4×4C4=495×70=34650。
(3)34650/3!=5775。
(4)12C2×10C2×8C8/2!=66×45/2=33×45=1485。
7・5スターリング数の総和。
nS3+nS2+nS1=
(3C3×3^n-3C2×2^n+3C1×1^n)/3!
+(2C2×2^n-2C1×1^n)/2!
+(1C1×1^n)
=(3^n-3×2^n+3)/6+(2^n-2)/2+1
=(3^(n-1)+1)/2。
1-(1)3^n。 8・1
(1)3×70=210。(2)11C5-10×10=11×6×7-100=362。
(3)100+35×3-10×3=175。287。
8・ 2
書き込み方式。485。
別解。右下がりの折れ線で塞ぐようにして場合分け。
7+18×6+23×15+4×6+1×1=485。
8・1追加。
Pは中心。362/2=181。
8・3
第4象限を通る。第2象限を通る。原点を通る。
で場合分け。排反である。
(16C8-6C3×10C5)/2=10×6×7×6
15×13×11×3-10×6×7×6=45(143-56)=3915。
8・4
書き込みは大変。排反な場合分け。
22^2+16^2+30^2+8^2+10^2+1^2+1^2
=484+256+900+64+100+1+1=1806。
対称性、対等性、排反。 9・1
1×6+2=8個。
(2n+1)C3=(4n^3-n)/3。3の倍数。
n(2n+1)。3の倍数。(n-1)(2n+1)+(2n+1)/3
=(6n^2-n-2)/3。二等辺三角形と正三角形。
9・ 2。台形と長方形。
奇数角形の時。nC2×(2n+1)=n(n-1)(2n+1)/2。
9・ 3
偶数角形の時。n((n-1)C2+nC2)-nC2
中心を通る二本の対角線の 1組と長方形1つが対応する。
(n(n-1)(n-2)+n^2(n-1)-n(n-1))/2
=(2n^3-5n^2+3n)/2。
9・4鋭角・鈍角・直角。
直角が一番簡単。鈍角も簡単。
全部で2nC3個。
頂点 1が鈍角⇔ 2≦i< j≦2n、i< j-n。
2≦i< j-n≦n。(n-1)C2個。よってn(n-1)(n-2)個。
直角は(2n-2)n=2n(n-1)個。
鋭角はn(4n-2)(n-1)/3 -n^2(n-1)
=n(n-1)(n-2)/3。鋭角:鈍角=1:3。
1つの鋭角三角形に対して3つの鈍角三角形が対応する。
中心に関する対称点を取って三角形を作る。
9・5
3≦y<<z<<w≦11と⇔3〜9⇔1〜7。7C3=35。
2≦x<<y<<z<<w≦12⇔2〜9⇔1〜8。8C4=70。
105個。中心を含まないのは各直径に対して2個ずつえる。直径の上に中心が乗ってしまう。
105-12=93個。 10・1
7C2×5C2=210。3×4×3×2+4×3×2×3-3×3×2×2
=72+72-36=108。210-108=102。
10・ 2
(1)領域の個数=1+交点の個数+直線の本数。公式。
1+nC2-3C2+n=(n^2+n-4)/2。
(2)交点の個数×2+直線の本数。公式。
(nC2-3C2)×2+n=n^2-6。
10・3
(1)f=nC2×2=n^2-n。
(2)g=2(n-1)×n=2n^2-2n。
(3)h=2+f=n^2-n+2。
P。2P。P+2。
球面の大円による分割。平面上の円の分割。
10・4
f5=12。f4=4。f3=16。∴12×10+4×4+16×1=152。
25C3-152=2148。
10・5
8C3=56。交わる2本の対角線⇔4つの頂点
⇔4つのT図形。8C4×4=280。336。
別解。6C2×8+5C2×8+(4C2+2C2)×8+
(3C2+3C2)×4=120+80+56+24=280。 第3部
11・1
(1)x(n+1)= 3a(n)。
(2)a(n+1)=x(n)+2a(n)。
(3)x(n+2)= 3x(n)+2x(n+1)。x1=0、x2=3より
x(n)={3^n+3(-1)^n}/4。
別解。anは不要。x(n+1)=3^n-x(n)。
補集合に着目。
11・2
a→cかつb→c。
右端がcであるもの:cn通り。
右端がaであるもの: (xn-cn)/2。
右端がbであるもの:同上。
x(n+1)=3cn+xn-cn=xn+2cn。
c(n+1)=xn。∴x(n+1)=xn+2x(n-1)。
x1= 3、x2=5より、xn={2^(n+2)-(-1)^n}/3。
別解。最初で場合分け。x(n+2)=2x(n)+x(n+1)。
補助数列。
11・3
(1)3C3×3^m-3C2×2^m+3C1×1^m=3^m-3×2^m+3。
(2)f(m+1,n)= n×f(m, n)+n×f(m, n-1)。
(3)f(m+1,m)= m×f(m, m)+m×f(m, m-1)。
a(m)=m×m!+m×a(m-1)。両辺をm!で割ると
b(m)=m+b(m−1)。 b(m)=m(m+1)/2。
a(m)= (m+1)m×m!/2。
別解。(m+1)C2×m×(m-1)!=(m+1)m×m!/2。 12・1
二項係数の公式。
(1)kC1×nCk=nC1×(n-1)C(k-1)。
(2)g=Σk×nCk×x^(k-1)=Σn×(n-1)C(k-1)×x^(k-1) (k=1〜n)。
=n(1+x)^(n-1)。二項定理。
12・2
パスカルの三角形。二個ずらして重ねたもの。
nAk=nCk+nC(k-2) (2≦k≦n)。最短経路。
12・3
(1)x=i-1のどこを横断するかで場合分け。見抜く。
(2)当てはめて丁寧に対応させる。(m+n-2)C(n-1)。
今度は横断しないで、x=iにぶつかったら左折して右折するということで一番上ではぶつかれない。
12・4
積分する。帰納法。
(1)途中 0〜 -1まで積分したと見なす所がポイント。
別解。積分無しで式変形だけでも出来る。
(2)帰納法。
別解。帰納法無しで式変形だけでも出来る。
意味をなさないものは0と定義して議論する。 13・1
(1)5×4×3×6×5=1800。(2n+1)P(n+1)×3nPn。
(2)対偶を取ると偶数番目には必ず偶数がある。
4×3×7×6×5=2520。2nPn×(3n+1)P(n+1)。
13・2
階差の大きさがポイント。
グラフを描く。微分する。増加数列。
f'(12n)=f'(24n)=1。
0〜12nまでと24n〜36nまでは全ての数字。
→値域の個数。
12n〜24nまでは全て異なる。
→定義域の個数。
f(0)=0。f(12n)=7n。f(24n)=20n。f(36n)=27n。
7n+12n+7n+1=26n+1。
13・3
遠回りして行くことは出来ない。
最短経路+2本。(n+3)C3×6nC2。
正方形が出来る場合をダブルカウントしている。
(n+3)C3×6nC2-n×(n+2)C2。
ある横線を通って次に縦線を通ることが決まっている場合の数は、高さを一段低くした経路と等しい。
(n+m)Cm×2mnC2-n×(n+m-1)C(m-1)
原題。(n+3)C3×6n
13・4
昇りだけ踏むA、降りだけ踏むB、両方とも踏むC。
AとBは連続できない。
an+1=bn+cn、bn+1=an+cn、cn+1=an+bn+cn。
a2=b2=c2=1より、an=bn。
2an+1= 2an+ 2cn、cn+2-cn+1=cn+1-cn+2cn、
c(n+2)=2c(n+1)+c(n)。c3=3、c4=7、c5=17、
c6=41、c7=99。 1
4!=24。樹形図。3!=6。対等性。3!=6。6×2=12。
数える時は何番目から数えようと自由。
数える順序の自由さ。最大の特徴。
例題1
(1)9×9×8=648。(2)9×8+4×8×8=328。
例題2
6C3×3!=120。別解。x×3!=6!、x=120。
確率は1/3!=1/6。
例題3
8!/2!2!。7!/2!×2+7!/2!2!×4=5040+5040=10080。
1個だけ残しても残さなくても同じになる。
例題4
6!/2!2!2!=90。ABを数えて後から6倍する。
C*C*、C**C、*C*C。2+2+1=5→30。
例題5
(1)連続しないものは10×9×9×9=7290。2710。
(2)含まないものは9^4+9^4-8^4=9026。974。
排反。どこで初めて連続するか。
10×1×10×10+10×9×10+10×9×9=2710。 (1)10C3=120。(2)12C3=220。(3)8C3=56。
(4)9C2=36。(5)3H10=66。
重複組合せ。
例題1
(1)6C3×3C3/2!=10。(2)6C2×4C4=15。
(3)7C2×5C2×3C3/2!=105。
例題2
スターリング数=全射/階乗。
9S3=(3C3×3^9-3C2×2^9+3C1×1^9)/3!
=3281-256=3025。
8C1×7C1×6C2×4C2×2C2/2!3!=28×15=420。
7C3=35。5C2×4C2=60。
例題3
書き込み方式。右下がりの折線で場合分け。
●4+30+80+15=129。○1+18+75+35=129。
10C4-21-45-60+15+30=129。 例題1
a=-1、b=1を代入する。
別解。特定の要素dが入るか入らないかで要素の個数の偶奇は変わり、その個数は等しい。
例題2
重みの平均は0とnの平均であるn/2。
公式5は和分の公式においてn→n-m+1としたものと一致する。実質的に同じ。積分。 練習1(1)5×4×3×6×5=1800。(2)4×3×7×6×5=2520。
練習2。6C1+7C3=41。
練習3。10!/4!3!3!=10×12×7×5=4200。
練習4。(1)3!/2! ×4!/2!=36。(2)4!/2! ×5×4C2=360。
練習5。7!/2! ×2 -6!=4320。
練習1。9C4×4!=3024。注意。
練習2。3H6×3H4=28×15×420。
練習3。x+y+z+w=17。4H17=1140。
2dが満たせば2d-1も満たすので奇数のものは偶数のもの以上ある。19C2+17C2+15C2+13C2+11C2
+9C2+7C2+5C2+3C2=171+136+105+78+
55+36+21+10+3=615。
練習4。12C4×8C4×4C4/3!=495×70/6
=165×35=5775。9C3×6C3×3C3=84×20=1680。
練習5。(1)3。(2)15+20+15=50。(3)15+10=25。 練習6。7C4=35。
練習7。(1)1+36+196+(1+9+4)^2=429。
(2)9C4=126。1つの長方形⇔4本の直線
⇔点線上の4点。
(1)別解。カタラン数。
14C7-14C6=14C7/8=c7。
13×11×3=429。
練習8。内部の1交点⇔ 2本の対角線⇔4個の頂点。
10C4=210。
別解。対角線で2つに分ける。
練習9。AとBは一対一にたいおするから。
問。2C2×2^5-2C1×1^5=32-2=30。全射の個数。
5S2=30/2!=15。2S1=1C1×1^2/1!=1。 組合せ論的確率。同様に確からしい。
同時型。戻さない形。戻す型。
復元抽出。非復元抽出。5C2=10。nCk。
同様に確からしい。対等性。5P2=20。nPk。
同様に確からしい。5^2=25。
重複順列。n^k。
組合せ。順列。重複順列。同様に確からしい。
4。7。9。同様に確からしくはない。
対等性を基盤にして同様に確からしいを考えなければならない。 物を全て区別した順列。同様に確からしいもの。
4C2=6。同時型⇔戻さない型。
例題1
8C3=56。同様に確からしい。4×3×2/56=3/7。
戻す型では組合せは同様に確からしくはない。
組合せのみ。順列も組合せも。重複順列のみ。
が同様に確からしい。重複組合せは同様に確からしくはない。サイコロ。コイン。じゃんけん。
(6+15+15+12+12+24)/216=7/18。
例題3
(k-1)C2/10C3。最後の10番目に引く人。 ■ このスレッドは過去ログ倉庫に格納されています