7 Calculating in Two Ways: Fubini’s Principle 朴大地

Warming Up 7.1. 単位正方形(タイル)を15×15正方形に並べる 辺の本数は? ① 水平な辺について 垂直な辺も同じ 全部で 2 5 click 15 3 16

Warming Up 7.1. 単位正方形(タイル)を15×15正方形に並べる 辺の本数は? ② 頂点の個数について 全部で 角 (次数 2) 外端 (次数 3) 内側 (次数 4) 全部で 15 5 click

Example 7.1. 15×15 タイル 15 × 15 タイルのふちに色を塗る 頂点 辺（頂点色から決まる） 赤 : or 青 : 赤赤⇒赤 : 青青⇒青 : 赤青⇒黄 : 5 click

Example 7.1. 15×15 タイル 15 × 15 タイルのふちに色を塗る 頂点 辺（頂点色から決まる） 赤 : or 青 : 赤赤⇒赤 : 青青⇒青 : 赤青⇒黄 : 5 click

Solution 方針 EX7.1 15×15のタイルのふちを色分けしました。 赤頂点は133個。うち角には2個、外端に32個。 黄辺は196本とする。青辺の数は? Solution 方針 赤辺の本数を とする 辺から見た赤頂点の出現の数 を、2通りの方法で数える が求められる (辺は全部で480本)

赤頂点の出現の数 ? ① EX7.1 15×15のタイルのふちを色分けしました。 赤頂点は133個。うち角には2個、外端に32個。 黄辺は196本とする。青辺の数は? 赤頂点の出現の数 ? ① 各辺から見て、両端の頂点が赤かどうか、重複も含めて観測された数 赤辺の本数　　とすれば 例

赤頂点の出現の数 ? ② EX7.1 15×15のタイルのふちを色分けしました。 赤頂点は133個。うち角には2個、外端に32個。 黄辺は196本とする。青辺の数は? 赤頂点の出現の数 ? ② 赤頂点から数える 角 (次数 2) 2個 外端 (次数 3) 32個 内側 (次数 4) 99個

赤頂点の出現の数 ? 結局 より 青辺は134本 EX7.1 15×15のタイルのふちを色分けしました。 赤頂点は133個。うち角には2個、外端に32個。 黄辺は196本とする。青辺の数は? 赤頂点の出現の数 ? 結局 より 青辺は134本

7. Calculating Two Ways 2つの集合 直積集合

Theorem 7.1. (Fubini’s Principle) 2つの集合 に対して、 は次を満たす。 2つの集合 に対して、 は次を満たす。 1

Theorem 7.1. (Fubini’s Principle) 2つの集合 に対して、 は次を満たす。 2つの集合 に対して、 は次を満たす。 1

Example 7.2. 例 ( 5, 3, 4, 2, 1 ) Ex 7.2. を から までの順列とする。 集合 に対して、次を証明せよ。 例 ( 5, 3, 4, 2, 1 ) 自分(k番目)より後ろにある、 自分より小さい数字の集合 自分(k番目)より手前にある、 自分より大きい数字の集合

Example 7.2. Solution 反転対を数える ( 5, 3, 4, 2, 1 ) Ex 7.2. を から までの順列とする。 集合 に対して、次を証明せよ。 Solution 反転対を数える ( 5, 3, 4, 2, 1 ) 5 3 4 2 1

Example 7.3. Mr. Fat’s class 12人の学生がいます。 毎週、学生は誰かとペアを組みます。(6ペア) 次のような2人が常に存在 その2人のどちらともペアを組んだことがあるという人が5人以上存在する または その2人のどちらともペアを組んだことがないという人が5人以上存在する

Example 7.3. Mr. Fat’s class ある2人が存在 s.t. 両方とペアを組んだこと がある5人が存在 または がない5人が存在 1 2 3 4 5 6 7 8 9 10 11 12 -

Example 7.3. Mr. Fat’s class ある2人が存在 s.t. 両方とペアを組んだこと がある5人が存在 または がない5人が存在 1週 （1, 5 ）（ 2, 8 ）（ 3 , 4 ） （6, 12）（ 7, 9 ）（10, 11） 1 2 3 4 5 6 7 8 9 10 11 12 - P

Example 7.3. Mr. Fat’s class ある2人が存在 s.t. 両方とペアを組んだこと がある5人が存在 または がない5人が存在 2週 （1, 3 ）（ 2, 8 ）（ 4 , 11） （5, 9 ）（ 6, 7 ）（10, 12） 1 2 3 4 5 6 7 8 9 10 11 12 - P

Example 7.3. Mr. Fat’s class ある2人が存在 s.t. 両方とペアを組んだこと がある5人が存在 または がない5人が存在 …週 （・, ・ ）（ ・, ・ ）（・ , ・ ） 1 2 3 4 5 6 7 8 9 10 11 12 - P

Example 7.3. Mr. Fat’s class ある2人が存在 s.t. 両方とペアを組んだこと がある5人が存在 または がない5人が存在 …週 （・, ・ ）（ ・, ・ ）（・ , ・ ） 1 2 3 4 5 6 7 8 9 10 11 12 - P

