منو
 کاربر Online
800 کاربر online
Lines: 1-189Lines: 1-191
 ||V{maketoc}|| ||V{maketoc}||
-||__~~navy:@#13::: این مطلب از بخش آموزش وب‌سایت المپیاد یی رشد،انتخاب شده که با فرمت pdf نیز در [http://olympiad.roshd.ir|وب‌سایت المپیاد رشد]موجود می‌باشد. برای مشاهده این موضوعات در وب‌سایت المپیاد، به آدرس [http://olympiad.roshd.ir/computercontentlist.html|فهرست مطالب کامپیوتر] مراجعه کنید. همچنین می‌توانید با کلیک ((مطالب علمی سایت المپیاد رشد|اینجا))‌ ، با ویژگی‌های بخش آموزش این وب‌سایت آشنا شوید.:: #@~~__|| +||__~~navy:@#13::: این مطلب از بخش آموزش وب‌سایت المپیاد کمپیو رشد،انتخاب شده که با فرمت pdf نیز در [http://olympiad.roshd.ir|وب‌سایت المپیاد رشد]موجود می‌باشد. برای مشاهده این موضوعات در وب‌سایت المپیاد، به آدرس [http://olympiad.roshd.ir/computercontentlist.html|فهرست مطالب کامپیوتر] مراجعه کنید. همچنین می‌توانید با کلیک ((مطالب علمی سایت المپیاد رشد|اینجا))‌ ، با ویژگی‌های بخش آموزش این وب‌سایت آشنا شوید.:: #@~~__||
 ^@#16: ^@#16:
 !آشنایی با نظریه مجموعه ها  !آشنایی با نظریه مجموعه ها
-در این بخش با بحثی به نام نظریهُ مجموعه ها آشنا می شوید. در اینجا سعی شده است با ارائهُ قضایا و مسایل جالب در نظریهُ مجموعه ها، تکنیک هایی برای حل این نوع مسایل به دست آورید. ابتدا با چند تعریف ساده مبحث را شروع می کنیم. +در این بخش با بحثی به نام نظریه مجموعه ها آشنا می شوید. در اینجا سعی شده است با ارائه قضایا و مسایل جالب در نظریه مجموعه ها، تکنیک هایی برای حل این نوع مسایل به دست آورید. ابتدا با چند تعریف ساده مبحث را شروع می کنیم.
 --- ---
 !تعریف !تعریف
- فرض کنید {TEX()} {x} {TEX}یک مجموعه باشد،{TEX()} { P(x) } {TEX}را مجموعهُ تمام زیرمجموعه های {TEX()} {x} {TEX}تعریف می کنیم. + فرض کنید {TEX()} {x} {TEX}یک ((مجموعه)) باشد،{TEX()} { P(x) } {TEX}را مجموعه تمام ((زیرمجموعه)) های {TEX()} {x} {TEX}تعریف می کنیم.
 --- ---
 !تعریف !تعریف
- {TEX()} {F \subset P(x)} {TEX} را یک خانواده از زیرمجموعه های مجموعهُ {TEX()} {x} {TEX}می نامیم. + {TEX()} {F \subset P(x)} {TEX} را یک خانواده از زیرمجموعه های مجموعه {TEX()} {x} {TEX}می نامیم.
 --- ---
 !تعریف !تعریف
- تعداد اعضای یک مجموعه مانند {TEX()} {x} {TEX}را با {TEX()} {|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}.
+!!مسأله 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} است. +اعضای{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 +!!مسأله 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()} { 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()} {|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()} {\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}خوب باقی بماند.  که خلاف فرض است. درنتیجه می توان به {TEX()} {F} {TEX}آنقدر عضو اضافه کرد که {TEX()} {|F|=2^{n-1}} {TEX} شود و {TEX()} {F} {TEX}خوب باقی بماند.
-در زیر با ارائه یک تعریف و حل مسألهای با آن، ایدهُ بسیار خوبی از نظریهُ مجموعه ها به دست خواهید آورد. +در زیر با ارائه یک تعریف و حل مسألهای با آن، ایده بسیار خوبی از نظریه مجموعه ها به دست خواهید آورد.
 #@ #@
 @#16: @#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} باشد و در غیر این صورت صفر می باشد. +فرض کنید {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} است. نشان دهید
