counting_chap7_1

7
Calculating in Two Ways:
Fubini’s Principle
朴大地
Warming Up 7.1.
• 単位正方形(タイル)を15×15正方形に並べる
• 辺の本数は? ①
– 水平な辺について
16 £ 15 = 240
– 垂直な辺も同じ
– 全部で
240 £ 2 = 480
15
1
2
15
3
16
Warming Up 7.1.
• 単位正方形(タイル)を15×15正方形に並べる
• 辺の本数は? ②
– 頂点の個数について
• 角 (次数 2)
4
• 外端 (次数 3) 14 £ 4 = 56
• 内側 (次数 4) 14 £ 14 = 196
– 全部で
4 ¢2 + 56 ¢3 + 196 ¢4 = 960
960=2 = 480
15
Example 7.1. 15×15 タイル
• 15 × 15 タイルのふちに色を塗る
• 頂点
–赤:
or 青 :
• 辺（頂点色から決まる）
– 赤赤⇒赤 :
– 青青⇒青 :
– 赤青⇒黄 :
Example 7.1. 15×15 タイル
• 15 × 15 タイルのふちに色を塗る
• 頂点
–赤:
or 青 :
• 辺（頂点色から決まる）
– 赤赤⇒赤 :
– 青青⇒青 :
– 赤青⇒黄 :
EX7.1 15×15のタイルのふちを色分けしました。
赤頂点は133個。うち角には2個、外端に32個。
黄辺は196本とする。青辺の数は?
• Solution
• 方針
– 赤辺の本数を r とする
– 辺から見た赤頂点の出現の
数 jSj を、2通りの方法で数
える
– r が求められる
(辺は全部で480本)
EX7.1 15×15のタイルのふちを色分けしました。
赤頂点は133個。うち角には2個、外端に32個。
黄辺は196本とする。青辺の数は?
• 赤頂点の出現の数 jSj ? ①
– 各辺から見て、両端の頂点が赤かどうか、
重複も含めて観測された数
jSj = (
) + 2£ (
– 赤辺の本数 r とすれば
jSj = 196 + 2r
)
例
jSj = 11
EX7.1 15×15のタイルのふちを色分けしました。
赤頂点は133個。うち角には2個、外端に32個。
黄辺は196本とする。青辺の数は?
• 赤頂点の出現の数 jSj ? ②
– 赤頂点から数える
• 角 (次数 2) 2個
• 外端 (次数 3) 32個
• 内側 (次数 4) 99個
jSj =
=
2 ¢2 + 32 ¢3 + 99 ¢4
496
EX7.1 15×15のタイルのふちを色分けしました。
赤頂点は133個。うち角には2個、外端に32個。
黄辺は196本とする。青辺の数は?
• 赤頂点の出現の数 jSj ?
• 結局
jSj = 196 + 2r
jSj = 2 ¢2 + 32 ¢3 + 99 ¢4
=
496
• より r = 150
• 青辺は134本
(480 ¡ 196 ¡ 150 = 134)
7. Calculating Two Ways
• 2つの集合
A = f a1; a2; ¢¢¢; am g
B = f b1; b2; ¢¢¢; bn g
• 直積集合 A £ B
b1
b2
a1 (a1; b1) (a2; b1)
a2 (a1; b2) (a2; b2)
..
..
..
.
.
.
an (a1; bn )
bn
¢¢¢
¢¢¢
¢¢¢
(am ; b1)
¢¢¢
(am ; bn )
..
.
Theorem 7.1. (Fubini’s Principle)
2つの集合 A; B に対して、 S µ A £ B は次を満たす。
Xn
jSj =
Xm
jS(¤; bj )j =
j=1
jS(ai ; ¤)j
i= 1
• S µ A £ B S(¤; bj ) = f (a; bj ) 2 Sg
jS(¤; b )j jS(¤; b )j jS(¤; b )j jS(¤; b )j jS(¤; b )j
jSj = 10
= 3
= 2
= 3
= 1
= 1
b1 b2 b3
b4 b5
1
0
0
0
0
a1
0
1
1
0
0
a2
1
1
1
1
1
a3
1
0
1
0
0
a4
1
2
3
4
5
Theorem 7.1. (Fubini’s Principle)
2つの集合 A; B に対して、 S µ A £ B は次を満たす。
Xn
jSj =
Xm
jS(¤; bj )j =
j=1
jS(ai ; ¤)j
i= 1
• S µ A £ B S(ai ; ¤) = f (ai ; b) 2 Sg
jSj = 10
b1 b2 b3
1
0
0
jS(a1; ¤)j = 1 a1
0
1
1
jS(a2; ¤)j = 2 a2
1
1
1
jS(a3; ¤)j = 5 a3
1
0
1
jS(a4; ¤)j = 2 a4
b4
b5
0
0
0
0
1
1
0
0
Ex 7.2. a1; a2; ¢¢¢; an を 1 から n までの順列とする。
Example
7.2.
集合 Fk = f ai jai < ak ; i > kg
Gk = f ai jai > ak ; i < kg
(1 · k · n)
に対して、次を証明せよ。
Xn
Xn
jFk j =
k= 1
jGk j
k= 1
• 例 ( 5, 3, 4, 2, 1 )
自分(k番目)より後ろにある、
自分より小さい数字の集合
F1 =
F2 =
F3 =
F4 =
F5 =
f 3; 4; 2; 1g
f 2; 1g
f 2; 1g
f 1g
fg
自分(k番目)より手前にある、
自分より大きい数字の集合
G1 =
G2 =
G3 =
G4 =
G5 =
fg
f 5g
f 5g
f 5; 3; 4g
f 5; 3; 4; 2g
Ex 7.2. a1; a2; ¢¢¢; an を 1 から n までの順列とする。
Example
7.2.
集合 Fk = f ai jai < ak ; i > kg
Gk = f ai jai > ak ; i < kg
(1 · k · n)
に対して、次を証明せよ。
Xn
Xn
jFk j =
k= 1
• Solution
jGk j
k= 1
反転対を数える
( 5, 3, 4, 2, 1 )
S = f (ai ; aj )jai < aj ; i > j g
5
3
4
2
1
S(¤; aj )
5
0
0
0
0
0
= f (ai ; aj )jai < aj ; i > j g = Fj
S(ai ; ¤)
3
1
0
0
0
0
4
1
0
0
0
0
= f (ai ; aj )jaj > ai ; j < i g = Gi
2
1
1
1
0
0
1
1
1
1
1
0
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
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
1
-
2
P
-
P
3
-
P
4
P
-
5
P
-
6
-
7
8
P
P
P
-
9
P
-
10
-
P
11
P
-
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
1
-
2
3
P
-
P
4
5
P
P
-
P
P
-
P
P
-
P
6
-
P
7
P
-
8
P
P
P
10
12
P
-
9
11
P
P
P
-
P
P
-
P
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
1
-
2
3
P
P P
P
4
5
P
6
P
P P
-
P
P
-
P
8
P
12
P
-
P
P
-
P
P
-
9
11
P
-
7
10
P
P
P
P
P
P
P
P
-
P
P
P
-
P
P
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
1
-
P P
2
P
-
3
P
4
P
6
P
-
P
8
P
11
12 P
P
P
P
P
P
-
P
P P
P P
-
P
P
-
P P
P
P
P
-
P
P
P
P
P
P P
-
P
10 P
P
P P
P
7
9
P
P P
5
P P
P
P
P
P
P
P
-
P P
-
P
P
P
P
-
P
P
P
-
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
1
-
P P
2
P
-
3
P
4
P P
5
P
6
P
P P
8
P
P P
P P
P
-
P
P P
P P
-
P
P
P
-
P
12 P
P
P
P
P P
P
P
P
-
P P P
10 P
P
P
P
P P
P
P
P
P
11
P
P
P
7
9
P P
P
P
P
P
P
P
-
P
P
P P P
-
P
P
P
P
-
P
P
P
-
P
P
EX7.3 12人の学生のうちある2人が存在。 s.t.
「両方と組んだことがある5人が存在。
または両方と組んだことがない5人が存在。」
• Solution
• 方針
– S : (¤; ¤) £ ¤
S
12 C2
– どちらか片方と
組んだことがある
「両方と組んだことがある、または
両方と組んだことがない」ではない
(1, 4) (2, 8) (3, 5)
(-----) (-----) (-----)
1
2
3
4
5
--
12
(1,2)
-
-
0
1
0
0
(1,3)
-
0
-
1
1
0
(1,4)
-
0
0
-
0
0
(1,5)
-
0
0
1
0
0
---
-
(2,3)
0
-
-
1
0
(2,4)
1
-
-
0
0
0
0
0
0
-
--(11,12)
0
EX7.3 12人の学生のうちある2人が存在。 s.t.
「両方と組んだことがある5人が存在。
または両方と組んだことがない5人が存在。」
• ①:列
• Claim jSj · 360
– 今まで、d人と組んだ
ことがある
– 列の個数
d(11 ¡ d) · 30
jSj · 30 ¢12 = 360
S
1
2
3
4
5
--
12
(1,2)
-
-
0
1
0
0
(1,3)
-
0
-
1
1
0
(1,4)
-
0
0
-
0
0
(1,5)
-
0
0
1
0
0
---
-
(2,3)
0
-
-
1
0
(2,4)
1
-
-
0
0
0
0
0
0
-
--(11,12)
0
EX7.3 12人の学生で、「常にある2人が存在。 s.t.
両方と組んだことがある5人が存在。
または両方と組んだことがない5人が存在。」
• ②:行
• 背理法
S
– 問題の条件を否定
1
2
3
4
5
(1,2)
-
-
0
1
0
0
(1,3)
-
0
-
1
1
0
(1,4)
-
0
0
-
0
0
(1,5)
-
0
0
1
0
0
-
1
0
-
0
0
0
0
-
– すべての行で1の
個数 ¸ 6 となることがある
---
-
(2,3)
0
-
jSj ¸ 6 ¢12C2 = 396
(2,4)
1
-
0
0
jSj · 30 ¢12 = 360
矛盾。問題の条件は正しい。証明終
--
12
--(11,12)
0
Example 7.4.
• 集合 X = f x 1; x 2; ¢¢¢; x n g
• 部分集合 A 1; A 2; ¢¢¢; A m ½ X
jA j j = 3 (1 · j · m)
– 要素数は 3
– 共通する要素数は1以下
jA i \ A j j · 1 (for all i 6
= j)
• どの A j も含まないような集合で
p
要素数が b 2nc 以上となる集合 A が存在
X = f 1; 2; 3; 4; 5; 6; 7; 8g
A 1 = f 1; 2; 3g A 4 = f 2; 4; 6g
A 2 = f 3; 6; 8g A 5 = f 2; 5; 8g
A 3 = f 5; 6; 7g A 6 = f 3; 4; 5g
A = f 1; 2; 4; 5; 7g
EX7.4 集合 A 1; A 2; ¢¢¢; A m ½ X に対して、jA j j = 3
jA i \ A j j · 1 pである。 A j を含まない集合 A ½ X
で要素数が b 2nc以上のものが存在することを示せ。
• 集合 A として要素数が最大のものを考える。
– あと1つでも要素を増やすと A j を含んでしまう。
– k = jAj として、 A に選ばれなかった n ¡ k 個の要素を
1個毎に A に加えてみる
n¡ k·
k C2
k C2
WHY?
X = f 1; 2; 3; 4; 5; 6; 7; 8g
A 1 = f 1; 2; 3g A 4 = f 2; 4; 6g
A 2 = f 3; 6; 8g A 5 = f 2; 5; 8g
A 3 = f 5; 6; 7g A 6 = f 3; 4; 5g
3:
6:
A = f 1; 2; 4; 5; 7g 8 :
A1
A6
A4
A3
A5
=
=
=
=
=
f 1; 2; 3g
f 3; 4; 5g
f 2; 4; 6g
f 5; 6; 7g
f 2; 5; 8g
EX7.4 集合 A 1; A 2; ¢¢¢; A m ½ X に対して、jA j j = 3
jA i \ A j j · 1 pである。 A j を含まない集合 A ½ X
で要素数が b 2nc以上のものが存在することを示せ。
• 集合 A として要素数が最大のものを考える。
– あと1つでも要素を増やすと A j を含んでしまう。
– k = jAj として、 A に選ばれなかった n ¡ k 個の要素を
1個毎に A に加えてみる
n¡ k·
2
C
=
(k
¡ k)=2
k 2
X = f 1; 2; 3; 4; 5; 6; 7; 8g
A 1 = f 1; 2; 3g A 4 = f 2; 4; 6g
A 2 = f 3; 6; 8g A 5 = f 2; 5; 8g
A 3 = f 5; 6; 7g A 6 = f 3; 4; 5g
A = f 1; 2; 4; 5; 7g
k 2 + k ¸ 2n
p
k ¸ b 2nc
Example 7.5. Full Sequence
[ IMO 2002 Short-listed]
• full sequence ― 次のような数字列
– k が含まれるなら k ¡ 1 も含まれる
– k ¡ 1 の最初の出現が k の最後の出現より手前
(3; 1; 2; 3) (1; 1; 1)
(1; 1; 3) (4; 3; 1; 2; 3; 5)
• f (n) : 長さ n の full sequence の数?
f (1) = 1
(1)
f (2) = 2
f (3) = 6
(1; 1) (1; 2)
(1; 1; 1) (2; 1; 2) (1; 1; 2)
(1; 2; 3) (1; 2; 1) (1; 2; 2)
f (n) = n! ?
EX7.5 full sequence : k ¡ 1 の最初の出現が k の最後の
出現より手前に来る。数 f (n) ?
• Solution（方針）
– f (n) を細かく分ける
f (n; k; a; b)
• k : 最大の数字
• a : k の最初の出現位置
• b : k の最後の出現位置
– 最初に出現する k を消す
• これは n ¡ 1 の full sequence への全射
• f (n) = n ¢f (n ¡ 1)
EX7.5 full sequence : k ¡ 1 の最初の出現が k の最後の
出現より手前に来る。数 f (n) ?
• f (n; k; a; b)
X
f (n) =
• k : 最大の数字
• a : k の最初の出現位置
• b : k の最後の出現位置
– 例. f (4; 2; 1; 4) = 3
f (3; 1; 1; 3)
f (3; 2; 3; 3)
f (3; 2; 2; 2)
f (3; 2; 2; 3)
f (3; 2; 1; 3)
f (3; 3; 3; 3)
(1; 1; 1)
(1; 1; 2)
(1; 2; 1)
(1; 2; 2)
(2; 1; 2)
(1; 2; 3)
f (n; k; a; b)
k;a;b
(2; 1; 1; 2) (2; 1; 2; 2) (2; 2; 1; 2)
EX7.5 full sequence : k ¡ 1 の最初の出現が k の最後の
出現より手前に来る。数 f (n) ?
• 最初の k を消す
– k が2個以上出現する場合
X
f (n; k; a; b) =
f (n ¡ 1; k; x; b¡ 1)
– k が1個しか出現しない場合
X
f (n; k; a; b) =
f (3; 1; 1; 3)
f (3; 2; 3; 3)
f (3; 2; 2; 2)
f (3; 2; 2; 3)
f (3; 2; 1; 3)
f (3; 3; 3; 3)
(1; 1; 1)
(1; 1; 2)
(1; 2; 1)
(1; 2; 2)
(2; 1; 2)
(1; 2; 3)
f (n ¡ 1; k ¡ 1; x; y)
(1; 1)
(1; 1)
(1; 1)
(1; 2)
(1; 2)
(1; 2)
f (2; 1; 1; 2)
f (2; 1; 1; 2)
f (2; 1; 1; 2)
f (2; 2; 2; 2)
f (2; 2; 2; 2)
f (2; 2; 2; 2)
EX7.5 full sequence : k ¡ 1 の最初の出現が k の最後の
出現より手前に来る。数 f (n) ?
•
X
f (n) =
f (n; k; a; b)
k;a· b
X
X
=
f (n ¡ 1; k; x; b¡ 1)
k;a< b 1· x · b¡ 1
X
X
+
f (n ¡ 1; k ¡ 1; x; y)
k;a= b x· a¡ 1;x· y
f (3; 1; 1; 3)
f (3; 2; 3; 3)
f (3; 2; 2; 2)
f (3; 2; 2; 3)
f (3; 2; 1; 3)
f (3; 3; 3; 3)
(1; 1; 1)
(1; 1; 2)
(1; 2; 1)
(1; 2; 2)
(2; 1; 2)
(1; 2; 3)
(1; 1)
(1; 1)
(1; 1)
(1; 2)
(1; 2)
(1; 2)
f (n ¡ 1; ¤; ¤; ¤)
は何回カウントされてる?
f (2; 1; 1; 2)
f (2; 1; 1; 2)
f (2; 1; 1; 2)
f (2; 2; 2; 2)
f (2; 2; 2; 2)
f (2; 2; 2; 2)
3回ずつ
EX7.5 full sequence : k ¡ 1 の最初の出現が k の最後の
出現より手前に来る。数 f (n) ?
•
X
f (n) =
f (n; k; a; b)
k;a· b
X
X
=
f (n ¡ 1; k; x; b¡ 1)
k;a< b 1· x · b¡ 1
X
X
+
f (n ¡ 1; k ¡ 1; x; y)
k;a= b x· a¡ 1;x· y
f (3; 1; 1; 3)
f (3; 2; 3; 3)
f (3; 2; 2; 2)
(1; 1; 1)
(1; 1; 2)
(1; 2; 1)
(1; 1)
(1; 1)
(1; 1)
f (2; 1; 1; 2)
f (2; 1; 1; 2)
f (2; 1; 1; 2)
f (2; 1; 1; 2)
は3回カウントされてる
EX7.5 full sequence : k ¡ 1 の最初の出現が k の最後の
出現より手前に来る。数 f (n) ?
•
X
f (n) =
f (n; k; a; b)
k;a· b
X
X
=
f (n ¡ 1; k; x; b¡ 1)
k;a< b 1· x · b¡ 1
X
X
+
f (n ¡ 1; k ¡ 1; x; y)
k;a= b x· a¡ 1;x· y
f (2; 2; 2; 2)
は3回カウントされてる
f (3; 2; 2; 3)
f (3; 2; 1; 3)
f (3; 3; 3; 3)
(1; 2; 2)
(2; 1; 2)
(1; 2; 3)
(1; 2)
(1; 2)
(1; 2)
f (2; 2; 2; 2)
f (2; 2; 2; 2)
f (2; 2; 2; 2)
EX7.5 full sequence : k ¡ 1 の最初の出現が k の最後の
出現より手前に来る。数 f (n) ?
f (7) =
f (7; 1; 1; 1) =
f (7; 1; 1; 2) =
..
.
f (7; 3; 2; 5) =
..
.
(-3**3--)
(-33*3--)
(-3-33--)
(-3--3--)
f (6; 3; 2; 4)
f (6; 3; 3; 4)
f (6; 3; 4; 4)
(-3*3--)
(--33--)
(---3--)
EX7.5 full sequence : k ¡ 1 の最初の出現が k の最後の
出現より手前に来る。数 f (n) ?
f (7) =
f (7; 1; 1; 1) =
f (7; 1; 1; 2) =
..
.
f (7; 4; 5; 5) =
..
.
(****4**)
(3---4--)
(33--4--)
：
(---34*3)
f (6; 3; 1; 1) = 0
f (6; 3; 1; 2) = 0
..
.
f (6; 3; 4; 6)
(3-----)
(33----)
：
(---3*3)
EX7.5 full sequence : k ¡ 1 の最初の出現が k の最後の
出現より手前に来る。数 f (n) ?
f (7) =
f (7; 1; 1; 1) =
f (7; 1; 1; 2) =
..
.
f
f
f
f
f
f
f
(7; 3; 1; 6)
(7; 3; 2; 6)
(7; 3; 3; 6)
(7; 4; 4; 4)
(7; 4; 5; 5)
(7; 4; 6; 6)
(7; 4; 7; 7)
=
=
=
=
=
=
=
7回カウントされる
逆に
f (6; 3; 3; 5)
(--3*3-)
(3(-3
(-(-(-(-(--
-3*3
-3*3
33*3
34*3
3*43
3*34
3*3–
4
)
)
)
)
)
)
)
EX7.5 full sequence : k ¡ 1 の最初の出現が k の最後の
出現より手前に来る。数 f (n) ?
f (7) =
f (7; 1; 1; 1)
f (7; 1; 1; 2)
..
.
=
7f (6; 1; 1; 1)
7f (6; 1; 1; 2)
..
.
7f (6; 6; 6; 6)
f (7; 7; 7; 7)
7回カウントされる
= 7f (6)
EX7.5 full sequence : k ¡ 1 の最初の出現が k の最後の
出現より手前に来る。数 f (n) ?
• 一般に
– f (n) = n ¢f (n ¡ 1)
= n(n ¡ 1)(n ¡ 2) ¢¢¢1
= n!
Theorem 7.2. (Sperner) 集合 S , ( jSj = n )
S の部分集合 S1; S2; ¢¢¢; Sm ½ S , Si µ Sj に対して、
m · n Cb n2 c
次が成立する。
• Example
S = f 1; 2; 3; 4; 5; 6; 7; 8g
– 8C4 = 70 個より多く S1; S2; ¢¢¢; Sm ½ S , Si µ Sj
はつくれない。
S1 = f 1; 2; 3; 4g
– たかだか70個
S2 = f 1; 2; 3; 5g
S3 = f 1; 2; 3; 6g
..
.
S70 = f 5; 6; 7; 8g
Theorem 7.2. (Sperner) 集合 S , ( jSj = n )
S の部分集合 S1; S2; ¢¢¢; Sm ½ S , Si µ Sj に対して、
m · n Cb n2 c
次が成立する。
• Proof
– Maximal chain を考える
; 6
= T1 ½ T2 ½ ¢¢¢½ Tn = S
• 空集合から、 S の要素をひとつづつ加えていったもの
• Maximal chain は n! 通り
• S の要素の順列を考えればよい
– Si は Maximal chain に含まれるか?
; 6
= T1 ½ T2 ½ ¢¢¢½ Si ½ ¢¢¢½ Tn = S
Theorem 7.2. (Sperner) 集合 S , ( jSj = n )
S の部分集合 S1; S2; ¢¢¢; Sm ½ S , Si µ Sj に対して、
m · n Cb n2 c
次が成立する。
• ; 6
= T1 ½ T2 ½ ¢¢¢½ Tn = S
– Maximal Chain × Si
• ①列カウント
–
Si を含む chain の数
T1 ½ ¢¢¢½ Si ½ Tki + 1 ½ ¢¢¢½ Tn
(ki = jSi j)
ki !(n ¡ ki )! 個
Xm
ki !(n ¡ ki )! 個
全部で
i= 1
S1 S2 S3
-
Sm
T1 ½ T2 ½ ¢¢¢½ Tn 0
0
0
-
0
U1 ½ U2 ½ ¢¢¢½ Un 0
1
0
-
0
V1 ½ V2 ½ ¢¢¢½ Vn
0
0
0
-
0
-
-
-
-
-
-
-
-
-
-
Z 1 ½ Z 2 ½ ¢¢¢½ Z n 0
0
0
-
0
Theorem 7.2. (Sperner) 集合 S , ( jSj = n )
S の部分集合 S1; S2; ¢¢¢; Sm ½ S , Si µ Sj に対して、
m · n Cb n2 c
次が成立する。
• ; 6
= T1 ½ T2 ½ ¢¢¢½ Tn = S
– Maximal Chain × Si
• ②行カウント
– 各行はたかだか1個
T1 ½ ¢¢¢½ Si ½ ¢¢¢½ Sj ½ ¢¢¢Tn
これは矛盾
全部で
n! 個以下
Xm
ki !(n ¡ ki )! · n!
i= 1
S1 S2 S3
-
Sm
T1 ½ T2 ½ ¢¢¢½ Tn 0
0
0
-
0
U1 ½ U2 ½ ¢¢¢½ Un 0
1
0
-
0
V1 ½ V2 ½ ¢¢¢½ Vn
0
0
0
-
0
-
-
-
-
-
-
-
-
-
-
Z 1 ½ Z 2 ½ ¢¢¢½ Z n 0
0
0
-
0
Theorem 7.2. (Sperner) 集合 S , ( jSj = n )
S の部分集合 S1; S2; ¢¢¢; Sm ½ S , Si µ Sj に対して、
m · n Cb n2 c
次が成立する。
• ; 6
= T1 ½ T2 ½ ¢¢¢½ Tn = S
•
Xm
ki !(n ¡ ki )! · n!
i= 1
Xm
i= 1
1
· 1
n Ck i
1
m
·
n Cb n2 c
Xm
i= 1
1
· 1
n Ck i
Theorem 3.2. (c)
n Ck i · n Cb n2 c
Example 7.6. Circles
[ IMO 2000 Short-listed]
• 平面上の点集合 S = f P1; P2; ¢¢¢; Pn g
– 3点ずつを使い外接円を描く
– どの4点も同一円上には無い
– 点 Pi を囲む円の数 ai (境界線上は
アウト)
• m(S) = a1 + a2 + ¢¢¢+ an
P1
– このとき
a1 = 2
「 P1; P2; ¢¢¢; Pn が凸多角形をなす」
「 m(S) = f (n) （ m(S) は点の配置に非依存）」
(f (n) = 2n C4)
必要十分条件
EX7.6 点集合 S = f P1; P2; ¢¢¢; Pn g で円を描くとする。
各点を内部に含むような円の数の総和 m(S) 。
「 S が凸多角形」 ⇔ 「m(S) = f (n) 」を示せ。
• Solution
（ある点が他の3点の円に囲まれているとは?）
• ある4点を取ってくる [ABCD] (同一円上に無い)
C
– ①ABCDが凸の場合
m(S) は2個プラス
D
A
A
B
– ②ABCDが凹の場合
m(S) は1個プラス
A
m(S) = 2 ¢°1 + °2
D
D
B
B
• 全ての4点の組み合わせをとると
C
C
EX7.6 点集合 S = f P1; P2; ¢¢¢; Pn g で円を描くとする。
各点を内部に含むような円の数の総和 m(S) 。
「 S が凸多角形」 ⇔ 「m(S) = f (n) 」を示せ。
• Solution
（ある点が他の3点の円に囲まれているとは?）
• ある4点を取ってくる [ABCD] (同一円上に無い)
– ①ABCDが凸の場合
•「 S が凸多角形である」
⇔ 「②が起こらない」
m(S) は2個プラス
⇒ 「 m(S) = 2n C4 」
– ②ABCDが凹の場合
•「 S が凸多角形でない」
m(S) は1個プラス ⇔ 「②が起こる」
• m(S) = 2 ¢°1 + °2
⇒ 「配置に依存」
Example 7.7. Tile Translation
• 2次元平面をすべてタイリング
– 各タイル (x; y) には実数 r (x; y) が書かれている
– タイルセットの得点 = r (x; y) の総和
• 2つのタイルセット
-2
5
-2
5
-2
5
-2
5
– A = f (a1; b1); ¢¢¢; (an ; bn )g
5
-2
5
-2
5
-2
5
-2
どのように移動しても得点が正
-2
5
-2
5
-2
5
-2
5
5
-2
5
-2
5
-2
5
-2
-2
5
-2
5
-2
5
-2
5
5
-2
5
-2
5
-2
5
-2
-2
5
-2
5
-2
5
-2
5
5
-2
5
-2
5
-2
5
-2
– B = f (u1; v1); ¢¢¢; (um ; vm )g
B を移動して得点を正
にすることができるか?
EX7.7 タイルセット A = f (a1; b1); ¢¢¢; (an ; bn )g
どのように移動しても得点が正。
B = f (u1; v1); ¢¢¢; (um ; vm )g の移動の中で
得点が正になるものが存在することを示せ。
• Solution
– s=
Xm Xn
r (ai + uj ; bi + vj )
j = 1 i= 1
Xn Xm
=
r (ai + uj ; bi + vj )
i= 1 j = 1
-2
5
-2
5
-2
5
-2
5
5
-2
5
-2
5
-2
5
-2
-2
5
-2
5
-2
5
-2
5
5
-2
5
-2
5
-2
5
-2
-2
5
-2
5
-2
5
-2
5
5
-2
5
-2
5
-2
5
-2
-2
5
-2
5
-2
5
-2
5
5
-2
5
-2
5
-2
5
-2
EX7.7 タイルセット A = f (a1; b1); ¢¢¢; (an ; bn )g
どのように移動しても得点が正。
B = f (u1; v1); ¢¢¢; (um ; vm )g の移動の中で
得点が正になるものが存在することを示せ。
• Solution
– s=
Xm Xn
r (ai + uj ; bi + vj )
j = 1 i= 1
Xn Xm
=
r (ai + uj ; bi + vj )
i= 1 j = 1
-2
5
-2
5
-2
5
-2
5
5
-2
5
-2
5
-2
5
-2
-2
5
-2
5
-2
5
-2
5
5
-2
5
-2
5
-2
5
-2
-2
5
-2
5
-2
5
-2
5
5
-2
5
-2
5
-2
5
-2
-2
5
-2
5
-2
5
-2
5
5
-2
5
-2
5
-2
5
-2
EX7.7 タイルセット A = f (a1; b1); ¢¢¢; (an ; bn )g
どのように移動しても得点が正。
B = f (u1; v1); ¢¢¢; (um ; vm )g の移動の中で
得点が正になるものが存在することを示せ。
• Solution
– s=
Xm Xn
r (ai + uj ; bi + vj )
j = 1 i= 1
Xn Xm
=
r (ai + uj ; bi + vj )
i= 1 j = 1
-2
5
-2
5
-2
5
-2
5
5
-2
5
-2
5
-2
5
-2
-2
5
-2
5
-2
5
-2
5
5
-2
5
-2
5
-2
5
-2
-2
5
-2
5
-2
5
-2
5
5
-2
5
-2
5
-2
5
-2
-2
5
-2
5
-2
5
-2
5
5
-2
5
-2
5
-2
5
-2
EX7.7 タイルセット A = f (a1; b1); ¢¢¢; (an ; bn )g
どのように移動しても得点が正。
B = f (u1; v1); ¢¢¢; (um ; vm )g の移動の中で
得点が正になるものが存在することを示せ。
• Solution
– s=
Xm Xn
r (ai + uj ; bi + vj )
j = 1 i= 1
Xn Xm
=
r (ai + uj ; bi + vj )
i= 1 j = 1
-2
5
-2
5
-2
5
-2
5
5
-2
5
-2
5
-2
5
-2
-2
5
-2
5
-2
5
-2
5
5
-2
5
-2
5
-2
5
-2
-2
5
-2
5
-2
5
-2
5
5
-2
5
-2
5
-2
5
-2
-2
5
-2
5
-2
5
-2
5
5
-2
5
-2
5
-2
5
-2
EX7.7 タイルセット A = f (a1; b1); ¢¢¢; (an ; bn )g
どのように移動しても得点が正。
B = f (u1; v1); ¢¢¢; (um ; vm )g の移動の中で
得点が正になるものが存在することを示せ。
• Solution
– s=
Xm Xn
r (ai + uj ; bi + vj )
j = 1 i= 1
Xn Xm
=
r (ai + uj ; bi + vj )
i= 1 j = 1
-2
5
-2
5
-2
5
-2
5
5
-2
5
-2
5
-2
5
-2
-2
5
-2
5
-2
5
-2
5
5
-2
5
-2
5
-2
5
-2
-2
5
-2
5
-2
5
-2
5
5
-2
5
-2
5
-2
5
-2
-2
5
-2
5
-2
5
-2
5
5
-2
5
-2
5
-2
5
-2
EX7.7 タイルセット A = f (a1; b1); ¢¢¢; (an ; bn )g
どのように移動しても得点が正。
B = f (u1; v1); ¢¢¢; (um ; vm )g の移動の中で
得点が正になるものが存在することを示せ。
• Solution
– s=
Xm Xn
r (ai + uj ; bi + vj ) > 0
j = 1 i= 1
Xn Xm
=
r (ai + uj ; bi + vj )
i= 1 j = 1
-2
5
-2
5
-2
5
-2
5
5
-2
5
-2
5
-2
5
-2
-2
5
-2
5
-2
5
-2
5
5
-2
5
-2
5
-2
5
-2
-2
5
-2
5
-2
5
-2
5
5
-2
5
-2
5
-2
5
-2
-2
5
-2
5
-2
5
-2
5
5
-2
5
-2
5
-2
5
-2
EX7.7 タイルセット A = f (a1; b1); ¢¢¢; (an ; bn )g
どのように移動しても得点が正。
B = f (u1; v1); ¢¢¢; (um ; vm )g の移動の中で
得点が正になるものが存在することを示せ。
• Solution
– s=
Xm Xn
r (ai + uj ; bi + vj ) > 0
j = 1 i= 1
Xn Xm
=
i= 1 j = 1
r (ai + uj ; bi + vj ) > 0
-2
5
-2
5
-2
5
-2
5
5
-2
5
-2
5
-2
5
-2
-2
5
-2
5
-2
5
-2
5
5
-2
5
-2
5
-2
5
-2
-2
5
-2
5
-2
5
-2
5
5
-2
5
-2
5
-2
5
-2
-2
5
-2
5
-2
5
-2
5
5
-2
5
-2
5
-2
5
-2
EX7.7 タイルセット A = f (a1; b1); ¢¢¢; (an ; bn )g
どのように移動しても得点が正。
B = f (u1; v1); ¢¢¢; (um ; vm )g の移動の中で
得点が正になるものが存在することを示せ。
• Solution
– s=
Xm Xn
r (ai + uj ; bi + vj ) > 0
j = 1 i= 1
Xn Xm
=
i= 1 j = 1
r (ai + uj ; bi + vj ) > 0
-2
5
-2
5
-2
5
-2
5
5
-2
5
-2
5
-2
5
-2
-2
5
-2
5
-2
5
-2
5
5
-2
5
-2
5
-2
5
-2
-2
5
-2
5
-2
5
-2
5
5
-2
5
-2
5
-2
5
-2
-2
5
-2
5
-2
5
-2
5
5
-2
5
-2
5
-2
5
-2
EX7.7 タイルセット A = f (a1; b1); ¢¢¢; (an ; bn )g
どのように移動しても得点が正。
B = f (u1; v1); ¢¢¢; (um ; vm )g の移動の中で
得点が正になるものが存在することを示せ。
• Solution
– s=
Xm Xn
r (ai + uj ; bi + vj ) > 0
j = 1 i= 1
Xn Xm
=
i= 1 j = 1
r (ai + uj ; bi + vj ) > 0
-2
5
-2
5
-2
5
-2
5
5
-2
5
-2
5
-2
5
-2
-2
5
-2
5
-2
5
-2
5
5
-2
5
-2
5
-2
5
-2
-2
5
-2
5
-2
5
-2
5
5
-2
5
-2
5
-2
5
-2
-2
5
-2
5
-2
5
-2
5
5
-2
5
-2
5
-2
5
-2
EX7.7 タイルセット A = f (a1; b1); ¢¢¢; (an ; bn )g
どのように移動しても得点が正。
B = f (u1; v1); ¢¢¢; (um ; vm )g の移動の中で
得点が正になるものが存在することを示せ。
• Solution
– s=
Xm Xn
r (ai + uj ; bi + vj ) > 0
j = 1 i= 1
Xn Xm
=
i= 1 j = 1
r (ai + uj ; bi + vj ) > 0
-2
5
-2
5
-2
5
-2
5
5
-2
5
-2
5
-2
5
-2
-2
5
-2
5
-2
5
-2
5
5
-2
5
-2
5
-2
5
-2
-2
5
-2
5
-2
5
-2
5
5
-2
5
-2
5
-2
5
-2
-2
5
-2
5
-2
5
-2
5
5
-2
5
-2
5
-2
5
-2
EX7.7 タイルセット A = f (a1; b1); ¢¢¢; (an ; bn )g
どのように移動しても得点が正。
B = f (u1; v1); ¢¢¢; (um ; vm )g の移動の中で
得点が正になるものが存在することを示せ。
• Solution
– s=
Xm Xn
r (ai + uj ; bi + vj ) > 0
j = 1 i= 1
Xn Xm
=
r (ai + uj ; bi + vj ) > 0
i= 1 j = 1
Xm
9i ; s:t:
r (ai + uj ; bi + vj ) > 0
j=1
-2
5
-2
5
-2
5
-2
5
5
-2
5
-2
5
-2
5
-2
-2
5
-2
5
-2
5
-2
5
5
-2
5
-2
5
-2
5
-2
-2
5
-2
5
-2
5
-2
5
5
-2
5
-2
5
-2
5
-2
-2
5
-2
5
-2
5
-2
5
5
-2
5
-2
5
-2
5
-2

Download Report