7章後半 M1　鈴木洋介.

Presentation on theme: "7章後半 M1　鈴木洋介."— Presentation transcript:

1 7章後半 M1　鈴木洋介

2 Example 7.8. 正n角形(n≧3)P1P2…Pnの3頂点を結んでできる三角形はいくつ存在するか。 ただし、合同なものは1つと数える。 三角形の頂点の１つをP1 に固定する。 N1：正三角形の数 N2：正三角形でない二等辺三角形の数 N3：不等辺三角形の数 としてN=N1+N2+N3を求める。 P1を頂点とする三角形は　　　　　個。 S={P1PiPj|2≦i＜j≦n}とすると|S|= Sのうちに、 同じ形の不等辺三角形はそれぞれ3!=6個存在する。 P1

3 Example 7.8. 正n角形(n≧3)P1P2…Pnの3頂点を結んでできる三角形はいくつ存在するか。 ただし、合同なものは1つと数える。 三角形の頂点の１つをP1 に固定する。 N1：正三角形の数 N2：正三角形でない二等辺三角形の数 N3：不等辺三角形の数 としてN=N1+N2+N3を求める。 P1を頂点とする三角形は　　　　　個。 S={P1PiPj|2≦i＜j≦n}とすると|S|= Sのうちに、 同じ形の不等辺三角形はそれぞれ3!=6個存在する。 同じ形の二等辺三角形はそれぞれ3個存在する。 P1

4 Example 7.8. 正n角形(n≧3)P1P2…Pnの3頂点を結んでできる三角形はいくつ存在するか。 ただし、合同なものは1つと数える。 三角形の頂点の１つをP1 に固定する。 N1：正三角形の数 N2：正三角形でない二等辺三角形の数 N3：不等辺三角形の数 としてN=N1+N2+N3を求める。 P1を頂点とする三角形は　　　　　個。 S={P1PiPj|2≦i＜j≦n}とすると|S|= Sのうちに、 同じ形の不等辺三角形はそれぞれ3!=6個存在する。 同じ形の二等辺三角形はそれぞれ3個存在する。 同じ形の正三角形は（存在するなら）1個存在する。 よって　　　　　=N1+3N2+6N3　　　・・・(*) P1

5 Example 7.8. 正n角形(n≧3)P1P2…Pnの3頂点を結んでできる三角形はいくつ存在するか。 ただし、合同なものは1つと数える。 P1を含む正三角形は最大１個なのでN1=1-p。 （pを正三角形が存在するとき0、しないとき1とする） P1Pi=P1Pjとなる二等辺三角形（正三角形含む）の数は、 nが偶数の場合 (n-2)/2、奇数の場合(n-1)/2 よってN1+N2=(n-2+q)/2　　　・・・(**) (nが偶数ならq=0 奇数なら 1) (*)(**)より p,q∈{0,1}。-4≦3q-4p≦3なのでNはn2/12に最も近い整数。 すなわち、

6 Example 7.9. 平面上にn個の点の集合Tがある。どの3点も一直線上になく、 各点に対して等距離の点がk個以上存在する。 このとき、　　　　　　　を証明せよ。 A=T={P1,P2,…,Pn}とする。 B={li,j|1≦i＜j≦n　li,jは線分PiPjの垂直二等分線}とする。 このとき|B|= S={(Pi,lj,k)|点Piは垂直二等分線lj,k上にある}とする。 どの3点も一直線上にないという条件から、|S(*,lj,k)|≦2。 よって li,j Pi Pj

7 Example 7.9. 平面上にn個の点の集合Tがある。どの3点も一直線上になく、 各点に対して等距離の点がk個以上存在する。 このとき、　　　　　　　を証明せよ。 ある点Piは少なくともk本の二等分線上にあるはずなので|S(Pi,*)|≧ 以上の２式よりk2-k-2(n-1)≦0 よって問題の不等式が成り立つ。 Pi

8 Example 7.10. 一直線上にn個の点がある。2点間の距離を考える。 各距離の値は最大2回しか現れない。このとき、 少なくとも　　　個の距離は1回だけ現れることを示せ。 x,yをそれぞれ1,2回だけ現れる距離の数とする。 x+yの下限を求めよう。 各点を左から右の順番にP1,…Pnとする。 プロセス1： P1を左の端点とする線分を考える。 このときP1はn-1個の線分の左の端点となる。 プロセス2： P2を左の端点とする線分を考える。 P2はn-2個の線分の左の端点となるが、 このうちいくつかの距離はすでにプロセス1で現れている可能性がある。 もしP1Pi=P2PjかつP1Pk=P2Plのとき、P1P2=PiPj=PkPlとなり、 同じ距離が3回以上は現れないという条件に矛盾する。 よって2回以上同じ長さはP1を含む距離に現れない。 つまり、n-3以上の新しい距離が現れることになる。 P1 P2

