||V{maketoc}||
||__~~navy:@#13::: این مطلب از بخش آموزش وب‌سایت المپیاد ریاضی رشد،انتخاب شده که با فرمت pdf نیز در [http://olympiad.roshd.ir|وب‌سایت المپیاد رشد]موجود می‌باشد. برای مشاهده این موضوعات در وب‌سایت المپیاد، به آدرس [http://olympiad.roshd.ir/computercontentlist.html|فهرست مطالب کامپیوتر] مراجعه کنید. همچنین می‌توانید با کلیک ((مطالب علمی سایت المپیاد رشد|اینجا))‌ ، با ویژگی‌های بخش آموزش این وب‌سایت آشنا شوید.:: #@~~__||
^@#16:
!آشنایی با نظریه مجموعه ها
در این بخش با بحثی به نام نظریهُ مجموعه ها آشنا می شوید. در اینجا سعی شده است با ارائهُ قضایا و مسایل جالب در نظریهُ مجموعه ها، تکنیک هایی برای حل این نوع مسایل به دست آورید. ابتدا با چند تعریف ساده مبحث را شروع می کنیم.
---
!تعریف
فرض کنید {TEX()} {x} {TEX}یک ((مجموعه)) باشد،{TEX()} { P(x) } {TEX}را مجموعهُ تمام ((زیرمجموعه)) های {TEX()} {x} {TEX}تعریف می کنیم.
---
!تعریف
{TEX()} {F \subset P(x)} {TEX} را یک خانواده از زیرمجموعه های مجموعهُ {TEX()} {x} {TEX}می نامیم.
---
!تعریف
تعداد اعضای یک مجموعه مانند {TEX()} {x} {TEX}را با {TEX()} {|x|} {TEX} ( ((کاردینال)) {TEX()} {x} {TEX}) نمایش می دهیم.
---
!!مسألهُ 1
خانواده ای از زیرمجموعه های مجموعهُ {TEX()} {x} {TEX}مانند {TEX()} {F} {TEX}را خوب می نامیم با این شرط که اگر {TEX()} {A,B \in F} {TEX} باشند آنگاه {TEX()} {A \cap B \neq \emptyset} {TEX}. نشان دهید {TEX()} {|F| \le 2^{n-1}} {TEX}.
__اثبات__
اعضای{TEX()} { P(x)} {TEX} را به زوج های {TEX()} {(A,A^c)} {TEX} ((افراز)) می کنیم ({TEX()} {A^c} {TEX} مکمل {TEX()} {A} {TEX}است) و چون {TEX()} {|P(x)|=2^n} {TEX} است پس تعداد این زوج ها برابر {TEX()} {2^{n-1}} {TEX} است. طبق ((اصل لانه کبوتری)) اگر {TEX()} {|F| > 2^{n-1}} {TEX} باشد آنگاه دو عضو {TEX()} {F} {TEX}از یک زوج انتخاب می شود و چون اشتراک هر دو عضو از این زوج ها تهی است. پس {TEX()} {F} {TEX}خانواده ای خوب نیست که با فرض اولیه تناقض دارد. بنابراین نتیجه می شود که {TEX()} {|F| \le 2^{n-1}} {TEX}، و برای حالت تساوی می توان یک عضو از {TEX()} {x} {TEX}، مانند {TEX()} {a} {TEX}را در نظر گرفت و تمام زیرمجموعه های {TEX()} {x} {TEX}را که شامل {TEX()} {a} {TEX}هستند ایجاب کرد که تعداد این زیرمجموعه ها {TEX()} {2^{n-1}} {TEX} است.
---
!!مسألهُ 2
در مسأله بالا نشان دهید اگر {TEX()} {|F|<2^{n-1}} {TEX} باشد، می توان یک عضو از{TEX()} { P(x) } {TEX}را که در {TEX()} {F} {TEX}نیامده است به {TEX()} {F} {TEX}اضافه کرد و {TEX()} {F} {TEX}همچنان خوب باقی بماند.
__اثبات__
چون {TEX()} {|F|<2^{n-1}} {TEX} است طبق اثبات مسألهُ قبل نتیجه می شود که {TEX()} {A,A^c \in P(x)} {TEX} وجود دارند که {TEX()} {A^c \notin F} {TEX} یا {TEX()} {A \notin F} {TEX} حال از ((برهان خلف)) استفاده می کنیم. فرض کنید {TEX()} {A \cup F} {TEX} و {TEX()} {A^c \cup F} {TEX} هر دو خوب نباشند درنتیجه {TEX()} {B,C \in F} {TEX} وجود دارند که {TEX()} {C \cap A^c = \emptyset} {TEX} و {TEX()} {B \cap A =\emptyset} {TEX}
@@{TEX()} {\Rightarrow B \subset A^c \ , \ C \cap A^c=\emptyset \ \Rightarrow \ C \cap B =\emptyset} {TEX}@@
که خلاف فرض است. درنتیجه می توان به {TEX()} {F} {TEX}آنقدر عضو اضافه کرد که {TEX()} {|F|=2^{n-1}} {TEX} شود و {TEX()} {F} {TEX}خوب باقی بماند.
در زیر با ارائه یک تعریف و حل مسألهای با آن، ایدهُ بسیار خوبی از نظریهُ مجموعه ها به دست خواهید آورد.
#@
@#16:
---
!تعریف
ماتریس یک خانواده را به صورت زیر تعریف می کنیم:
فرض کنید {TEX()} {F=\{A_1,\cdots , A_k \}} {TEX}، {TEX()} {X=\{x_1,\cdots ,x_n \}} {TEX} و {TEX()} {A_i \subseteq X} {TEX} که {TEX()} {|X|=n} {TEX} باشد. یک ((ماتریس)) {TEX()} {n\times k} {TEX} را در نظر می گیریم که درایه سطر {TEX()} {i} {TEX}ام و ستون {TEX()} {j} {TEX}ام آن 1 است اگر و تنها اگر {TEX()} {x_i \in A_j} {TEX} باشد و در غیر این صورت صفر می باشد.
---
!!مسألهُ 3
{TEX()} {F} {TEX}یک خانوادهُ {TEX()} {m} {TEX}عضوی از زیرمجموعه های {TEX()} {r} {TEX}عضوی{TEX()} { P(x) } {TEX}است و به ازای هر {TEX()} {A_i,A_j} {TEX} متعلق به {TEX()} {F} {TEX}، {TEX()} {|A_i \cap A_j | \le k} {TEX} است. نشان دهید
@@{TEX()} {\Big| \bigcup_1^{|F|} A_i \Big| \ge \frac{r^2m}{r+k(m-1)}} {TEX}@@
__اثبات__
فرض کنید {TEX()} {F=\{A_1,A_2,\cdots , A_m \}} {TEX}، {TEX()} {X= \bigcup_1^{|F|} A_i} {TEX} و{TEX()} { |X|=n } {TEX} باشد. ماتریس این خانواده را در نظر می گیریم. در این ماتریس تعداد جفت درایه های واقع در سطر {TEX()} {i} {TEX}ام را که شامل 1 هستند {TEX()} {a_i} {TEX}می گیریم. در واقع {TEX()} {a-i} {TEX}تعداد {TEX()} {(A_k,A_j)} {TEX}هایی است که {TEX()} {x_i \in A_i \cap A_j} {TEX}. همچنین {TEX()} {S} {TEX}را مجموع همه {TEX()} {a_i} {TEX}ها {TEX()} {(i=1,2,\cdots ,n )} {TEX} در نظر می گیریم.
در ضمن می دانیم {TEX()} {A_i \cap A_j} {TEX} برابر است با تعداد یک های هم سطری که یک در ستون {TEX()} {i} {TEX}ام و دیگری در ستون {TEX()} {j} {TEX}ام قرار دارد. هر دو ستون از این ماتریس را که در نظر بگیریم حداکثر {TEX()} {k} {TEX}تا از این جفت درایه های شامل یک دارند. زیرا {TEX()} {|A_i \cap A_j| \le k} {TEX} است، پس
(1)@@{TEX()} {S \le {m\choose 2} k} {TEX}@@
#@
@#16:
و اگر تعداد یک های واقع در سطر {TEX()} {i} {TEX}ام را {TEX()} {b_i} {TEX} بگیریم تعداد جفت درایه های شامل یک، در سطر {TEX()} {i} {TEX}ام برابر {TEX()} {{{b_i}\choose 2}} {TEX} خواهد بود و نتیجه می شود که
@@{TEX()} {S={{b_1}\choose 2}+{{b_2}\choose 2}+\cdots +{{b_n}\choose 2}} {TEX}@@
(2)@@ {TEX()} {=\frac{1}{2} \Big[ big( b_1^2+b_2^2+\cdots +b_n^2 \big) – \big(b_1+b_2+\cdots b_n \big) \Big]} {TEX}@@
و چون {TEX()} {|A_i|=r} {TEX} است پس تعداد یک های کل جدول برابر {TEX()} {mr} {TEX}است یعنی
@@{TEX()} {b_1+b_2+\cdots +b_n=mr} {TEX}@@
طبق نامساوی کوشی شوارتز خواهیم داشت
@@{TEX()} {b_1^2+b_2^2+\cdots +b_n^2 \ge \frac{(b_1+b_2+\cdots +b_n)^2}{n}={m^2r^2}{n}} {TEX}@@
از (1) و (2) نیز نتیجه می شود:
@@{TEX()} {{m\choose 2}k \ge \frac{1}{2} \Big[ \big( b_1^2+b_2^2+\cdots +b_n^2 \big)- \big(b_1+\cdots +b_n \big) \Big]} {TEX}@@
@@{TEX()} {\Rightarrow \frac{1}{2} m(m-1)k \ge \frac{1}{2} \Big( \frac{m^2r^2}{n}-mr \Big)} {TEX}@@
@@{TEX()} { \Rightarrow \ (m-1)k \ge \frac{mr^2}{n}-r \ \Rightarrow \ r+(m-1)k \ge \frac{mr^2}{n}} {TEX}@@
@@ {TEX()} {\Rightarrow \ n \ge \frac{mr^2}{(m-1)k+r}} {TEX}@@
در حل مسألهُ فوق از روشی به نام دوگانه شمردن استفاده شده است. در این روش همان طور که در حل مسأله دیدید تعداد یک سری اعضای خاص یک بار در ستون ها شمرده می شود و یک بار در سطرها و چون تعداد این اعضای خاص در هر دو حالت برابر با تعداد اعضای خاص کل جدول می باشد، درنتیجه یک تساوی یا نامساوی بین مفروضات مسأله به دست می آید.
---
!!مسألهُ 4
فرض کنید {TEX()} {H=\{E_1,\cdots , E_m \}} {TEX} یک خانواده از مجموعه {TEX()} {n} {TEX}عضوی {TEX()} {x} {TEX}باشد و به ازا هر {TEX()} {F\subset E_i} {TEX}، {TEX()} {F\in H} {TEX} باشد نشان دهید که تابع {TEX()} {\delta :H\rightarrow H} {TEX} وجود دارد که به ازای هر {TEX()} {E\in H} {TEX}، {TEX()} {E \cap \delta (E)} {TEX}.
__اثبات__
#@
@#16:
فرض کنید {TEX()} {X=\{a_1,\cdots ,a_n \}} {TEX}. حال حکم را با ((استقرا)) روی {TEX()} {n} {TEX}اثبات می کنیم. حکم برای {TEX()} {n=1} {TEX} بدیهی است زیرا تابع {TEX()} {\delta} {TEX} با شرط {TEX()} {\delta (\emptyset )=a_1} {TEX} و {TEX()} {\delta (\{a_1 \})=\emptyset} {TEX} در شرط مسأله صدق می کند. فرض کنید حکم برای {TEX()} {n=k} {TEX} برقرار باشد، حکم را برای {TEX()} {n=k+1} {TEX} اثبات می کنیم. {TEX()} {H} {TEX}را به دو زیرمجموعه {TEX()} {H_1} {TEX} و {TEX()} {H_2} {TEX} افراز می کنیم به طوری که:
@@{TEX()} {\forall Ei \in H_1 \ \Rightarrow \ a_{k+1} \in E_i} {TEX}@@
@@{TEX()} {\forall E_i \in H_2 \ \Rightarrow \ a_{k+1} \notin E_i} {TEX}@@
همچنین {TEX()} {H_3} {TEX} را به صورت زیر تعریف می کنیم:
@@{TEX()} {H_3=\{E_1-\{a_{k+1} \} | E_i \in H_1 \}} {TEX}@@
طبق فرض مسأله هر عضو {TEX()} {H_3} {TEX} به {TEX()} {H} {TEX}متعلق است پس {TEX()} {H_3 \subset H_2} {TEX} است. با توجه به فرض استقرا، توابع {TEX()} {{\delta}_1 :H_2 \rightarrow H_2} {TEX} و {TEX()} {{\delta}_2 :H_3 \rightarrow H_3} {TEX} وجود دارند که در شرط مسأله صدق می کنند. حال {TEX()} {\delta} {TEX} را به صورت زیر تعریف می کنیم:
@@{TEX()} {A_i \in H_1 \ \Rightarrow \ \delta(A_i)={\delta}_1 (A_i-\{a_{k+1} \} )} {TEX} اگر@@
@@{TEX()} {A_i \in H_3 \Rightarrow \ \delta(A_i)=[{\delta}_2 (A_i)] \cup \{a_{k+1} \}} {TEX} اگر@@
@@ {TEX()} {A_i \in H_2} {TEX} اگر@@
@@ {TEX()} {\delta (A_i)={\delta}_1(A_i)} {TEX}@@
و
@@{TEX()} {A_i \notin H_3} {TEX}@@
به سادگی دیده می شود که تابع {TEX()} {\delta} {TEX} جواب مسأله است.
---
#@
@#16:
!!مسألهُ 5
فرض کنید {TEX()} {X} {TEX}مجموعه ای دلخواه با حداقل 12 عضو و {TEX()} {A_{1379},\cdots , A_2,A_1} {TEX} زیرمجموعه هایی 12 عضوی از {TEX()} {A} {TEX}باشند ({TEX()} {A_i} {TEX}ها لزوماً متمایز نیستند) ثابت کنید دو زیرمجموعهُ {TEX()} {X_1} {TEX} و {TEX()} {X_2} {TEX} وجود دارند به طوری که {TEX()} {X_1\cap X_2 =\emptyset } {TEX} و {TEX()} {X_1\cup X_2=X} {TEX} و به ازای هر {TEX()} {1 \le i \le 1379} {TEX}،
@@{TEX()} {A_i \subseteq X_2 \ , \ A_i \subset X_1} {TEX}@@
__اثبات__
__برهان خلف__ اگر چنین زیرمجموعه هایی وجود نداشته باشند، آنگاه برای هر افراز {TEX()} {X} {TEX}به دو مجموعه {TEX()} {X_1} {TEX} و {TEX()} {X_2} {TEX}، {TEX()} {i} {TEX}و {TEX()} {j} {TEX}وجود دارند به طوری که{TEX()} {A_i \subseteq X_j} {TEX}. بدون کاسته شدن از کلیت مسأله می توان فرض کرد که {TEX()} {X} {TEX}مجموعه ای متناهی است زیرا قرار می دهیم {TEX()} {X^\prime =\bigcup_{i=1}^{1379} A_i} {TEX} و به جای {TEX()} {X} {TEX}با {TEX()} {X^\prime} {TEX}کار می کنیم. فرض کنید {TEX()} {|X|=n} {TEX}، در این صورت تعداد افرازهای {TEX()} {X} {TEX}به دو مجموعهُ {TEX()} {X_1} {TEX} و {TEX()} {X_2} {TEX} برابر است با {TEX()} {2^n} {TEX}. حال تعداد حالاتی را می شماریم که {TEX()} {X} {TEX}به دو مجموعهُ {TEX()} {X_1} {TEX} و {TEX()} {X_2} {TEX} افراز شده است به طوری که به ازای یک اندیس {TEX()} {i} {TEX}معلوم {TEX()} {A_i \subseteq X_1} {TEX} یا {TEX()} {A_i \subseteq X_2} {TEX}.
اگر {TEX()} {A_i \subseteq X_1} {TEX}، آنگاه برای {TEX()} {X_1} {TEX}، {TEX()} {2^{n+2}} {TEX} حالت موجود است و با مشخص شدن {TEX()} {X_1} {TEX}، {TEX()} {X_2} {TEX} نیز مشخص می شود. به همین ترتیب اگر {TEX()} {A_i \subseteq X_2} {TEX} آنگاه برای {TEX()} {X_2} {TEX}، {TEX()} {2^{n-12}} {TEX} حالت موجود است و با مشخص شدن {TEX()} {X_2} {TEX}، {TEX()} {X_1} {TEX} معلوم خواهد شد.
بنابراین تعداد حالات بالا حداکثر برابر با {TEX()} {1379 \times 2 \times 2^{n-12}} {TEX} است، ولی
@@{TEX()} {1379 \times 2 \times 2^{n-12}=1379 \times 2^{n-11}<2^{11} \times 2^{n-11}=2^n} {TEX}@@
پس لااقل یک حالت باقی می ماند که در شرایط مسأله صدق می کند.
---
#@
@#16:
!قضیهُ اسپرنر
خانوادهُ {TEX()} {P=\{A_1 , \cdots A_p \}} {TEX} شامل زیرمجموعه هایی غیرتهی از {TEX()} {X=\{1,2,\cdots ,n \}} {TEX} مفروض است. به طوری که برای هر {TEX()} {i} {TEX}و {TEX()} {j} {TEX}داریم {picture=img/daneshnameh_up/2/21/com0032a.jpg} ، آنگاه
@@{TEX()} {|P| \le {n\choose {\Big[\frac{n}{2} \Big] }} {TEX}@@
__اثبات__
ابتدا نشان می دهیم تعداد خانواده های {TEX()} {\{B_0,B_1,\cdots ,B_n \}} {TEX} با شرط
@@{picture=img/daneshnameh_up/8/8c/com0032b.jpg}@@
برابر با {TEX()} {n!} {TEX}است.
با توجه به اینکه {TEX()} {G|B_0|<|B_1|<\cdots <|B_n| {TEX}، نتیجه می شود {TEX()} {|B_i|=i} {TEX} {TEX()} {(i=0,\cdots ,n)} {TEX} و {TEX()} {B_0} {TEX} ، 1 حالت دارد و {TEX()} {B_1} {TEX}، {TEX()} {n} {TEX}حالت داریم، {TEX()} {B_2} {TEX}،{TEX()} { n-1 } {TEX} حالت دارد و ... و {TEX()} {B_n} {TEX}، 1 حالت دارد پس تعداد این خانواده ها برابر {TEX()} {n!} {TEX}است. حال نشان می دهیم اگر {TEX()} {B_m} {TEX} ثابت باشد تعداد این خانواده ها برابر با {TEX()} {m!(n-m)!} {TEX} است، زیرا:
@@حالت {TEX()} {B_{m+1}-B_m=\{x_1 \} \rightarrow \qquad n-m} {TEX}@@
@@حالت {TEX()} {B_{m+2}-B_{m+1}=\{x_1 \} \rightarrow \qquad n-m-1} {TEX}@@
@@حالت {TEX()} {B_n-B_{n-1}=\{x_{n-m} \} \rightarrow \qquad 1} {TEX}@@
@@{picture=img/daneshnameh_up/2/2f/com0032c.jpg}@@
و تعداد خانواده های {TEX()} {\{B_0,\cdots ,B_{m+1}\}} {TEX} برابر با{TEX()} {m!} {TEX}و تعداد خانواده های {TEX()} {\{B_{m+1} ,cdots ,B_n \}} {TEX} برابر با {TEX()} {(n-m)!} {TEX} است، پس تعداد این خانواده ها برابر {TEX()} {m!(n-m)!} {TEX} است. حال به اثبات قضیه می پردازیم. اگر {TEX()} {|A_k|=k} {TEX} در این صورت تعداد خانواده های {TEX()} {\{A_0,\cdots , A_k , \cdots , A_n \}} {TEX} که شامل {TEX()} {A_k} {TEX} است برابر{TEX()} {k!(n-k)!} {TEXاست {TEX()} {P} {TEX}نیز از هر کدام از این خانواده ها حداکثر یک عضو دارد. پس
@@{TEX()} {\sun_{A\in P} |A|!(n-|A|)! \le n!} {TEX}@@
زیرا تعداد خانواده هایی که {picture=img/daneshnameh_up/9/9b/com0032d,e.jpg} و در آن {TEX()} {A_k} {TEX} ثابت باشد از تعداد خانواده هایی که شرطی به جز {picture=img/daneshnameh_up/9/9b/com0032d,e.jpg} ندارند بیشتر نیست. پس با فرض {TEX()} {|A_i|=k_i} {TEX} داریم:
#@
@#16:
@@{TEX()} {\sum_{i=1}^{|P|} k_i!(n-k_i)! \le n!} {TEX}@@
با توجه به اینکه
@@{TEX()} {{n\choose {k_i}}=\frac{n!}{k_i!(n-k_i)!} \ \Rightarrow \ \sum_{i=1}^{|P|} \frac{n!}{{n\choose{k_i}}} \le n!} {TEX}@@
(1)@@ {TEX()} {\Rightarrow \ \sum_{i=1}^{|P|} \frac{1}{{n\choose{k_i}}} \le 1} {TEX} @@
(2) @@{TEX()} {{n\choose {k_i}} \le {n\choose {\Big[\frac{n}{2} \Big] }} {TEX}@@
@@{TEX()} {\Rightarrow \ \frac{|P|}{{n\choose {\frac{n}{2}}} \le \sum_{i=1}^{|P|} \frac{1}{{n\choose {k_i}}} \le 1} {TEX} از (1) و (2)@@
@@{TEX()} {\Rightarrow |P| \le {n\choose {\Big[\frac{n}{2} \Big] }}} {TEX}@@
و اگر تساوی برقرار باشد در این صورت هر عضو {TEX()} {P\Big[ \frac{n}{2} \Big]} {TEX} یا {TEX()} {\Big[ \frac{n}{2} \Big]} {TEX} عضوی است و {TEX()} {P} {TEX}از هر خانواده دقیقاً یک عضو دارد.
---
!قضیه (Edros-ko-rado)
اگر {TEX()} {\{A_1,\cdots , A_m \}} {TEX} خانواده ای از زیرمجموعه های {TEX()} {k} {TEX}عضوی {TEX()} {\Big( k \le \frac{n}{2} \Big)} {TEX} مجموعهُ {TEX()} {\{1,2,\cdots , n \}} {TEX} باشد به طوری که برای هر {TEX()} {i\neq j} {TEX}، {TEX()} {A_i \cap A_j \neq \emptyset} {TEX}، در این صورت {TEX()} {m\le {{n-1}\choose {k-1}}} {TEX}.
__اثبات__
فرض کنید
@@ {TEX()} {F_i=\{i,i+1,\cdots , i+k-1 \} \qquad 1 \le i \le n} {TEX}@@
اعضای مجموعه را به پیمانهُ {TEX()} {n} {TEX} در نظر بگیرید، همچنین فرض کنید {TEX()} {F=\{F_1,\cdots , F_n \}} {TEX}، در این صورت {TEX()} {|A \cap F | \le k} {TEX} زیرا در غیر این صورت دو عضو از {TEX()} {A} {TEX}مثلاً {TEX()} {A_i} {TEX} و {TEX()} {A_j} {TEX} یافت می شوند به طوری که
#@
@#16:
@@{TEX()} {A_i \cap A_j=\emptyset} {TEX}.@@
برای هر ((جایگشت)) {TEX()} {\pi} {TEX} از{TEX()} {\{1,2,\cdots ,n\}} {TEX} مجموعه های {TEX()} {F_i^{\pi}} {TEX} و {TEX()} {F^{\pi}} {TEX} را به شکل زیر تعریف می کنیم: @@{TEX()} {F_i^{\pi} =\{\pi (x)|x \in F_i \}} {TEX}@@
@@{TEX()} {F^{\pi}=\{F_1^{\pi},F_2^{\pi} , \cdots , F_n^{\pi} \}} {TEX}@@
با استدلال مشابه حالت قبل می توان نشان داد {TEX()} {|A\cap F^{\pi}|\le k} {TEX}، پس {TEX()} {\sum_{\pi} |A\cap F^{\pi} | \le n!k} {TEX} و چون داریم:
{TEX()} {\sum_{\pi} |A \cap F^{\pi}=mnk!(n+k)!} {TEX} (چرا؟) درنتیجه خواهیم داشت:
@@{TEX()} {mnk!(n+k)! \le n!k \ \Rightarrow n(k-1)!(n-k)1 \le (n-1)!} {TEX}@@
@@{TEX()} {\Rightarrow \ m\le {{n-1}\choose {k-1}}} {TEX}@@
---
!تعریف
فرض کنید {TEX()} {\{A_0,\cdots , A_{n-1} \}} {TEX} خانواده ای از زیرمجموعه های مجموعهُ {TEX()} {S} {TEX}باشد، منظور از {TEX()} { SDR } {TEX} برای این خانواده یعنی {TEX()} {n} {TEX}عضو دو به دو متمایز {TEX()} {a_0,a_1,\cdots ,a_{n-1}} {TEX} از {TEX()} {S} {TEX}، به طوری که {TEX()} {a_i \in A_i} {TEX}.
---
!قضیه فیلپ هال
خانواده {TEX()} {\{A_0,A_1,\cdots ,A_{n-1}} {TEX} ،{TEX()} { SDR } {TEX} دارد اگر و تنها اگر ((اجتماع)) هر {TEX()} {k} {TEX}عضو این خانواده حداقل {TEX()} {k} {TEX}عضو داشته باشد.
(اثبات قضیهُ فوق را در این مقاله نمی آوریم.)
---
!تعریف
ماتریس مربعی {TEX()} {A} {TEX}را جایگشتی گوییم، هرگاه در هر سطر و هر ستون {TEX()} {A} {TEX}فقط یک درایه 1 و بقیهُ درایه ها صفر باشند.
---
#@
@#16:
!قضیه
فرض کنید {TEX()} {A} {TEX}ماتریسی با درایه های متعلق به ((اعداد صحیح)) نامنفی باشد، اگر مجموع درایه های هر سطر و هر ستون برابر {TEX()} {k} {TEX}باشد در این صورت {TEX()} {A} {TEX}را می توان به صورت مجموع {TEX()} {k} {TEX}ماتریس جایگشتی نوشت.
__اثبات__
تعریف کنید {TEX()} {A_i=\{j|a_{ij}>0 \}} {TEX}، {TEX()} {t} {TEX}سطر را در نظر بگیرید. مجموع درایه های آنها {TEX()} {tk} {TEX}است، پس حداقل در {TEX()} {t} {TEX}ستون درایه های ناصفر وجود دارند، زیرا مجموع درایه های هر ستون نیز {TEX()} {k} {TEX}است. بنابراین {TEX()} {\{a_1,\cdots , a_n \}} {TEX} در شرط قضیه ((فیلیپ هال)) صدق می کند، پس {TEX()} {n} {TEX}تا درایه وجود دارد که هیچ دوتایی در یک سطر یا یک ستون نبوده و هر کدام از صفر بیشتر هستند، بنابراین می توان از این درایه ها یک واحد کم کرد و یک ((ماتریس)) جایگشتی تولید کرد و با استقراء روی این ماتریس جدید حکم اثبات می شود. (جزئیات اثبات به عهدهُ خواننده گذاشته می شود).
---
!قضیه konig
فرض کنید {TEX()} {A} {TEX}ماتریسی باشد که درایه های آن 0 یا 1 هستند، در این صورت اگر کمترین تعداد سطرها یا ستون هایی که همهُ 1ها را شامل شوند {TEX()} {m} {TEX} بنامیم و بیشترین تعداد 1هایی که هیچ دوتایی هم سطر و یا هم ستون نیستند را {TEX()} {M} {TEX}بنامیم آنگاه {TEX()} { m=M } {TEX}.
__اثبات__
واضح است که {TEX()} {m\ge M} {TEX}. فرض کنید {TEX()} {m=r+s} {TEX} و {TEX()} {r} {TEX}سطر و {TEX()} {s} {TEX}ستون شامل همهُ 1ها باشد. بدون ازدست دادن کلیت فرض کنید این سطرها و ستون ها، {TEX()} {r} {TEX}سطر و {TEX()} {s} {TEX}ستون اول ماتریس باشند. به ازای {TEX()} {1 \le i \le r} {TEX} تعریف کنید: {TEX()} {A_i=\{j |a_{ij}=1 , j>s \}} {TEX}.
خانواده {TEX()} {\{A_1,a_2,\cdots , A_r \}} {TEX} در شرط هال صدق می کند زیرا اگر {TEX()} {k} {TEX}سطر باشند که حداکثر با {TEX()} {k-1} {TEX}ستون ((اشتراک)) داشته باشند می توان به جای {TEX()} {k} {TEX}سطر، {TEX()} {k-1} {TEX}ستون را انتخاب کرد که با ((مینیمم)) بودن {TEX()} {M} {TEX}در تناقض است. پس خانوادهُ فوق{TEX()} { SDR } {TEX} دارد، یعنی در بلوک سمت راست بالا، {TEX()} {r} {TEX}تا 1 دو به دو غیر هم خط وجود دارد به طور مشابه در بلوک سمت چپ پایین، {TEX()} {s} {TEX}تا 1 دو به دو غیر هم خط وجود دارد، پس حداقل{TEX()} { r+s=m } {TEX} تا 1 دو به دو غیر هم خط وجود دارد، بنابراین {TEX()} {M\ge m} {TEX}، لذا{TEX()} { M=m } {TEX}.
---
!قضیه
فرض کنید
@@{TEX()} {U,V \subseteq P(X) \ , \ |X|=n} {TEX}@@
با این شرط که
@@{picture=img/daneshnameh_up/c/c8/com0032f.jpg}@@
آنگاه {TEX()} {|U|\cdot |V| \le 2^n |U\cap V|} {TEX}، و اگر در شرط (2)، به جای {TEX()} {b\subseteq a} {TEX}، {TEX()} {a \subseteq b} {TEX} را قرار دهیم داریم:
@@{TEX()} {|U| \cdot |V| \ge 2^n|U \cap V|} {TEX}@@
---
!!مسألهُ 6
{TEX()} {F \subseteq P(X)} {TEX} مفروض است. اگر {TEX()} {|X|=n} {TEX} و به ازای هر {TEX()} {A,B \in F} {TEX}، {TEX()} {A\cap B \neq \emptyset} {TEX} و {TEX()} {A\cup B \neq X} {TEX} در این صورت نشان دهید {TEX()} {|F| \le 2^{n-2}} {TEX}.
__اثبات__
#@
@#16:
مجموعهُ {TEX()} {U} {TEX}و {TEX()} {V} {TEX}را به صورت زیر تعریف می کنیم:
@@{TEX()} {U=\{x|x\subseteq y \ , \ y \in F \}} {TEX}@@
@@{TEX()} {V=\{x|y\subseteq x \ , \ y \in F \}} {TEX}@@
در این صورت اگر {TEX()} {a^\prime ,a \in V} {TEX} آنگاه {TEX()} {a\cap a^\prime \neq \emptyset} {TEX} و اگر {TEX()} {a,a^\prime \in U} {TEX}، آنگاه {TEX()} {a\cup a^\prime \neq X} {TEX} و نیز اگر
@@{picture=img/daneshnameh_up/3/38/com0032g.jpg}@@

طبق قضیهُ گفته شده داریم:
@@{TEX()} {|U|\cdot |V| \ge 2^n|U\cap V|} {TEX}@@
و چون اشتراک هر دو عضوی از {TEX()} {V} {TEX}ناتهی و ((اجتماع)) هر دو عضوی از {TEX()} {U} {TEX}، مخالف {TEX()} {X} {TEX}است داریم:
@@{TEX()} {|U| \le 2^{n-1}} {TEX}@@
@@{TEX()} {|V| \le 2^{n-1}} {TEX}@@
و با توجه به اینکه {TEX()} {|F| \le |U \cap V|} {TEX} خواهیم داشت:
@@{TEX()} {2^n|F| \le 2^n|U\cap V| \le |U| \cdot |V| \le 2^{n-1} \times 2^{n-1}\2^{2n-2}} {TEX}@@
@@{TEX()} {\Rightarrow \ |F| \le 2^{n-2}} {TEX}@@
---
! پیوند های خارجی
[http://Olympiad.roshd.ir/computer/content/pdf/0057.pdf]
---
!همچنین ببینید
*((نظریه گراف (المپیاد) ))
*((تعریف گراف ))
*((اعداد رمزی ))
#@^