Example 7.3. Mr. Fat’s class ある2人が存在 s.t. 両方とペアを組んだこと がある5人が存在 または がない5人が存在 …週 （・, ・ ）（ ・, ・ ）（・ , ・ ） 1 2 3 4 5 6 7 8 9 10 11 12 - P

Solution 方針 EX7.3 12人の学生のうちある2人が存在。 s.t. 「 両方と組んだことがある5人が存在。 「 両方と組んだことがある5人が存在。 または 両方と組んだことがない5人が存在。」 Solution 方針 どちらか片方と　　　組んだことがある 1 2 3 4 5 -- 12 (1,2) - (1,3) (1,4) (1,5) --- (2,3) (2,4) (11,12) 「両方と組んだことがある、または両方と組んだことがない」ではない (1, 4) (2, 8) (3, 5) (-----) (-----) (-----)

① : 列 Claim EX7.3 12人の学生のうちある2人が存在。 s.t. 「 両方と組んだことがある5人が存在。 「 両方と組んだことがある5人が存在。 または 両方と組んだことがない5人が存在。」 ① : 列 Claim 今まで、d人と組んだことがある 列の個数 1 2 3 4 5 -- 12 (1,2) - (1,3) (1,4) (1,5) --- (2,3) (2,4) (11,12)

② : 行 背理法 EX7.3 12人の学生で、「常にある2人が存在。 s.t. 両方と組んだことがある5人が存在。 または 両方と組んだことがない5人が存在。」 ② : 行 背理法 問題の条件を否定 すべての行で1の 個数 となることがある 1 2 3 4 5 -- 12 (1,2) - (1,3) (1,4) (1,5) --- (2,3) (2,4) (11,12) 矛盾。問題の条件は正しい。証明終

Example 7.4. 集合 部分集合 要素数は 3 どの も含まないような集合で 要素数が 以上となる集合 が存在 共通する要素数は1以下 どの も含まないような集合で 　　　要素数が　　　　以上となる集合 が存在

で要素数が 以上のものが存在することを示せ。 EX7.4 集合 に対して、 である。 を含まない集合 で要素数が 以上のものが存在することを示せ。 集合 として要素数が最大のものを考える。 　あと1つでも要素を増やすと を含んでしまう。 として、 に選ばれなかった 個の要素を1個毎に に加えてみる WHY?

で要素数が 以上のものが存在することを示せ。 EX7.4 集合 に対して、 である。 を含まない集合 で要素数が 以上のものが存在することを示せ。 集合 として要素数が最大のものを考える。 　あと1つでも要素を増やすと を含んでしまう。 として、 に選ばれなかった 個の要素を1個毎に に加えてみる

Example 7.5. Full Sequence full sequence ― 次のような数字列 [ IMO 2002 Short-listed] full sequence ― 次のような数字列 が含まれるなら も含まれる の最初の出現が の最後の出現より手前 : 長さ の full sequence の数? ?

Solution（方針） EX7.5 full sequence : の最初の出現が の最後の 出現より手前に来る。数 ? を細かく分ける 出現より手前に来る。数 ? Solution（方針） を細かく分ける : 最大の数字 : の最初の出現位置 : の最後の出現位置 最初に出現する を消す これは の full sequence への全射

EX7.5 full sequence : の最初の出現が の最後の 出現より手前に来る。数 ? 出現より手前に来る。数 ? : 最大の数字 : の最初の出現位置 : の最後の出現位置 例.

最初の を消す EX7.5 full sequence : の最初の出現が の最後の 出現より手前に来る。数 ? が2個以上出現する場合 出現より手前に来る。数 ? 最初の を消す が2個以上出現する場合 が1個しか出現しない場合

EX7.5 full sequence : の最初の出現が の最後の 出現より手前に来る。数 ? 出現より手前に来る。数 ? は何回カウントされてる? 3回ずつ

EX7.5 full sequence : の最初の出現が の最後の 出現より手前に来る。数 ? 出現より手前に来る。数 ? は3回カウントされてる

EX7.5 full sequence : の最初の出現が の最後の 出現より手前に来る。数 ? 出現より手前に来る。数 ? は3回カウントされてる

EX7.5 full sequence : の最初の出現が の最後の 出現より手前に来る。数 ? 出現より手前に来る。数 ? ( - 3 * * 3 - - ) ( - 3 3 * 3 - - ) ( - 3 - 3 3 - - ) ( - 3 - - 3 - - ) ( - 3 * 3 - - ) ( - - 3 3 - - ) ( - - - 3 - - )

EX7.5 full sequence : の最初の出現が の最後の 出現より手前に来る。数 ? 出現より手前に来る。数 ? ( * * * * 4 * * ) ( 3 - - - 4 - - ) ( 3 3 - - 4 - - ) ： ( - - - 3 4 * 3 ) ( 3 - - - - - ) ( 3 3 - - - - ) ： ( - - - 3 * 3 )