9 Example 7.10. 一直線上にn個の点がある。2点間の距離を考える。 各距離の値は最大2回しか現れない。このとき、 少なくとも　　　個の距離は1回だけ現れることを示せ。 プロセス3： P3を左の端点とする線分を考える。 これ以降も同様の議論を行えて、n-5以上の新しい距離が現れる。 よって距離の種類の合計x+y≧(n-1)+(n-3)+(n-5)+・・・ nが奇数ならx+y≧(n2-1)/4、偶数ならx+y≧n2/4となる。 同じ距離を許した距離の総数x+2y=n(n-1)/2より、

10 Example 7.11. p(n)をnの整数分割の数とする。 p(n,m)を分割数mのnの整数分割の数とする。 h(n,m)を最大値mのnの整数分割の数とする。 p(n,m)=h(n,m)を示せ。 例：n=6,m=3 6を3つの自然数に分割する。 6=1+1+4 6=1+2+3 6=2+2+2 6を最大値3の自然数に分割する。 6=3+3 6= p(6,3)=h(6,3)=3

11 (3,5,7,8,9,9) (2,3,4,4,5,5,6,6,6) Example 7.11. p(n)をnの整数分割の数とする。
p(n,m)を分割数mのnの整数分割の数とする。 h(n,m)を最大値mのnの整数分割の数とする。 p(n,m)=h(n,m)を示せ。 分割(a1,…,am)をn×m行列で表現する。 各i列ごとに上からai個を1,それ以外を0にする。 この行列を裏返して90度傾けると 一意に最大値mの分割を示すm×n行列となる。 この変換は全単射なので p(n,m)=h(n,m)。 (3,5,7,8,9,9) (2,3,4,4,5,5,6,6,6)

12 Example 7.12. πがnの整数分割であるとき、α(π)をπに含まれる1の数とする。 β(π)をπに含まれる値の種類数とする。 ∑を全てのnの整数分割についての和とするとき、 ∑ α(π)= ∑β(π)を示せ。 例：n=4 4=4 4=3+1 4=2+2 4=2+1+1 4= α(π)=0　β(π)=1 α(π)=1　β(π)=2 α(π)=2　β(π)=2 α(π)=4　β(π)=1 α(π)=7　β(π)=7 +

13 Example 7.12. πがnの整数分割であるとき、α(π)をπに含まれる1の数とする。 β(π)をπに含まれる値の種類数とする。 ∑を全てのnの整数分割についての和とするとき、 ∑ α(π)= ∑β(π)を示せ。 A={1,2,…,n}、B={π|πはnの整数分割}とする。 p(n)をnの整数分割の個数とすると、|B|=p(n)。 S={(a,π)|a∈A,π∈B,aはπに含まれる}とする。 このときβ(π)=|S(*,π)|。 フビニの法則より π=(a1,a2,…am)とする。 a=akがπに含まれるとき(a1,a2,…,ak-1,ak+1,…,am)はn-aの整数分割となる。 よって|S(a,*)|=p(n-a)。 ただしp(0)=1と定める。するとフビニの定理より

14 Example 7.12. πがnの整数分割であるとき、α(π)をπに含まれる1の数とする。 β(π)をπに含まれる値の種類数とする。 ∑を全てのnの整数分割についての和とするとき、 ∑ α(π)= ∑β(π)を示せ。 帰納法で以下の式を示す。 n=1のときπ={1}のみなので明らか。Bnをnの分割の集合として を仮定し、n+1の分割を考える。 あるnの分割に対して、1を追加するとそれはn+1の分割となる。 これによって、nの分割のうちに存在した　　　　　　個の1に p(n)個の1が追加されることになる。よって 以上の帰納が成り立つので∑ α(π)= ∑β(π)が言える。

15 Example 7.13. Xをn (≧7)要素の集合とする。 A1,…Amを相異なる、5要素のXの部分集合とする。 なるmに対してインデックスi1,…,i6が存在して Ai1,…,Ai6の和集合はちょうど6要素を含むことを示せ。 何が言いたいのか？ n要素の集合から５要素の部分集合をいろいろ作っていく。 ある程度たくさん(m＞・・・)集合を作りだしたら、 このような関係の６集合が見つかるはず。 ちなみに、各部分集合はそれぞれ異なるので、 ２つ以上の和集合をとればその要素数は必ず6以上になる。 これから、どの６要素の和集合も要素数が６より多くなると仮定して、矛盾を導く。 １２３４５ １２４５６ １２３４６ １３４５６ １２３５６ ２３４５６

