جواب کار در کلاس صفحه 80 درس 3 ریاضیات گسسته (ترکیبیّات (شمارش))

مطابق شکل، مثلث را به 9 مثلث متساوی الاضلاع تقسیم می کنیم. حال 10 نقطه را کبوتر و هر مثلث کوچک را یک لانه فرض می کنیم (9 لانه داریم). طبق اصل لانه کبوتری حداقل دو کبوتر در یک لانه جای می گیرند، یعنی حداقل دو نقطه درون یک مثلث کوچک قرار خواهند گرفت.

از طرفی با توجه به این که طول اصلاع مثلث کوچک 1 واحد می باشد، فاصله بین دو نقطه درون یک مثلث از 1 واحد کمتر است.

سوال: 5 نقطه درون مربعی به ضلع 2 واحد مفروض است. ثابت کنید حداقل 2 نقطه بین این نقاط وجود دارد به طوریکه فاصله آن ها از یکدیگر کمتر از \(\sqrt 2 \) است.

اثبات: مطابق شکل  زیر  مربع را به چهار مربع یکسان ( به ضلع 1 واحد) تقسیم می کنیم. حال 5 نقطه را کبوتر و مربعات کوچک را به عنوان 4 لانه در نظر می گیریم. طبق اصل لانه کبوتری حداقل دو کبوتر در یک لانه واقع می شوند. یعنی حداقل دو نقطه مثل A و B یافت می شوند که در یک مربع کوچک قرار می گیرند.

حال با توجه به شکل، طبق قضیه فیثاغورث می توان نوشت:

\(\begin{array}{l}A{B^2} = A{C^2} + B{C^2}\;\;\mathop \Rightarrow \limits_{BC < 1}^{AC < 1} A{B^2} < {1^2} + {1^2}\\\\ \Rightarrow A{B^2} < 2 \Rightarrow AB < \sqrt 2 \end{array}\)

هر سال دارای 4 فصل است که آن ها را به عنوان 4 لانه و هر یک  از افراد خانواده را به عنوان یک کبوتر در نظر می گیریم. بنابراین می خواهیم حداقل 5 کبوتر را در 4 لانه جای دهیم که طبق اصل لانه کبوتری حداقل دو کبوتر یافت می شوند که در یک لانه جای گیرند، یعنی حداقل دو نفر از افراد خانواده وجود دارند که در یک فصل از سال متولد شده اند.

با توجه به راهنمایی داده شده مسئله را حل می کنیم:

حالت اول (اگر گراف فاقد رأس تنها باشد)، هر کدام از رئوس گراف را یک کبوتر و هر کدام از درجات 1 تا P-1 را یک لانه فرض می کنیم. بنابراین P کبوتر و P-1 تا لانه کبوتر داریم، که طبق اصل لانه کبوتری حداقل دو کبوتر وجود دارند که در یک لانه جای می گیرند، یعنی حداقل دو تا از رئوس دارای درجه یکسان می باشند.

حالت دوم ( اگر گراف دارای یک رأس تنها باشد )، درجه آن رأس تنها صفر می باشد، که با کنار گذاشتن آن، P-1 رأس داریم و آن ها را به عنوان کبوتر در نظر می گیریم.

از طرفی هر کدام از این رئوس می توانند درجات 1 تا P-2 داشته باشند، که اگر به عنوان لانه در نظر گرفته شوند، طبق اصل لانه کبوتری با وجود P-1 کبوتر و P-2 لانه، حداقل دو کبوتر یافت می شوند که در یک لانه جای گیرند. یعنی حداقل دو رأس وجود دارد که دارای درجه یکسانند.

و این که آیا نیازی هست حالتی را در نظر بگبربم که دو رأس یا بیشتر تنها باشند که در جواب این سوال باید بگوییم خیر، زیرا هر چه رأس تنها داشته باشیم، آن ها را کنار گذاشته و از تعداد رئوس و تعداد اعدادی که می توانند درجه ی آن ها محسوب شوند، به یک میزان کاسته می شود و همواره تعداد رئوس بیشتر از تعداد درجات است.