EX7.5 full sequence : の最初の出現が の最後の 出現より手前に来る。数 ? 出現より手前に来る。数 ? 逆に ( - - 3 * 3 - ) ( 3 - - 3 * 3 - ) ( - 3 - 3 * 3 - ) ( - - 3 3 * 3 - ) ( - - 3 4 * 3 - ) ( - - 3 * 4 3 - ) ( - - 3 * 3 4 - ) ( - - 3 * 3 – 4 ) 7回カウントされる

EX7.5 full sequence : の最初の出現が の最後の 出現より手前に来る。数 ? 出現より手前に来る。数 ? 7回カウントされる

EX7.5 full sequence : の最初の出現が の最後の 出現より手前に来る。数 ? 一般に

Example Theorem 7.2. (Sperner) 集合 , ( ) の部分集合 , に対して、 次が成立する。 個より多く , の部分集合 , に対して、 次が成立する。 Example 個より多く , はつくれない。 たかだか70個

Proof Theorem 7.2. (Sperner) 集合 , ( ) の部分集合 , に対して、 次が成立する。 の部分集合 , に対して、 次が成立する。 Proof Maximal chain を考える 空集合から、 の要素をひとつづつ加えていったもの Maximal chain は 通り の要素の順列を考えればよい は Maximal chain に含まれるか?

Theorem 7.2. (Sperner) 集合 , ( ) の部分集合 , に対して、 次が成立する。 の部分集合 , に対して、 次が成立する。 Maximal Chain × ①列カウント を含む chain の数 - 1 個 全部で 個

Theorem 7.2. (Sperner) 集合 , ( ) の部分集合 , に対して、 次が成立する。 の部分集合 , に対して、 次が成立する。 Maximal Chain × ②行カウント 各行はたかだか1個 - 1 これは矛盾 全部で 個以下

Theorem 7.2. (Sperner) 集合 , ( ) の部分集合 , に対して、 次が成立する。 Theorem 3.2. (c)

Example 7.6. Circles 平面上の点集合 3点ずつを使い外接円を描く どの4点も同一円上には無い 点 を囲む円の数 このとき [ IMO 2000 Short-listed] 平面上の点集合 3点ずつを使い外接円を描く どの4点も同一円上には無い 点 を囲む円の数 このとき 「 が凸多角形をなす」 「 （ は点の配置に非依存）」 (境界線上は アウト) 必要十分条件

Solution （ある点が他の3点の円に囲まれているとは?） EX7.6 点集合 で円を描くとする。 各点を内部に含むような円の数の総和 。 「 が凸多角形」 ⇔ 「 」を示せ。 Solution　（ある点が他の3点の円に囲まれているとは?） ある4点を取ってくる [ABCD] (同一円上に無い) ①ABCDが凸の場合 ②ABCDが凹の場合 全ての4点の組み合わせをとると は2個プラス は1個プラス

Solution （ある点が他の3点の円に囲まれているとは?） EX7.6 点集合 で円を描くとする。 各点を内部に含むような円の数の総和 。 「 が凸多角形」 ⇔ 「 」を示せ。 Solution　（ある点が他の3点の円に囲まれているとは?） ある4点を取ってくる [ABCD] (同一円上に無い) ①ABCDが凸の場合 ②ABCDが凹の場合 「 が凸多角形である」 ⇔ 「②が起こらない」 ⇒ 「 」 「 が凸多角形でない」 ⇔ 「②が起こる」 ⇒ 「配置に依存」 は2個プラス は1個プラス

Example 7.7. Tile Translation 2次元平面をすべてタイリング 各タイル には実数 が書かれている タイルセットの得点 = の総和 2つのタイルセット どのように移動しても得点が正 -2 5 B を移動して得点を正にすることができるか?

EX7.7 タイルセット どのように移動しても得点が正。 の移動の中で 得点が正になるものが存在することを示せ。 Solution -2 5

EX7.7 タイルセット どのように移動しても得点が正。 の移動の中で 得点が正になるものが存在することを示せ。 Solution -2 5

EX7.7 タイルセット どのように移動しても得点が正。 の移動の中で 得点が正になるものが存在することを示せ。 Solution -2 5

EX7.7 タイルセット どのように移動しても得点が正。 の移動の中で 得点が正になるものが存在することを示せ。 Solution -2 5

EX7.7 タイルセット どのように移動しても得点が正。 の移動の中で 得点が正になるものが存在することを示せ。 Solution -2 5

EX7.7 タイルセット どのように移動しても得点が正。 の移動の中で 得点が正になるものが存在することを示せ。 Solution -2 5

EX7.7 タイルセット どのように移動しても得点が正。 の移動の中で 得点が正になるものが存在することを示せ。 Solution -2 5

EX7.7 タイルセット どのように移動しても得点が正。 の移動の中で 得点が正になるものが存在することを示せ。 Solution -2 5

EX7.7 タイルセット どのように移動しても得点が正。 の移動の中で 得点が正になるものが存在することを示せ。 Solution -2 5

EX7.7 タイルセット どのように移動しても得点が正。 の移動の中で 得点が正になるものが存在することを示せ。 Solution -2 5

EX7.7 タイルセット どのように移動しても得点が正。 の移動の中で 得点が正になるものが存在することを示せ。 Solution -2 5