Processing math: 37%

المپدیا

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

ابزار کاربر

ابزار سایت


آموزش:ترکیبیات:معادلات خطی با ضرایب واحد

معادلات خطی با ضرایب واحد

شرح مساله

معادله زیر را در نظر بگیرید که شامل k متغیر و عدد ثابت n می‌باشد.

x1+x2+...+xk=n در حالت کلی، به دنبال یافتن تعداد xiهایی هستیم که معادله فوق را ارضا کنند. اگر هیچ شرطی روی متغیرها اعمال نشود، تعداد پاسخ‌های معادله بی‌نهایت است، زیرا می‌توان از اعداد حقیقی استفاده کرد. بنابراین در اکثر مواقع، با توجه به مساله ترکیبیاتی‌ای که در دست هست، شروطی روی xiها در نظر گرفته می‌شود. برای درک بهتر موضوع، به مثال زیر توجه کنید.

مثال:

تعداد جواب‌های معادله‌ی x1+x2=6 چند تا است به شرطی که x1 و x2 اعدادی طبیعی باشند.

پاسخ

می‌توان مشاهده کرد که تعداد حالات ۵ تا است. کافی است x1 را عددی بین ۱ تا ۵ انتخاب کنید، آنگاه x2 به صورت یکتا انتخاب می‌شود و x2=6x1 خواهد بود.

روش کلی حل این معادلات در ادامه به تفصیل بیان خواهند شد. در ادامه ابتدا مثالی می‌بینیم از کاربرد این معادلات تا انگیزه‌ای ایجاد شود که این مسائل می‌توانند بسیار در حل مسائل ترکیبیاتی مفید باشند.

مثال:

۱۰ توپ یکسان داریم و می‌خواهیم آن‌‌ها را بین علی و رضا و سارا تقسیم کنیم. به چند طریق می‌توان این کار را انجام داد؟ دقت کنید که همه‌ی توپ‌ها باید تقسیم شوند و توپی را دور نمی‌اندازیم.

پاسخ

اگر توپ‌ها یکسان نبودند، پاسخ مساله برابر بود با 310 زیرا برای هر توپ ۳ حالت داریم که به چه کسی برسد. اما در این مساله، توپ‌ها یکسان هستند. بنابراین تنها چیزی که مهم است، تعداد توپ‌هایی هست که به هر نفر رسیده. اکنون برای هر کدام از این سه نفر، یک متغیر تعریف کنید که نشان دهنده تعداد توپ‌هایی است که به این شخص رسیده.

سپس یک معادله تشکیل دهید که جمع این سه متغیر برابر با تعداد توپ‌ها باشد: xali+xsara+xreza=10

شرطی که باید روی متغیرها بگذاریم، این است که هر کدام از متغیرها باید در اعداد حسابی باشند (اعداد حسابی شامل صفر هستند). پس تعداد جواب‌های معادله فوق، برابر با تعداد حالات مساله ترکیبیاتی ما است. سعی کنید به کمک مبحث تناظر یک به یک این مطلب را اثبات کنید.

در ادامه، به دنبال حل مساله فوق خواهیم بود. به عبارتی، با دریافت عدد ثابت n، تعداد متغیرها و شروطی که روی متغیرها گذاشته شده، تعداد جواب‌های معادله را پیدا می‌کنیم.

از آنجا که با توجه به هر مساله می‌توان شروط متنوعی روی متغیرها گذاشت، در اینجا فقط به دو حالت رایج می‌پردازیم. حالت اول این است که متغیرها اعداد طبیعی باشند. حالت دوم که بالاتر در مثال ظاهر شد، این است که متغیرها اعداد حسابی باشند. حالت اول را اثبات می‌کنیم و حالت دوم را به عنوان یک سوال مطرح می‌کنیم که می‌توان از حالت اول آن را بدست آورد.

حل یک نمونه رایج از مساله

در حالتی کلی، فرض کنید معادله x1+x2+...+xk=n

داده شده که n,k اعدادی ثابت و داده شده هستند. به دنبال یافتن تعداد جواب‌های معادله فوق هستیم به طوری که xiها اعدادی طبیعی باشند. برای راحتی کار فرض کنید nk است (در غیر اینصورت تعداد جواب‌ها صفر است، چون سمت چپ معادله حداقل به اندازه k می‌باشد).

ادعا می‌کنیم تعداد جواب‌های معادله فوق برابر است با \binom{n - 1}{k - 1}. اثبات این ادعا سخت نیست. سعی کنید قبل از اینکه پاسخ را ببینید، خودتان سعی کنید آن را ثابت کنید.

