counting_chap3-2

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

Download Report