المپدیا

دانش‌نامه‌ی المپیاد کامپیوتر ایران

ابزار کاربر

ابزار سایت


آموزش:ترکیبیات:اصل لانه کبوتری

اصل لانه‌کبوتری

اصل لانه‌کبوتری یکی از ساده‌ترین ابزارها برای حل مسائل ترکیبیاتی است. دلیل استفاده‌ی «اصل» به جای «قضیه» نیز همین است، چون صورت این حکم بدیهی به نظر می‌آید.

صورت ساده

ساده‌ترین حکم از اصل لانه‌کبوتری بصورت زیر است:

اگر n+1 کبوتر در n لانه قرار بگیرند، حداقل در یک لانه بیش از یک کبوتر قرار دارد.

این اصل را اولین بار دیریکله در سال 1834 میلادی برای حل یک مسئله‌ی نظریه‌اعداد بکار کرد. او این اصل را «اصل قفسه» نامید.

یکی دیگر از ریاضیدانانی که در گسترش این اصل تاثیرگذار بود، فرانک رمزی است. شهرت او بواسطه‌ی تلاش‌هایی است که در خصوص دسته‌ای از مسائل در ترکیبیات صورت داده است. در حل این مسائل به کرات از اصل لانه‌کبوتری استفاده شده و باعث ظهور اعدادی به نام «اعداد رمزی» در ترکیبیات شده‌اند. امروزه کاربرد این اصل در علوم کامپیوتر به اثبات رسیده و مسائل و الگوریتم‌های زیادی از این اصل و یا تعمیم‌های آن استفاده می‌کنند.

با اینکه این اصل صورت ساده‌ای دارد، مسائل گسترده و بعضا پیچیده‌ای با آن حل می‌شوند. معمولا می‌توان فهمید که چه زمانی باید از اصل لانه‌کبوتری استفاده کرد، ولی اینکه کبوتر و لانه در مسئله چگونه تعریف بشوند می‌تواند کار سختی باشد و یا محاسبات بیشتری را بطلبد.

چند مثال

با چند مثال کار را ادامه می‌دهیم:

مثال: 11 عدد طبیعی داریم. ثابت کنید رقم یکان دو تا از آنها یکسان است.

پاسخ

می‌دانیم یکان هر عدد 10 حالت مختلف (رقمی بین 0 تا 9) می‌تواند داشته باشد. در این مسئله 11 عدد (کبوتر) باید یکی از 10 حالت ممکن (لانه) را داشته باشند. چون 11 > 10، طبق اصل لانه‌کبوتری حداقل 2 عدد هستند که رقم یکان یکسانی دارند.

مثال: در یک مهمانی $n$ نفر حضور دارند. هر دو نفر حداکثر یک بار باهم دست داده‌اند. ثابت کنید دو نفر هستند که به تعداد یکسان با بقیه دست داده‌اند.

پاسخ

برای هر نفر، تعداد دفعاتی که دست داده را یادداشت می‌کنیم. بدین ترتیب $n$ عدد نوشته می‌شود که همگی آنها بین 0 تا $n-1$ هستند. ولی همزمان نمی‌توانیم هم عدد 0 و هم عدد $n-1$ را داشته باشیم، چون اگر شخصی با $n-1$ نفر دست داده باشد یعنی با همه‌ی افراد دست داده و بنابراین فردی وجود ندارد که 0 بار دست داده باشد.

پس $n$ عدد خواهیم داشت که می‌توانند $n-1$ حالت مختلف داشته باشند و بنابراین طبق اصل لانه کبوتری دو تا از آنها با هم برابر خواهند بود.

مثال: فرض کنید $n+1$ عدد از مجموعه‌ی $\{ 1, 2, ..., 2n \}$ انتخاب کرده‌ایم. ثابت کنید دو تا از آنها نسبت به هم اول هستند.

پاسخ

در این مسئله از روشی استفاده می‌کنیم که در حل بسیاری از سوالات لانه کبوتری کاربرد دارد.

ابتدا اعضای مجموعه را به $n$ دسته تقسیم می‌کنیم که اعضای هر دسته نسبت به هم اول باشند. چون $n+1$ عدد انتخاب شده، طبق اصل لانه کبوتری حداقل دو عدد در یک دسته قرار دارند و در نتیجه آن دو نسبت به هم اول خواهند بود.

پس باید بتوانیم اعداد 1 تا $2n$ را در $n$ دسته با ویژگی گفته شده قرار دهیم. می‌دانیم هر دو عدد متوالی نسبت به هم اول هستند، پس دسته‌بندی بدین صورت انجام می‌شود: $\{ \{1, 2 \}, \{3, 4 \}, ... \{2n-1, 2n \} \}$.

مثال: ثابت کنید هر عددی همانند $n$ مضربی دارد که تنها از رقم‌های صفر و یک تشکیل شده است.

پاسخ

دنباله‌ای از اعداد را بدین ترتیب تعریف می‌کنیم: $A = \{ A_1, A_2, ... A_n \}$ که در آن $A_i = \underbrace{11 ... 11}_{i}$. اگر یکی از اعضای آن بر $n$ بخش‌پذیر باشد مسئله حل شده است. در غیر اینصورت باقیمانده‌ی آنها بر $n$ یکی از اعداد 1 تا $n-1$ خواهد بود. چون $A$ در مجموع $n$ عضو دارد طبق اصل لانه‌کبوتری دو عدد از اعضای $A$ وجود دارند که باقیمانده‌ی یکسانی بر $n$ داشته باشند (مثلا $A_i < A_j$). در نتیجه در این حالت نیز $A_j - A_i = \underbrace{11 ... 11}_{j - i} \underbrace{00 ... 00}_{i}$ بر $n$ بخش‌پذیر (مضرب $n$) است و تنها از ارقام صفر و یک تشکیل شده است.

مسائل نمونه

  • سوال 9 مرحله اول دوره‌ی 10

ابزار صفحه