16 記号をどのように設定するか？ ⊃ ⊃ ⊃ ⊃ ⊃ ⊃ SQに含まれる要素をQに加えると、 Aに含まれる集合に「復元」できる。 A Q A
X A1 Q SQ A1 ⊃ ⊃ 対応 和集合 A2 Q SQ A2 ⊃ ⊃ ・ ・ ・ ・ ・ Am Q SQ Am ×n個 ⊃ ⊃

17 × × 記号をどのように設定するか？ ⊃ ⊃ ⊃ ⊃ ⊃ ⊃ SQに含まれる要素をQに加えると、 Aに含まれる集合に「復元」できる。 A Q
VA1 A X A1 Q SQ A1 × ⊃ ⊃ 対応 和集合 A2 Q SQ A2 × ⊃ ⊃ ・ 直積 ・ ・ ・ ・ Am Q SQ Am ×n個 ⊃ ⊃

18 Example 7.13. Xをn (≧7)要素の集合とする。 A1,…Amを相異なる、5要素のXの部分集合とする。 なるmに対してインデックスi1,…,i6が存在して Ai1,…,Ai6の和集合はちょうど6要素を含むことを示せ。 フビニの法則より x∈AならVA(*,x)={(A-{x},x)}なので|VA(*,x)|=1。 x∈X-Aなら|VA(*,x)|≦4。 ∵5以上だと、和集合が６要素となる６つの部分集合 A,Q1∪{x},Q2∪{x},Q3∪{x},Q4∪{x},Q5∪{x} が存在することになるので矛盾。 以上より

19 Example 7.13. Xをn (≧7)要素の集合とする。 A1,…Amを相異なる、5要素のXの部分集合とする。 なるmに対してインデックスi1,…,i6が存在して Ai1,…,Ai6の和集合はちょうど6要素を含むことを示せ。 TQ={A|A∈A,Q⊂A}とするとSQとTQは一対一対応する。 |SQ|=|TQ|より |TQ|は上式の左辺の和の中で|TQ|回現れる。よって 二乗平均平方根に関する不等式より、 |Q|≦　　　より、上記の式を合わせて

20 × 記号をどのように設定するか？ ⊃ ⊃ ⊃ ⊃ ⊃ ⊃ SQに含まれる値をQに加えると、 Aに含まれる集合に「復元」できる。 A U Q
X A1 Q SQ A1 × 直積 ⊃ ⊃ 対応 和集合 A2 Q SQ A2 ⊃ ⊃ ・ ・ ・ ・ ・ Am Q SQ Am ×n個 ⊃ ⊃

21 Example 7.13. Xをn (≧7)要素の集合とする。 A1,…Amを相異なる、5要素のXの部分集合とする。 なるmに対してインデックスi1,…,i6が存在して Ai1,…,Ai6の和集合はちょうど6要素を含むことを示せ。 U={(A,Q)|A∈A,Q∈Q,Q⊂A}とするとU(*,Q)=TQ。 T(A,*)はAに含まれる全ての４つ組なので| T(A,*) |=5 フビニの法則より よって となり前提条件の式に矛盾する。

22 Example 7.14. 一部砂糖入りの異なるケーキミックスを使って、68個のケーキを作る。 (1)各ケーキは5種類の異なるケーキミックスから作られる。 (2)各ケーキを作るケーキミックスのうち1つ以上は砂糖入りである。 (3)どのケーキミックスを３つ選んでも、それら全てを含むケーキがただ1つある。 このとき1つ以上は砂糖入りのケーキミックスが４つ以上使われた 甘すぎるケーキであることを証明せよ。 甘すぎるケーキは存在しないと仮定して、矛盾を導く。 全てのケーキミックスをs1,s2,…,sn 、 そのうち砂糖入りのものをs1,s2,…,smとする。(n≧m) ケーキミックスの３つ組を考えたとき、全体で　　　個の３つ組が存在する。 また、それぞれのケーキに対して、３つ組は　　 =10個含まれる。 68・10=　　　より、n=17。

23 Example 7.14. 一部砂糖入りの異なるケーキミックスを使って、68個のケーキを作る。 (1)各ケーキは5種類の異なるケーキミックスから作られる。 (2)各ケーキを作るケーキミックスのうち1つ以上は砂糖入りである。 (3)どのケーキミックスを３つ選んでも、それら全てを含むケーキがただ1つある。 このとき1つ以上は砂糖入りのケーキミックスが４つ以上使われた 甘すぎるケーキであることを証明せよ。 1つのケーキミックスsiが使われるケーキの数ciを求めよう。 各ケーキの中でsiを含む３つ組の数は　　　　=6。 ⇒siを含む３つ組の数は6ci。 また、全体では、siを含む３つ組の総数は　　　　=120 6ci=120より、ci=20 ・・・1つのケーキミックスは20個のケーキに使われる。