+!!مسأله 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()} {\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()} {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} است، پس  در ضمن می دانیم {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}@@ + (1)@@{TEX()} {S \le {m\choose 2} k} {TEX}@@
 #@ #@
 @#16: @#16:
 و اگر تعداد یک های واقع در سطر {TEX()} {i} {TEX}ام را {TEX()} {b_i} {TEX} بگیریم تعداد جفت درایه های شامل یک، در سطر {TEX()} {i} {TEX}ام برابر {TEX()} {{{b_i}\choose 2}} {TEX} خواهد بود و نتیجه می شود که  و اگر تعداد یک های واقع در سطر {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}@@ @@{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}@@ +(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()} {|A_i|=r} {TEX} است پس تعداد یک های کل جدول برابر {TEX()} {mr} {TEX}است یعنی
 @@{TEX()} {b_1+b_2+\cdots +b_n=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}@@ @@{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) نیز نتیجه می شود:  از (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()} {{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 \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 \ (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}@@ @@ {TEX()} {\Rightarrow \ n \ge \frac{mr^2}{(m-1)k+r}} {TEX}@@
-در حل مسألهُ فوق از روشی به نام دوگانه شمردن استفاده شده است. در این روش همان طور که در حل مسأله دیدید تعداد یک سری اعضای خاص یک بار در ستون ها شمرده می شود و یک بار در سطرها و چون تعداد این اعضای خاص در هر دو حالت برابر با تعداد اعضای خاص کل جدول می باشد، درنتیجه یک تساوی یا نامساوی بین مفروضات مسأله به دست می آید. +در حل مسأله فوق از روشی به نام دوگانه شمردن استفاده شده است. در این روش همان طور که در حل مسأله دیدید تعداد یک سری اعضای خاص یک بار در ستون ها شمرده می شود و یک بار در سطرها و چون تعداد این اعضای خاص در هر دو حالت برابر با تعداد اعضای خاص کل جدول می باشد، درنتیجه یک تساوی یا نامساوی بین مفروضات مسأله به دست می آید.
 --- ---
-!!مسألهُ 4 +!!مسأله 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}.   فرض کنید {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: @#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()} {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 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()} {\forall E_i \in H_2 \ \Rightarrow \ a_{k+1} \notin E_i} {TEX}@@
 همچنین {TEX()} {H_3} {TEX} را به صورت زیر تعریف می کنیم:  همچنین {TEX()} {H_3} {TEX} را به صورت زیر تعریف می کنیم:
 @@{TEX()} {H_3=\{E_1-\{a_{k+1} \} | E_i \in H_1 \}} {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()} {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_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_3 \Rightarrow \ \delta(A_i)=[{\delta}_2 (A_i)] \cup \{a_{k+1} \}} {TEX} اگر@@
  @@ {TEX()} {A_i \in H_2} {TEX} اگر@@  @@ {TEX()} {A_i \in H_2} {TEX} اگر@@
 @@ {TEX()} {\delta (A_i)={\delta}_1(A_i)} {TEX}@@ @@ {TEX()} {\delta (A_i)={\delta}_1(A_i)} {TEX}@@
  و  و
 @@{TEX()} {A_i \notin H_3} {TEX}@@ @@{TEX()} {A_i \notin H_3} {TEX}@@
 به سادگی دیده می شود که تابع {TEX()} {\delta} {TEX} جواب مسأله است.  به سادگی دیده می شود که تابع {TEX()} {\delta} {TEX} جواب مسأله است.
 --- ---
 #@ #@
 @#16: @#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}،
+!!مسأله 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()} {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()} {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()} {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}} {TEX} است، ولی
 @@{TEX()} {1379 \times 2 \times 2^{n-12}=1379 \times 2^{n-11}<2^{11} \times 2^{n-11}=2^n} {TEX}@@ @@{TEX()} {1379 \times 2 \times 2^{n-12}=1379 \times 2^{n-11}<2^{11} \times 2^{n-11}=2^n} {TEX}@@
 پس لااقل یک حالت باقی می ماند که در شرایط مسأله صدق می کند.  پس لااقل یک حالت باقی می ماند که در شرایط مسأله صدق می کند.
 --- ---
 #@ #@
 @#16: @#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=\{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()} {|P| \le {n\choose {\Big[\frac{n}{2} \Big] }} {TEX}@@
 __اثبات__  __اثبات__
 ابتدا نشان می دهیم تعداد خانواده های {TEX()} {\{B_0,B_1,\cdots ,B_n \}} {TEX} با شرط  ابتدا نشان می دهیم تعداد خانواده های {TEX()} {\{B_0,B_1,\cdots ,B_n \}} {TEX} با شرط
 @@{picture=img/daneshnameh_up/8/8c/com0032b.jpg}@@ @@{picture=img/daneshnameh_up/8/8c/com0032b.jpg}@@
 برابر با {TEX()} {n!} {TEX}است.  برابر با {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()} {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+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_{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}@@ +@@حالت {TEX()} {B_n-B_{n-1}=\{x_{n-m} \} \rightarrow \qquad 1} {TEX}@@
 @@{picture=img/daneshnameh_up/2/2f/com0032c.jpg}@@ @@{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()} {\{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}@@ @@{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} داریم:  زیرا تعداد خانواده هایی که {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: @#16:
 @@{TEX()} {\sum_{i=1}^{|P|} k_i!(n-k_i)! \le n!} {TEX}@@ @@{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}@@ @@{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} @@ (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}@@ (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 \ \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()} {\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}از هر خانواده دقیقاً یک عضو دارد.  و اگر تساوی برقرار باشد در این صورت هر عضو {TEX()} {P\Big[ \frac{n}{2} \Big]} {TEX} یا {TEX()} {\Big[ \frac{n}{2} \Big]} {TEX} عضوی است و {TEX()} {P} {TEX}از هر خانواده دقیقاً یک عضو دارد.
 --- ---
 !قضیه (Edros-ko-rado) !قضیه (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()} {\{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()} {F_i=\{i,i+1,\cdots , i+k-1 \} \qquad 1 \le i \le n} {TEX}@@
-اعضای مجموعه را به پیمانهُ n در نظر بگیرید، همچنین فرض کنید {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} یافت می شوند به طوری که +اعضای مجموعه را به پیمانه {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: @#16:
 @@{TEX()} {A_i \cap A_j=\emptyset} {TEX}.@@ @@{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()} {\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()} {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()} {|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()} {\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()} {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()} {\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,\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_0,A_1,\cdots ,A_{n-1}} {TEX} ،{TEX()} { SDR } {TEX} دارد اگر و تنها اگر ((اجتماع)) هر {TEX()} {k} {TEX}عضو این خانواده حداقل {TEX()} {k} {TEX}عضو داشته باشد.
(اثبات قضیه فوق را در این مقاله نمی آوریم.)
 --- ---
 !تعریف !تعریف
- ماتریس مربعی {TEX()} {A} {TEX}را جایگشتی گوییم، هرگاه در هر سطر و هر ستون {TEX()} {A} {TEX}فقط یک درایه 1 و بقیهُ درایه ها صفر باشند. + ماتریس مربعی {TEX()} {A} {TEX}را جایگشتی گوییم، هرگاه در هر سطر و هر ستون {TEX()} {A} {TEX}فقط یک درایه 1 و بقیه درایه ها صفر باشند.
 --- ---
 #@ #@
 @#16: @#16:
 !قضیه !قضیه
- فرض کنید {TEX()} {A} {TEX}ماتریسی با درایه های متعلق به اعداد صحیح نامنفی باشد، اگر مجموع درایه های هر سطر و هر ستون برابر {TEX()} {k} {TEX}باشد در این صورت {TEX()} {A} {TEX}را می توان به صورت مجموع {TEX()} {k} {TEX}ماتریس جایگشتی نوشت. + فرض کنید {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}تا درایه وجود دارد که هیچ دوتایی در یک سطر یا یک ستون نبوده و هر کدام از صفر بیشتر هستند، بنابراین می توان از این درایه ها یک واحد کم کرد و یک ماتریس جایگشتی تولید کرد و با استقراء روی این ماتریس جدید حکم اثبات می شود. (جزئیات اثبات به عهدهُ خواننده گذاشته می شود). + تعریف کنید {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  !قضیه konig
- فرض کنید {TEX()} {A} {TEX}ماتریسی باشد که درایه های آن 0 یا 1 هستند، در این صورت اگر کمترین تعداد سطرها یا ستون هایی که همهُ 1ها را شامل شوند {TEX()} {m} {TEX} بنامیم و بیشترین تعداد 1هایی که هیچ دوتایی هم سطر و یا هم ستون نیستند را {TEX()} {M} {TEX}بنامیم آنگاه {TEX()} { m=M } {TEX}. + فرض کنید {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()} {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}@@ @@{TEX()} {U,V \subseteq P(X) \ , \ |X|=n} {TEX}@@
 با این شرط که  با این شرط که
 @@{picture=img/daneshnameh_up/c/c8/com0032f.jpg}@@  @@{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| \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}@@ @@{TEX()} {|U| \cdot |V| \ge 2^n|U \cap V|} {TEX}@@
 --- ---
-!!مسألهُ 6 +!!مسأله 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}.   {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: @#16:
- مجموعهُ {TEX()} {U} {TEX}و {TEX()} {V} {TEX}را به صورت زیر تعریف می کنیم: + مجموعه {TEX()} {U} {TEX}و {TEX()} {V} {TEX}را به صورت زیر تعریف می کنیم:
 @@{TEX()} {U=\{x|x\subseteq y \ , \ y \in F \}} {TEX}@@ @@{TEX()} {U=\{x|x\subseteq y \ , \ y \in F \}} {TEX}@@
 @@{TEX()} {V=\{x|y\subseteq x \ , \ 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} و نیز اگر  در این صورت اگر {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}@@ @@{picture=img/daneshnameh_up/3/38/com0032g.jpg}@@
   
-طبق قضیهُ گفته شده داریم: +طبق قضیه گفته شده داریم:
 @@{TEX()} {|U|\cdot |V| \ge 2^n|U\cap V|} {TEX}@@ @@{TEX()} {|U|\cdot |V| \ge 2^n|U\cap V|} {TEX}@@
-و چون اشتراک هر دو عضوی از {TEX()} {V} {TEX}ناتهی و اجتماع هر دو عضوی از {TEX()} {U} {TEX}، مخالف {TEX()} {X} {TEX}است داریم: +و چون اشتراک هر دو عضوی از {TEX()} {V} {TEX}ناتهی و ((اجتماع)) هر دو عضوی از {TEX()} {U} {TEX}، مخالف {TEX()} {X} {TEX}است داریم:
 @@{TEX()} {|U| \le 2^{n-1}} {TEX}@@ @@{TEX()} {|U| \le 2^{n-1}} {TEX}@@
 @@{TEX()} {|V| \le 2^{n-1}} {TEX}@@ @@{TEX()} {|V| \le 2^{n-1}} {TEX}@@
 و با توجه به اینکه {TEX()} {|F| \le |U \cap V|} {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()} {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}@@ @@{TEX()} {\Rightarrow \ |F| \le 2^{n-2}} {TEX}@@
 --- ---
 ! پیوند های خارجی ! پیوند های خارجی
 [http://Olympiad.roshd.ir/computer/content/pdf/0057.pdf] [http://Olympiad.roshd.ir/computer/content/pdf/0057.pdf]
- +---
!همچنین ببینید
*((نظریه گراف (المپیاد) ))
*((تعریف گراف ))
*((اعداد رمزی ))
 #@^ #@^

تاریخ شماره نسخه کاربر توضیح اقدام
 یکشنبه 14 آبان 1385 [11:16 ]   4   زینب معزی      جاری 
 یکشنبه 19 شهریور 1385 [09:24 ]   3   زینب معزی      v  c  d  s 
 یکشنبه 19 شهریور 1385 [09:21 ]   2   زینب معزی      v  c  d  s 
 پنج شنبه 16 شهریور 1385 [06:59 ]   1   زینب معزی      v  c  d  s 


ارسال توضیح جدید
الزامی
big grin confused جالب cry eek evil فریاد اخم خبر lol عصبانی mr green خنثی سوال razz redface rolleyes غمگین smile surprised twisted چشمک arrow



از پیوند [http://www.foo.com] یا [http://www.foo.com|شرح] برای پیوندها.
برچسب های HTML در داخل توضیحات مجاز نیستند و تمام نوشته ها ی بین علامت های > و < حذف خواهند شد..