منو
 صفحه های تصادفی
ولادت پیامبر اکرم از زبان حضرت آمنه
مشبهات
ارتداد اسود عنسی و مبارزه ایرانیان با او
آنتونوف
فرهنگ استان سمنان
آزمایش غواص دکارتی
بخش بندی طلایی و نسبتهای کمی در عکاسی
تیره کوریاریاسه
1-دلیل عقلى محض
طراحی صحنه در تلویزیون
 کاربر Online
796 کاربر online
تاریخچه ی: دوگونه شمردن II

||V{maketoc}||
||__~~navy:@#13::: این مطلب از بخش آموزش وب‌سایت المپیاد ریاضی رشد،انتخاب شده که با فرمت pdf نیز در [http://olympiad.roshd.ir|وب‌سایت المپیاد رشد]موجود می‌باشد. برای مشاهده این موضوعات در وب‌سایت المپیاد، به آدرس [http://olympiad.roshd.ir/computercontentlist.html|فهرست مطالب کامپیوتر] مراجعه کنید. همچنین می‌توانید با کلیک ((مطالب علمی سایت المپیاد رشد|اینجا))‌ ، با ویژگی‌های بخش آموزش این وب‌سایت آشنا شوید.:: #@~~__||
^@#16:
!!مثال
در جمعی، {TEX()} {12k} {TEX}نفر حضور دارند. در این جمع، هر فرد{TEX()} {3k + 6} {TEX} فرد دیگر را می شناسد. همچنین، می دانیم تعداد افرادی که هر دو نفر ار می شناسند مقداری ثابت است. تعداد اعضای این جمع را به دست آورید.
__حل__
برای راحتی کار هر نفر را با یک نقطه (رأس) نشان می دهیم و اگر دو نفر با یکدیگر آشنا باشند یک پاره خط (یال) بین نقاط (رئوس) متناظر آنها رسم می کنیم. همچنین فرض می کنیم که تعداد آشناهای مشترک هر دو نفر مقدار ثابت {TEX()} {p} {TEX}باشد. به عبارت دیگر به ازای هر دو رأس {TEX()} {x} {TEX}و {TEX()} {y} {TEX}داریم{TEX()} {|N(x) \cap N(y)|=p} {TEX}. حال مقدار {TEX()} {k} {TEX}و {TEX()} {p} {TEX}را به دست می آوریم.
برای به دست آوردن تعداد اعضای این جمع لازم است که یک کمیت را دوبار بسماریم. برای این کار، ابتدا یک فرد (رأس) دلخواه مانند {TEX()} {x} {TEX}را در نظر یم گیریم. سپس تمام افرادی که این شخص را می شناسند، در مجموعه ی {TEX()} {B} {TEX} (مجموعه ی همسایه های رأس {TEX()} {x} {TEX}) و تمام افراد ناآشنا با فرد مورد نظر را در مجموعه ی {TEX()} {C} {TEX}جای می دهیم. حال، با توجه به شرایط مسئله، داریم:
@@{TEX()} {|B|=3k+6 \ , \ |C|=12k-(3k+6)-1=9k-7} {TEX}@@
::{picture=img/daneshnameh_up/8/83/com0038a.jpg}::
حالت تعداد رابطه های آشنایی (یال های) بین مجموعه افراد (رئوس) {TEX()} {B} {TEX}و مجموعه افراد (رئوس) {TEX()} {C} {TEX}را به دو طریق می شماریم.
فرض کنید {TEX()} {y} {TEX}یک رأس دلخواه از مجموعه ی {TEX()} {C} {TEX}باشد. طبق فرض مسئله تعداد همسایه های (آشناهای) مشترک {TEX()} {x} {TEX}و {TEX()} {y} {TEX}، برابر {TEX()} {p} {TEX}است. پس تعداد یال های یک همسایه ی مشترک {TEX()} {x} {TEX}و {TEX()} {y} {TEX}می باشد و بالعکس. در نتیجه تعداد یال های بین مجموعه ی {TEX()} {B} {TEX}و {TEX()} {C} {TEX}برابر است با
@@{TEX()} { p|C| = p(9k - 7).} {TEX} @@
حال فرض کنید {TEX()} {z} {TEX}یک رأس دلخواه از مجموعه ی {TEX()} {B} {TEX}باشد. طبق فرض مسئله تعداد همسایه های (آشناهای) مشترک {TEX()} {x} {TEX}و {TEX()} {z} {TEX}، برابر {TEX()} {p} {TEX}است. پس تعداد یال های بین رأس {TEX()} {z} {TEX}و مجموعه ی {TEX()} {B} {TEX}برابر {TEX()} {p} {TEX}است. ولی طبق فرض مسئله تعداد کل یال های مجاور رأس {TEX()} {z} {TEX} (مجموع یال های بین {TEX()} {z} {TEX}و مجموعه ی {TEX()} {B} {TEX}و یال های بین {TEX()} {z} {TEX}و مجموعه ی {TEX()} {C} {TEX}برابر{TEX()} {3k + 6 - p - 1 = 3k + 5 - p } {TEX} می باشد. در نتیجه تعداد یال های بین مجموعه ی {TEX()} {B} {TEX}و {TEX()} {C} {TEX}برابر است با
@@ {TEX()} { (3k + 5 - p)|B| = (3k + 5 - p)(3k + 6) } {TEX}@@
حال چون{TEX()} { (3k + 5 - p) (3k + 6) } {TEX}و{TEX()} { p(9k - 7) } {TEX} برابر تعداد یال های بین مجموعه {TEX()} {B} {TEX}و {TEX()} {C} {TEX}هستند، پس داریم:
@@{TEX()} {(3k+5-p)(3k+6)=p(9k-7)} {TEX}@@
@@{TEX()} {\Rightarrow \ -(3k+6)p+(3k+5)(3k+6)=(pk-7)} {TEX}@@
@@{TEX()} {\Rightarrow \ (12k-1)p=3(3k+5)(k+2)} {TEX}@@
@@{TEX()} {\Rightarrow \ p=3\times \frac{(3k+5)(k+2)}{12k-1} } {TEX}@@
با توجه به این که {TEX()} {p} {TEX}باید یک مقدار صحیح باشد، تنها جواب{TEX()} { k = 3 } {TEX}و{TEX()} { p = 6 } {TEX}است. در نتیجه تعداد افراد این جمع 36 نفر است.
همچنین به راحتی می توانید وجود جواب را برای 36 نفر امتحان کنید. گرافی 36 رأسی با شرایط مسئله بسازید.
---
!اثبات نامساوی های ترکیباتی
#@
@#16:
تا کنون از دوگونه شمردن برای اثبات تساوی های ترکیباتی و به دست آوردن مقدار یک کمیت ترکیباتی استفاده کردیم. حال به بررسی مسایلی می پردازیم که در آنها با استفاده از دوگونه شمردن نامساوی های ترکیباتی را اثبات می کنیم.
---
!!مثال
فرض کنید {TEX()} {S} {TEX}مجموعه ای از {TEX()} {n} {TEX}نقطه در صفحه باشد به طوری که
•هیچ سه نقطه ای بر یک استقامت نیستند.
•به ازای هر نقطه ی {TEX()} {P} {TEX}از مجموعه ی {TEX()} {S} {TEX}، حداقل {TEX()} {k} {TEX}نقطه از {TEX()} {S} {TEX}یافت می شوند که از {TEX()} {P} {TEX}به یک فاصله اند.
ثابت کنید{TEX()} {k < \frac{1}{2}+\sqrt{2n}} {TEX}.
__حل__
تعداد کل پاره خط هایی که از دو نقطه از نقاط {TEX()} {S} {TEX}می گذرند را به دو طریق می شماریم. چون به ازای هر دو نقطه ای دقیقاً یک پاره خط وجود دارد، پس تعداد این پاره خطوط برابر است با{TEX()} {n\choose 2} {TEX}.
حال برای هر نقطه مانند {TEX()} {P} {TEX}از این {TEX()} {n} {TEX}نقطه، حداقل {TEX()} {k} {TEX}نقطه وجود دارد که از آن به یک فاصله اند. پس این {TEX()} {k} {TEX}نقطه روی دایره ای به مرکز {TEX()} {P} {TEX}قرار دارند و{TEX()} {k \choose 2} {TEX} پاره خط را مشخص می کنند. حال چون به ازای هر نقطه حداقل{TEX()} {k \choose 2} {TEX} ((پاره خط)) وجود دارد، پس تعداد پاره خط ها حداقل{TEX()} {n{k\choose 2}} {TEX} است. اما در این بین از طرف دیگر هر خط را حداکثر دوبار شمرده ایم. زیرا اگر یک پاره خط را بیش از دوبار شمرده باشیم باید دوسر این پاره خط روی حداقل سه دایره قرار گرفته باشند. از طرف دیگر می دانیم که مرکز این ((دایره)) ها روی ((عمود منصف)) این پاره خط قرار دارد. پس سه نقطه پیدا کردیم که بر یک استقامتند. ولی این با فرض مسئله در تناقض است. در نتیجه هر پاره خط را حداکثر دوبار شمرده ایم. پس داریم:
@@{TEX()} {\frac{1}{2}n {k\choose 2} \le {n\choose 2}} {TEX}@@
@@{TEX()} {\Rightarrow \ \frac{nk(k-1)}{2} \le n(n-1)} {TEX}@@
@@{TEX()} {\Rightarrow \ k^2-k-2(n-1) \le 0} {TEX}@@
@@{TEX()} {\Rightarrow \ k \le \frac{1+\sqrt{1+8(n-1)}}{2}} {TEX}@@
@@{TEX()} {\Rightarrow \ k <\frac{1}{2}+\frac{1}{2}\sqrt{8n}=\frac{1}{2}+\sqrt{2n}} {TEX}@@
---
!!مثال
فرض کنید {TEX()} {G} {TEX}یک ((گراف ساده)) با {TEX()} {n} {TEX}رأس و {TEX()} {m} {TEX}یال باشد. اگر{TEX()} {m>\frac{n}{4} (1+\sqrt{4n-3})} {TEX} باشد، ثابت کنید {TEX()} {G} {TEX}دوری به طول 4 دارد.
__حل__
از برهان خلف استفاده می کنیم. فرض کنید این گراف هیچ دوری به طول 4 نداشته باشد. حال برای حل این مسئله و دسیدن به تناقض تعداد جفت های متمایز رئوس را به دو طریق می شماریم. از یک طرف این مقدار برابر است با{TEX()} {n\choose 2} {TEX}.
از طرف دیگر فرض کنید{TEX()} { N(x)} {TEX} مجموعه رئوس متصل به رأس {TEX()} {x} {TEX} (مجموعه ی همسایه های {TEX()} {x} {TEX}) باشد. واضح است که{TEX()} {|N(x)|=d(x)} {TEX}. حال به ازای هر دو رأس دلخواه {TEX()} {x} {TEX}و {TEX()} {y} {TEX}،{TEX()} {|N(x) \cap N(y)| \le 1} {TEX}. زیرا اگر دو رأس {TEX()} {x} {TEX}و {TEX()} {y} {TEX}، دو همسایه مشترک مانند {TEX()} {u} {TEX}و{TEX()} {v} {TEX} داشته باشند، دورxuyvx یک دور به طول 4 است و این برخلاف فرض است. پس هر د رأسی حداکثر یک همسایه ی مشترک دارند. حال به ازای هر رأس دلخواهی مانند {TEX()} {x} {TEX}، تعداد جفت رأس های همسایه ی {TEX()} {x} {TEX}برابر است با{TEX()} {{{|N(x)|} \choose 2}={{d(x)}\choose 2}} {TEX} و چون هیچ دو رأسی بیش از یک همسایه ی مشترک ندارند، پس تعداد جفت رأس های متمایز این گراف حداقل برابر است با{TEX()} {\sum_{x\in V(G)} {{d(x)}\choose 2}} {TEX}. حال با توجه به این که تعداد جفت رأس های متمایز برابر{TEX()} {n \choose 2} {TEX} است داریم:
#@
@#16:
@@{TEX()} {\sum_{x\in V(G)} {{d(x)} \choose 2} \le {n \choose 2}} {TEX}@@
حال با استفاده از نامساوی «((ین سن))» داریم:
@@{TEX()} {{n\choose 2} \ge \sum_{x\in V} {{d(x)}\choose 2} \ge n {{\frac{2m}{n}}\choose 2}} {TEX}@@
@@{TEX()} {\Rightarrow \ {n\choose 2} \ge \frac{m(2m-n)}{n}} {TEX}@@
@@{TEX()} {\Rightarrow 2m^2-nm-\frac{n^2(n-1)}{2} \le 0} {TEX}@@
@@{TEX()} {\Rightarrow \ m\le \frac{n+\sqrt{n^2+4n^2(n-1)}}{4}=\frac{n}{4} (1+\sqrt{4n-3})} {TEX}@@
و این برخلاف فرض مسئله است و به تناقض رسیدیم. پس این ((گراف دوری)) به طول 4 دارد.
---
!!مثال
فرض کنید {TEX()} {G} {TEX}یک گراف ساده با {TEX()} {n} {TEX}رأس و {TEX()} {m} {TEX}یال باشد. ثابت کنید این گراف حداقل{TEX()} {\frac{4m}{3n} \Big(m-\frac{n^2}{4} \Big)} {TEX} ((مثلث)) (دور به طول 3) دارد.
__حل__
در این مسئله، به جای شمردن مستقیم تعداد مثلث ها، سعی می کنیم مثلث هایی را که به صورت اجباری به وجود می آیند بشماریم.
فرض کنید {TEX()} {S} {TEX}تعداد مثلث های گراف {TEX()} {G} {TEX}باشد. اگر{TEX()} { N(x) } {TEX} مجموعه ی همسایه های رأس {TEX()} {x} {TEX}باشد، به ازای هر یال دلخواه{TEX()} {xy \in E(G)} {TEX} داریم:
@@{TEX()} {|N(x) \cap N(y)|=|N(x)|+|N(y)|-|N(x) \cup N(y)| \ge d(x)+d(y)-n} {TEX}@@
بنابراین به ازای هر دو رأس مجاور در {TEX()} {G} {TEX}، حداقل{TEX()} { d(x) + d(y) - n } {TEX} رأس داریم که همسایه ی مشترک {TEX()} {x} {TEX}و {TEX()} {y} {TEX}هستند. در نتیجه تعداد مثلث هایی که شامل یال {TEX()} {xy} {TEX}هستند حداقل{TEX()} { d(x) + d(y) - n } {TEX} خواهد بود. حال چون هر مثلث سه یال دارد، در نتیجه
@@{TEX()} {S \ge \frac{1}{3} \sum_{xy \in E(G)} (d(x)+d(y)-n)} {TEX}@@
حال برای ساده کردن عبارت{TEX()} {\sum_{xy \in E(G)} (d(x)+d(y)-n)} {TEX} از تکنیک آشنای خود یعنی دو گونه شمردن استفاده می کنیم. برای این کار کافی است به این نکته توجه کنیم که به ازای هر رأس {TEX()} {x} {TEX}، {TEX()} { d(x) } {TEX} دقیقاً {TEX()} { d(x) } {TEX} بار در مجموع فوق ظاهر می شود. بنابراین داریم:
@@{TEX()} {S \ge \frac{1}{3} \sum_{xy \in E(G)} (d(x)+d(y)-n)=\frac{1}{3} \Big[ \sum_{x\in V(G)} (d(x))^2-mn \Big]} {TEX}@@
---
!!مثال
#@
@#16:
{TEX()} {n} {TEX}نقطه در صفحه داده شده اند. نشان دهید که کم تر از{TEX()} {n\sqrt{n}} {TEX} جفت از این نقاط وجود دارند، به طوری که فاصله ی بین هر جفت برابر یک سانتی متر باشد.
__حل__
آری باز هم از دوست آشنای خود استفاده خواهیم کرد. ولی این بار چطور؟
فرض کنید{TEX()} {S=\{P_1,P-2,\cdots ,P-n \}} {TEX}، مجموعه ی نقاط مفروض باشد. همچنین فرض کنید{TEX()} {a_i} {TEX}، تعداد نقاطی از {TEX()} {S} {TEX}باشد که فاسله ی آنها از{TEX()} {P_i} {TEX} برابر یک سانتی متر است. در نتیجه تعداد جفت نقاط مورد نظر برابراست با:
@@{TEX()} {m=\frac{1}{2} \sum_{i=1}^n a_i =\frac{a_1+a_2+\cdots +a_n}{2}} {TEX}@@
حال فرض کنید{TEX()} {C_i} {TEX} دایره ای به شعاع یک سانتی متر و به مرکز{TEX()} {P_i} {TEX} باشد. هر دو دایره ای را که از بین این دایره ها (دایره های{TEX()} {C_1} {TEX}،{TEX()} {C_2} {TEX}، ...، {TEX()} {C_n} {TEX}) در نظر بگیریم حداکثر در دو نقطه یکدیگر را قطع می کنند. بنابراین تعداد نقاط برخورد دایره ها حداکثر{TEX()} {2{n\choose 2}=n(n-1)} {TEX} می باشد. حال بیایید نقاط تقاطع دایره ها را به یک طریق دیگر بشماریم:
برای هر نقطه ی{TEX()} {P_i} {TEX}،{TEX()} {{a_i}\choose 2} {TEX} دایره وجود دارد که{TEX()} {P_i} {TEX} نقطه ی برخورد آنها است. (چرا؟) بنابراین حداقل نقاط برخورد دایره ها برابر است با{TEX()} {\sum_{i=1}^n {{a_i}\choose 2}} {TEX}. ولی حداکثر تعداد نقاط برخورد دایره ها نیز برابر است با{TEX()} { n(n – 1)} {TEX}. در نتیجه داریم:
@@{TEX()} {n(n-1) \ge \sum_{i=1}^n {{a_i}\choose 2}=\frac{1}{2} \sum_{i=1}^n a_i^2 - \sum_{i=1}^n a_i} {TEX}@@
@@{TEX()} { \Rightarrow 2n(n-1)+2m \ge \sum_{i=1}^n a_i^2} {TEX}@@
با استفاده از ((نامساوی کوشی- شوارتز)) داریم:
@@{TEX()} {2n(n-1)+2m \ge \sum_{i=1}^n a_i^2 \ge \frac{1}{n} \Bigg( \sum_{i=1}^n a_i \Bigg)^2=\frac{4m^2}{n}} {TEX}@@
@@{TEX()} {\Rightarrow \ 2m^2-nm-n^2(n-1) \le 0} {TEX}@@
@@{TEX()} {\Rightarrow \ m \le \frac{n+\sqrt{8n^3-7n^2}}{4}<n\frac{1+\sqrt{8n}}{4}} {TEX}@@
@@{TEX()} {\Rightarrow \ m<n\frac{\sqrt{n}+3\sqrt{n}}{4}=n\sqrt{n}} {TEX}@@
---
!!مثال
#@
@#16:
در یک {TEX()} {n} {TEX}ضلعی ((محدب))، تمام قطرها را رسم کرده این. اگر هیچ سه قطری همرس نباشند، {TEX()} {n} {TEX}ضلعی به چند ناحیه تقسیم می شود؟
__حل__
__ روش اول__ این مسئله، یکی از زیباترین مسایلی است که با استفاده از این تکنیک حل می شود. در این مسئله، {TEX()} {n} {TEX}ضلعی را به نواحی ای تقسیم کرده این. حال فرض کنید که تعداد سه ضلعی های به دست آمده را{TEX()} {p_3} {TEX}، تعداد چهار ضلعی های به دست آمده را{TEX()} {p_4} {TEX} و ... و بالاخره به تعداد {TEX()} {k} {TEX}ضلعی های به دست آمده را{TEX()} {p_k} {TEX} بگیریم. ({TEX()} {k} {TEX}حداکثر چه مقداری می تواند باشد؟) بنابراین مسئله از ما خواسته است که مقدار{TEX()} {m=p_1+p_2+\cdots +p_k} {TEX} را به دست آوریم. ابتدا تعداد نقطه های داخلی را- که محل برخورد قطرهای {TEX()} {n} {TEX}ضلعی محدب می باشند- تعیین می کنیم. به ازای هر چهار رأس از رئوس {TEX()} {n} {TEX}ضلعی دقیقاً یک نقطه ی تقاطع داخلی وجود دارد. بنابراین تعداد نقطه های داخلی برابر است با{TEX()} {n\choose 4} {TEX}. حال مجموع زوایای داخلی را به دو روش می شماریم؛ از یک طرف، این مقدار برابر است با مجموع زوایای داخلی تمام نواحی ایجاد شده:
@@{TEX()} {180 \big[ p_3(3-2)+p_4(4-2)+\cdots +p_k(k-2) \big]=180 \big(3p_3+4p_4+\cdots kp_k -2m} {TEX}@@
و از طرف دیگر، می توان گفت که هر نقطه ی داخلی، به اندازه ی 360 درجه به مجموع زوایا اضافه می کند و علاوه بر نقاط داخلی، رئوس {TEX()} {n} {TEX}ضلعی نیز مجموعاً به اندازه ی {TEX()} {180(n – 2)} {TEX} درجه در مجموع زوایا سهم دارند. بنابراین، مجموع زوایای نواحی برابر است با:
@@{TEX()} {{n\choose 4}\times 360+(n-2) \times 180} {TEX}@@
در نتیجه:
(1) @@ {TEX()} {3p_3+4p_4+\cdots +kp_k-2m=2\times {n\choose 4} +(n-2)} {TEX}@@
حال مجموع رئوس تمام نواحی از یک طرف برابر با{TEX()} {3p_3+4p_4+\cdots +kp_k} {TEX} خواهد بود، و از طرف دیگر می توان گفت که رئوس داخلی، در 4 ناحیه و رئوس {TEX()} {n} {TEX}ضلعی در{TEX()} { n – 2 } {TEX} ناحیه شمرده می شوند. (چرا؟) بنابراین:
(2)@@ {TEX()} {3p_3+4p_4+\cdots +kp_k={n\choose 4} \times 4 +n(n-2)} {TEX}@@
حال از روابط (1) و (2) به دست می آوریم که:
@@{TEX()} {2m=2\times {n\choose 4}+(n-1)(n-2) \ \Rightarrow \ m={n\choose 4}+{{n-1}\choose 2}} {TEX}@@
__روش دوم.__ تعداد نقاط تلاقی قطرها داخل {TEX()} {n} {TEX}ضلعی برابر است با{TEX()} {n\choose 4} {TEX}. پس یک گراف مسطح{TEX()} {V=n+{n\choose 4}} {TEX} رأسی داریم که درجه ی {TEX()} {n} {TEX}رأس آن برابر{TEX()} { n – 1 } {TEX}و درجه ی{TEX()} {{n\choose 4}} {TEX} رأس دیگر آن برابر 4 است. پس تعداد یال های این ((گراف)) برابر است با{TEX()} {E=\frac{n(n-1)}{2}+2{n\choose 4}} {TEX}.
حال طبق قضیه ی اویلر در گراف های مسطح می دانیم{TEX()} { V + F = E + 2} {TEX}. پس
@@{TEX()} {F=E-V+2=\frac{n(n-1)}{2}+2{n\choose 4}-{n\choose 4}-n+2} {TEX}@@
@@{TEX()} {=\frac{(n-1)(n-2)}{2}+{n\choose 4}+1={{n-1}\choose 2}+{n\choose 4}+1} {TEX}@@
ولی یکی از این نواحی، ناحیه ی خارجی است. پس تعداد نواحی داخلی {TEX()} {n} {TEX}ضلعی برابر است با{TEX()} {{{n-1}\choose 2}+{n\choose 4}} {TEX}.
---
!!مثال. قضیه ی sperner
#@
@#16:
فرض کنید که {TEX()} {X} {TEX}یک مجموعه ی {TEX()} {n} {TEX}عضوی و{TEX()} {G=\{A_1,A_2,\cdots , A_p \}} {TEX} یک خانواده از زیر مجموعه های {TEX()} {X} {TEX}باشد، به طوری که برای هر{TEX()} {i \neq j \ , \ i,j=1,2,\cdots ,p} {TEX} داشته باشیم:{picture=img/daneshnameh_up/5/5d/com0038aa.jpg} . ثابت کنید که {TEX()} {p} {TEX}حداکثر برابر است با{TEX()} {{n\choose{\Big[ \frac{n}{2} \Big] }} {TEX}.
__اثبات__
دنباله ی{TEX()} {M_1,M_2,\cdots ,M_n} {TEX} از زیر مجموعه های {TEX()} {X} {TEX}را، یک زنجیره به طول {TEX()} {n} {TEX}می نامیم هرگاه:
@@{TEX()} {M_1\subset M_2 \subset M_3 \subset \cdots \subset M_{n-1} \subset M_n=X} {TEX}@@
و به ازای هر{TEX()} {1 \le i \le n} {TEX}، داشته باشیم{TEX()} {|M_i|=i} {TEX}.
تعداد زنجیره های به طول {TEX()} {n} {TEX}که از زیر مجموعه های یک مجموعه ی {TEX()} {n} {TEX}عضوی تشکیل شده باشند برابر است با {TEX()} {n!} {TEX} (چرا؟) حال اگر{TEX()} {A \subseteq X} {TEX} و{TEX()} {|A| = r } {TEX} باشد، تعداد زنجیره های به طول {TEX()} {n} {TEX}که شامل A باشند برابر است با{TEX()} { r!(n – r)!.} {TEX} زیرا اگر دنباله ی
@@{TEX()} {M_1 \subset M_2 \subset \cdots \subset M_{r-1} \subset A \subset M_{r+1} \subset \cdots \subset M_n} {TEX}@@
زنجیره ی مورد نظر باشد، {TEX()} {M_1,M_2,\cdots ,M_{r-1},A} {TEX}،{TEX()} {r!} {TEX}حالت و دنباله ی{TEX()} {A,M_{r+1},M_{r+2} , \cdots , M_n} {TEX}،{TEX()} { (n – r)! } {TEX}حالت دارند.
اگر{TEX()} {A_i} {TEX} و{TEX()} {A_j} {TEX} هیچ یک زیر مجموعه ی هم نباشند، هر زنجیره که شامل{TEX()} {A_i} {TEX} است، نمی تواند شامل{TEX()} {A_j} {TEX} نیز باشد و برعکس. بنابراین اگر{TEX()} {(i=1,2,3,\cdots , p) \ |A_i|=n_i} {TEX} با توجه به خاصیت {TEX()} {G} {TEX}می توان گفت:
@@{TEX()} {\sum_{i=1}^p n_i!(n-n_i)! \le n!} {TEX}@@
@@{TEX()} {\Rightarrow \sum_{i=1}^p \frac{n_i(n-n_i)!}{n!}} {TEX}@@
@@{TEX()} {\Rightarrow \ \sum_{i=1}^p \frac{1}{n\choose{n_i}} \le 1} {TEX}@@
و چون بیش ترین مقدار{TEX()} {n\choose{n_i}} {TEX}، برابر است با{TEX()} {n\choose {\Big[\frac{n}{2} \Big]}} {TEX}. بنابراین:
@@{TEX()} {\sum_{i=1}^p \frac{1}{n\choose{n_i}} \le 1 \ \Rightarrow \frac{p}{n\choose {\Big[ \frac{n}{2} \Big] }} \le 1 \ \Rightarrow \ p \le {n\choose {\Big[ \frac{n}{2} \Big] }}} {TEX}@@
و این همان حکم خواسته شده است. حال، برای این که ثابت کنیم یک چنین خانواده ای در {TEX()} {G} {TEX}وجود دارد، کافی است که {TEX()} {G} {TEX}را مجموعه ی تمام زیر مجموعه های{TEX()} {\Big[ \frac{n}{2} \Big]} {TEX} عضوی {TEX()} {X} {TEX}بگیریم. واضح است که این خانواده دارای خاصیت خواسته شده است.
---
!!مثال
فرض کنید {TEX()} {p} {TEX}عددی اول باشد و داشته باشیم:
@@{picture=img/daneshnameh_up/7/7d/com0038b.jpg}@@

ثابت کنید که رابطه ی هم نهشتی زیر برقرار است:
@@{TEX()} {{m\choose n}={a\choose c}{b\choose d} \qquad (mod \ p)} {TEX}@@
__حل__
ابتدا توجه کنید که اگر{TEX()} { m < n } {TEX} باشد، در آن صورت{TEX()} { a < c } {TEX} و یا{TEX()} { b < d } {TEX}. در هر دو صورت هر دو طف همنهشتی برابر صفر خواهند شد. پس فرض می کنیم{TEX()} {m\ge n} {TEX} باشد. در نتیجه{TEX()} {a \ge c} {TEX}. (چرا؟)
یک جدول{TEX()} {(a+1) \times p} {TEX} خانه ای را در نظر بگیرید که از سطر آخر آن به اندازه ی{TEX()} { p – b } {TEX} خانه، بریده شده است.
#@
@#16:
::{picture=img/daneshnameh_up/6/6b/com0038c.jpg}::
اکنون قصد داریم {TEX()} {n} {TEX}خانه از این جدول را که دارای {TEX()} {m} {TEX}خانه است، با رنگ آبی و بقیه ی خانه ها را با رنگ قرمز رنگ آمیزی کنیم. همان طور که می دانید این کار را به{TEX()} {m\choose n} {TEX} طریق می توان انجام داد. اگر در یک رنگ آمیزی از یک سطر جدول،{TEX()} {(0 <x<p) \ x} {TEX} خانه رنگ شده باشد، چون خود این {TEX()} {x} {TEX}خانه را به{TEX()} {p\choose x} {TEX} طریق می توان رنگ کرد و این مقدار بر {TEX()} {p} {TEX}بخش پذیر است (چرا؟) پس در این حالت، تعداد راه های رنگ کردن کل جدول نیز بر {TEX()} {p} {TEX}بخش پذیر است. به عبارت دیگر تعداد راه هایی که این جدول می تواند رنگ شود به طوری که حداقل یکی از سطرهای 1 تا {TEX()} {a} {TEX}آن به طور کامل آبی شده باشد و نه به طور کامل قرمز شده باشد، بر {TEX()} {p} {TEX}بخش پذیر است. در نتیجه می توان فرض کرد که هر یک از سطرهای 1 تا {TEX()} {a} {TEX}یا به طور کامل به رنگ آبی هستند یا به طور کامل به رنگ قرمز هستند. حال در این حالت چون در سطر آخر {TEX()} { b < p } {TEX} خانه موجو است، دقیقاً {TEX()} {c} {TEX}سطر از {TEX()} {a} {TEX}سطر اول و {TEX()} {d} {TEX}خانه از {TEX()} {b} {TEX}خانه ی سطر آخر را باید با رنگ آبی رنگ آمیزی کرد. در نتیجه این کار را به{TEX()} {{a\choose c}{b\choose d}} {TEX} طریق می توان انجام داد. تعداد بقیه ی حالات رنگ آمیزی صفحه نیز بر {TEX()} {p} {TEX}بخش پذیر بود. درنتیجه باید بای مانده ی{TEX()} {{a\choose c}{b\choose d}} {TEX} و{TEX()} {m\choose n} {TEX} بر {TEX()} {p} {TEX}یکسان باشد. پس حکم ثابت شد.
---
! پیوند های خارجی
[http://Olympiad.roshd.ir/computer/content/pdf/0142.pdf]
---
!همچنین ببینید
*((دوگونه شمردن I ))
*((اصل اکسترمال ))
#@^

تاریخ شماره نسخه کاربر توضیح اقدام
 یکشنبه 14 آبان 1385 [11:42 ]   3   زینب معزی      جاری 
 یکشنبه 19 شهریور 1385 [11:14 ]   2   زینب معزی      v  c  d  s 
 پنج شنبه 16 شهریور 1385 [07:49 ]   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 در داخل توضیحات مجاز نیستند و تمام نوشته ها ی بین علامت های > و < حذف خواهند شد..