A path to combinatorics 第３章後半(Ex3.8-最後) 京都大学情報学研究科 通信情報システム専攻 岩間・伊藤研究室 M１　西田　尚平

Ex ３.８ を証明して下さい 方針:再帰的（帰納的？）に示す とする は、すぐに確かめられる 任意のｎで が成立してほしい

公式B 項を分離

Ex ３.９ を証明して下さい 方針:これも帰納的に示す とする を示せばよい→差分が簡単に書ける

初項と末項を持ってきた 展開してくくりだす

ｍからi個、ｎから(k-i)個取ってくる Ex ３.１０ を証明して下さい Solution: ｍ個 ｎ個 　ｍからi個、ｎから(k-i)個取ってくる

Ex ３.１１ この４つの数が等差数列では無い事を証明して下さい Solution: とする もし等差数列なら になるはず！ ⇒方針はこれが矛盾することを示す

とすると… ｘの二次方程式！！ xの二次方程式がxに対して解を高々２つまでしか持たない⇒ｋとｋ＋１

全て解は求まったはず・・・ところが も解になりうる ⇒全ての解が求まったことに矛盾！！ ⇒最初に仮定した、等差数列というのがダメ

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

Ex ３.１２ ２３のバスケットボールチームが引き分け無しの 総当たり戦を行ったとする。 その結果表を見た時、３チーム部分集合{A,B,C}を 全て見てCyclic 3-Set となっているようなものをカウントして行く。 最大何個そのような部分集合ができうるか。 × × ○ ○ ○ ○ ○ × × がCyclic 3-set × × ○

方針： Cyclic 3-Setでは無いものの数を最小にするような 対戦結果を与えることでCyclic 3-Setの最大値を 求める そもそもCyclic 3-Setでは無いものには どのような条件があるのか？

A C B Cyclic 3-Setでは無い部分集合の必要十分条件は 部分集合のうちある１チームが他の２チームを 倒している場合である。 部分集合のうちある１チームが他の２チームに 敗北している場合である。

するとCyclic 3-Setでない部分集合の数Mは × ○ あるチームiの 勝利した数を 敗北した数を　 と置く ○ ×× … … ○× ○ × ○ するとCyclic 3-Setでない部分集合の数Mは

２乗平均平方根－相加平均の関係 ２乗平均平方根－相加平均の関係 ２乗平均平方根－相加相乗平均－ハーモニック平均の関係

より 等式は ⇒全てのチームの勝ちと負けが等しい 全体から引き算をして 組が最大！ でもそもそもそんな対戦表作れんの？

できます チーム i は以下のチームに勝ったという対戦表を作る チーム たとえばチーム５なら６から１６に勝つ

とかいろいろ書いてきましたが…

nのp進数表現 関数のmodの定義 全ての　に対して　　　　　 が　で割り切れる ⇒ が を割りきり、 はそのような数の中で最大という記号

定理３.３ を素数として　を任意の正の整数とする と書ける時、下の数式が成り立つ。 方針： は を展開した時の の係数！！

定理３.２(ｋ)より　 　　　 はpで割り切れるので これを繰り返し適用して を で分解して記述してみると…

の係数 全てのｘで成立するためには でなくてはならない

定理３.４ を素数とすると が を割りきる必要十分条件は が と をp進数上で加算した時に起こる キャリーの数以下であることである キャリーの数ってなんだ？ １０進数上で２！ 補題３.６を使用して証明する（補題３.５を使って補題３.６を証明）

補題３.５ を素数とすると のとき、 方針: tを分解してダブルカウントする を となる数とすると p成分の数 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個の場所に を 個 を 個 を 個 場所を取って埋めていく数に等しい