پاسخ

از تناظر یک به یک استفاده می‌کنیم. یک مساله جدید تعریف می‌کنیم و سپس نشان می‌دهیم یک تناظر یک به یک بین این مساله و مساله خودمان برقرار است.

مساله جدید: فرض کنید n توپ در یک ردیف قرار دارند. می‌خواهیم k - 1 جدا کننده بین توپ‌ها بگذاریم به نحوی که شرایط زیر برقرار باشند:

  • بین هر دو تا جداکننده باید حداقل یک توپ باشد.
  • جداکننده‌ها نمی‌توانند در ابتدای ردیف و یا انتهای ردیف باشند.

اکنون نشان می‌دهیم یک تناظر یک به یک بین این مساله و مساله تعداد جواب‌های معادله برقرار است. تناظر را به این صورت نشان می‌دهیم که از توپ اول تا آخرین توپی که قبل از جداکننده اول قرار دارد، متناظر با x_1 است. تعداد توپ‌هایی که بین جداکننده اول و دوم قرار دارد، بیانگر x_2 است و به همین صورت ادامه می‌دهیم. در انتها، تعداد توپ‌هایی که بعد از آخرین جداکننده هست، بیانگر x_k است.

به عنوان مثال، فرض کنید معادله x_1 + x_2 + x_3 = 6 داده شده باشد. یک حالت از توضیحات بالا به صورت زیر است:

اکنون توجه داریم که تعداد جایگاه‌های موجود برای جداکننده‌ها برابر است با n - 1. از طرفی، تعداد جداکننده‌های مورد نیاز برابر است با k - 1 که یکی کمتر از تعداد متغیرها است (زیرا از جداکننده آخر تا انتها نیز یک متغیر می‌شود). پس به دنبال تعداد حالاتی هستیم که بتوان k - 1 جایگاه از n - 1 جایگاه موجود را انتخاب کرد که تعداد آن برابر است با \binom{n - 1}{k - 1}.

مثال:

تعداد جواب‌های معادله زیر را بیابید به گونه‌ای که x_i ها حسابی باشند (می‌توانند صفر هم باشند).

x_1 + x_2 + ... + x_k = n

پاسخ

برای حل این مساله دو راه وجود دارد:

راه اول:

مانند بالا می‌توان مساله را به توپ‌ها و جداکننده‌ها مدل کرد. تنها تفاوت این است که در این حالت، دو یا چند جداکننده می‌توانند مجاور یکدیگر باشند و هیچ توپی بین آن‌ها نباشد. پس n توپ و k - 1 جداکننده داریم و می‌خواهیم آن‌ها را در یک ردیف بچینیم بدون هیچ شرطی. از جایگشت با تکرار می‌دانیم که تعداد حالات برابر است با: \binom{n + k - 1}{n} = \binom{n + k - 1}{k - 1}

راه دوم:

می‌دانیم می‌توان یک عدد ثابت را به دو طرف معادله اضافه کرد. پس داریم:

x_1 + x_2 + ... + x_k = n \iff x_1 + x_2 + ... + x_k + k = n + k \iff (x_1 + 1) + (x_2 + 1) + ... + (x_k + 1) = n + k

اکنون یک سری متغیر جدید y_i تعریف می‌کنیم به طوری که y_i = x_i + 1 باشد و معادله را بازنویسی می‌کنیم: y_1 + y_2 + ... + y_k = n + k

اکنون می‌دانیم y_i \ge 1 است چون y_i همان x_i + 1 است. پس مساله جدید، همان حالتی است که متغیرها در اعداد طبیعی بودند و لذا تعداد حالات برابر است با: \binom{n + k - 1}{n} = \binom{n + k - 1}{k - 1}

مثال:

مطلوب است تعداد پاسخ‌های معادله‌ی a_1 + a_2 + a_3 + a_4 + 2b_1 + 3b_2 + 4b_3 + 5b_4 = 15 با رعایت شرط: 0 \leq a_i \leq i

پاسخ

قرار می‌دهیم c_i = a_i + (i + 1)b_i و متناظر می‌کنیم تعداد جواب‌های معادله‌ی فوق را با معادله‌ی حسابی زیر: c_1 + c_2 + c_3 + c_4 = 15

که با توجه به مطالب پیشین برابر است با: \binom{15 + 4 - 1}{3} = \binom{18}{3}


ابزار صفحه