Download presentation
Presentation is loading. Please wait.
1
A path to combinatorics 第３章後半(Ex3.8-最後)
京都大学情報学研究科 通信情報システム専攻 岩間・伊藤研究室 M１ 西田 尚平
2
Ex ３.８ を証明して下さい 方針:再帰的（帰納的？）に示す とする は、すぐに確かめられる 任意のｎで が成立してほしい
3
公式B 項を分離
4
Ex ３.９ を証明して下さい 方針:これも帰納的に示す とする を示せばよい→差分が簡単に書ける
5
初項と末項を持ってきた 展開してくくりだす
6
ｍからi個、ｎから(k-i)個取ってくる
Ex ３.１０ を証明して下さい Solution: ｍ個 ｎ個 ｍからi個、ｎから(k-i)個取ってくる
7
Ex ３.１１ この４つの数が等差数列では無い事を証明して下さい Solution: とする もし等差数列なら になるはず！ ⇒方針はこれが矛盾することを示す
8
とすると… ｘの二次方程式！！ xの二次方程式がxに対して解を高々２つまでしか持たない⇒ｋとｋ＋１
9
全て解は求まったはず・・・ところが も解になりうる ⇒全ての解が求まったことに矛盾！！ ⇒最初に仮定した、等差数列というのがダメ
10
A C B Ex ３.１２の前に… Cyclic 3-Setとは ある３チームが総当たり戦を行うとする、その
チームをそれぞれA、B、Cとする。 その時、その試合の結果が、 AがBに勝ち、BがCに勝ち、CがAに勝って いるように３すくみの関係になっていた時 このチーム集合{A,B,C}をCyclic 3-Setという A C B
11
Ex ３.１２ ２３のバスケットボールチームが引き分け無しの 総当たり戦を行ったとする。 その結果表を見た時、３チーム部分集合{A,B,C}を 全て見てCyclic 3-Set となっているようなものをカウントして行く。 最大何個そのような部分集合ができうるか。 × × ○ ○ ○ ○ ○ × × がCyclic 3-set × × ○
12
方針： Cyclic 3-Setでは無いものの数を最小にするような 対戦結果を与えることでCyclic 3-Setの最大値を 求める そもそもCyclic 3-Setでは無いものには どのような条件があるのか？
13
A C B Cyclic 3-Setでは無い部分集合の必要十分条件は 部分集合のうちある１チームが他の２チームを 倒している場合である。
部分集合のうちある１チームが他の２チームに 敗北している場合である。
14
するとCyclic 3-Setでない部分集合の数Mは
× ○ あるチームiの 勝利した数を 敗北した数を と置く ○ ×× … … ○× ○ × ○ するとCyclic 3-Setでない部分集合の数Mは
15
２乗平均平方根－相加平均の関係 ２乗平均平方根－相加平均の関係 ２乗平均平方根－相加相乗平均－ハーモニック平均の関係
16
より 等式は ⇒全てのチームの勝ちと負けが等しい 全体から引き算をして 組が最大！ でもそもそもそんな対戦表作れんの？
17
できます チーム i は以下のチームに勝ったという対戦表を作る チーム たとえばチーム５なら６から１６に勝つ
18
とかいろいろ書いてきましたが…
19
nのp進数表現 関数のmodの定義 全ての に対して が で割り切れる ⇒ が を割りきり、 はそのような数の中で最大という記号
20
定理３.３ を素数として を任意の正の整数とする と書ける時、下の数式が成り立つ。 方針： は を展開した時の の係数！！
21
定理３.２(ｋ)より はpで割り切れるので これを繰り返し適用して を で分解して記述してみると…
23
の係数 全てのｘで成立するためには でなくてはならない
24
定理３.４ を素数とすると が を割りきる必要十分条件は が と をp進数上で加算した時に起こる キャリーの数以下であることである キャリーの数ってなんだ？ １０進数上で２！ 補題３.６を使用して証明する（補題３.５を使って補題３.６を証明）
25
補題３.５ を素数とすると のとき、 方針: tを分解してダブルカウントする を となる数とすると p成分の数
pが素数⇒ とはiを素因数分解した時の p成分の数
26
あるマトリックスを考える は となる最大の数 j列目の１の数は 個 i行目の１の数は 個 マトリックスの中にある１の数は同じ
27
補題３.６ を素数とし、 とすると のとき 方針: 前半は補題３.５より示されている よって後半の等式を示せばよい
28
で割り、切り捨て １からｍまでを足し合わせる 等比級数
29
n
30
定理３.４ を素数とすると が を割りきる必要十分条件は が と をp進数上で加算した時に起こる キャリーの数以下であることである 方針： となるようなa,b,cを評価していく となる
31
とする 補題３.６より
32
ところで… これをp進数の足し算で書き下すと
33
０か１！ 全ての和を取ると
34
となる！よって定理３.４は成立する 定理３.４ を素数とすると が を割りきる必要十分条件は が と をp進数上で加算した時に起こる キャリーの数以下であることである
35
Ex３.１３ を素数とすると、以下の１から３が成立 １. の中にpで割り切れないものが 個存在する ２. の全てがpの倍数に なっている必要十分条件は ３. の全てがpの倍数に なっていない必要十分条件は
36
１. の中にpで割り切れないものが 個丁度存在する 定理３.３より 全てのjで ならば割り切れない なお且つその時のみ割り切れない 各桁に 通りの数字の定め方がある
37
２. の全てがpの倍数に なっている必要十分条件は もし ならば より のとき のどれか一つが０⇒定理３.３より もし ならば のどこかの桁を-１したi なお且つそれは０でもｎでもない存在する
38
３. の全てがpの倍数に なっていない必要十分条件は もし ならば のどれも０にできない もし ならば ある桁 j がp-１以下 ⇒ が０
39
Ex ３.１４ 下の性質を持つ正の整数kを全て列挙せよ 性質：kに対してあるnが存在して が全てkで割り切れる kが１の時は自明、素数の時はEx３.１３(b)より が存在している。 kが素数でない時は？
40
もしkがある素数pで割れるなら そのkに対応するnはpでも条件を満たす。 ⇒ を考えるとこれもkで割れるはず なのにkがp以外の素因数を持つとおかしい ⇒少なくとも
41
かつ を考えると のp進数でのキャリーは１！！ なお且つこれはkによって割り切られる ⇒ つまりkは素数しかあり得ない！
42
定理３.７ 証明してみろよって書いてありますが、割と自明な気がしている・・・・
43
項を全て展開することを考える ↓ ある項は各クローズから １個変数を選んできて作られる n個
44
ある項 の数は？ を 個 を 個 を 個 並べた列の総数に等しい n個の場所に を 個 を 個 を 個 場所を取って埋めていく数に等しい
Similar presentations