24 Example 7.14. 一部砂糖入りの異なるケーキミックスを使って、68個のケーキを作る。 (1)各ケーキは5種類の異なるケーキミックスから作られる。 (2)各ケーキを作るケーキミックスのうち1つ以上は砂糖入りである。 (3)どのケーキミックスを３つ選んでも、それら全てを含むケーキがただ1つある。 このとき1つ以上は砂糖入りのケーキミックスが４つ以上使われた 甘すぎるケーキであることを証明せよ。 2つのケーキミックスsi,sjが両方使われるケーキの数ci,jを求めよう。(1≦i ≦ j ≦ 17) 各ケーキの中でsi,sjを含む３つ組の数は　　　 =3。 ⇒si,sjを両方含む３つ組の数は3ci,j。 また、全体で、si,sjを両方含む３つ組の総数は　　　　=15 3ci,j=15より、ci,j=5 ・・・2つのケーキミックスの組は5個のケーキに使われる。

25 Example 7.14. 一部砂糖入りの異なるケーキミックスを使って、68個のケーキを作る。 (1)各ケーキは5種類の異なるケーキミックスから作られる。 (2)各ケーキを作るケーキミックスのうち1つ以上は砂糖入りである。 (3)どのケーキミックスを３つ選んでも、それら全てを含むケーキがただ1つある。 このとき1つ以上は砂糖入りのケーキミックスが４つ以上使われた 甘すぎるケーキであることを証明せよ。 3つのケーキミックスsi,sj,skが全て使われるケーキの数ci,j,kを求めよう。 (1≦i ≦ j ≦k ≦ 17) 問題文より、 ci,j,k=1。 4つのケーキミックスsi,sj,sk,slが全て使われるケーキの数ci,j,k,lを求めよう。 仮定より、 1≦i≦j≦k≦l≦mならば ci,j,k,l=0。

26 Example 7.14. 一部砂糖入りの異なるケーキミックスを使って、68個のケーキを作る。 (1)各ケーキは5種類の異なるケーキミックスから作られる。 (2)各ケーキを作るケーキミックスのうち1つ以上は砂糖入りである。 (3)どのケーキミックスを３つ選んでも、それら全てを含むケーキがただ1つある。 このとき1つ以上は砂糖入りのケーキミックスが４つ以上使われた 甘すぎるケーキであることを証明せよ。 どのケーキにも砂糖入りケーキミックスが１つは入っていることを考慮する。 s1 =ミックス ×11 sn （ノンシュガー） sm s2 =ケーキ ×11 ×11

27 Example 7.14. 一部砂糖入りの異なるケーキミックスを使って、68個のケーキを作る。 (1)各ケーキは5種類の異なるケーキミックスから作られる。 (2)各ケーキを作るケーキミックスのうち1つ以上は砂糖入りである。 (3)どのケーキミックスを３つ選んでも、それら全てを含むケーキがただ1つある。 このとき1つ以上は砂糖入りのケーキミックスが４つ以上使われた 甘すぎるケーキであることを証明せよ。 どのケーキにも砂糖入りケーキミックスが１つは入っていることを考慮する。 包除原理より 以上の方程式を満たすm≦17は存在しないので、矛盾する。 よって必ず甘すぎるケーキが存在する。スイーツ（笑）

28

29 Example 7.13. Xをn (≧7)要素の集合とする。 A1,…Amを相異なる、5要素のXの部分集合とする。 なるmに対してインデックスi1,…,i6が存在して Ai1,…,Ai6の和集合はちょうど6要素を含むことを示せ。 問題の前提条件において、どの6つの部分集合をとっても その和集合は6以上 A={A1,…,Am} Q={ Q | |Q|=4,あるA∈Aに対してQ⊂A} QAをA(∈A)から４つ要素を取り出した組（４つ組）の集合とする。 このときQは全ての４つ組の集合となる。 この定義より、Qの要素となる各Qに対して1つ以上はXの要素xが存在して Q∪{x}∈Aとなる。 SQ={x|x∈X,Q∪{x}∈A}とする。 Aの要素Aに対して、直積QA ×Xを考える。 VA={(Q,x)|Q∈QA,x∈X, Q∪{x}∈A}とする。 このとき|VA(Q,*)|=|SQ|。 フビニの定理より、