تعداد جوابهای صحیح و نامنفی نامعادله خطی را بیابید

Question

تعداد جوابهای صحیح و نامنفی نامعادله خطی زیر را بیابید. $$ x_{1} + x_{2} + x_{3} \leq 4$$

پاسخ و حلم: تعداد جوابهای صحیح نامنفی نامعادله بالا از دستور $ \binom{n+k}{k} $ بدست میاد پس: $$ \binom{4+3}{3}=35 تا جواب $$ حالا سوال بنده اینه که اگر نامعادله های(و یا معادله های) معادل با صورت سوال را بنویسیم و تعداد جوابهای صحیح نامنفی را بیابیم چرا ۳۵ نمیشن و متعاوت اند؟!!

مثلاً تعداد جوابهای صحیح و نامنفی $$ x_{1} + x_{2} + x_{3} < 5$$ را اینطوریم بدست میاریم که : ابتدا با افزودن یک مقدار صحیح مثبتm به سمت چپ، نامعادله را به معادله خطی تبدیل کرده و تعداد جوابهای صحیح نامنفی را میابیم: $$ x_{1} + x_{2} + x_{3} +m=5$$ که تعداد جوابهای این معادله خطی برابر است با : $$ \binom{n+k-1}{k-1} = \binom{5+4-1}{4-1} = \binom{8}{3} =56$$

و همچنین می‌شود معادل های دیگه نوشت که تعداد حواب صحیح و نامنفی متفاوت میده!

چرا تعداد های بدست آمده متفاوت اند؟؟

Answer 1

تعداد جوابهای صحیح و نامنفی معادله $x_1+x_2+...+x_m=n$ برابر است با $ \ \binom{m+n-1}{n} = \binom{m+n-1}{m-1} $.بنابر این تعداد جوابهای نامعادله فوق برابر است با تعداد جوابهای معادلات:

$x_1+x_2+x_3=0,1,2,3,4$

یعنی:

$ \binom{2}{0} + \binom{3}{1} + \binom{4}{2} + \binom{5}{3} + \binom{6}{4} $

$ \Box $

Comments

@قاسم شبرنگ
سپاس وقت گذاشتید.
صحیح است، حل شما هم یکی از معادل ها یا روش های دیگه هست که میشه استفاده کرد.

اما آیا روش دومی که بنده در حلم در صورت سوال استفاده کردم غلط هست؟؟

---

سلام.شما می تواند به جای متغیر m حتا دو یا سه متغیر دیگر بگذارید که می بینید جوابهای متفاوتی داریم.

---

@قاسم شبرنگ
متاسفانه قانع نمیشم ، به دلایلی مثلاً:
اولاً مگر همان یک متغیر مثل m با هر مقدار که نامعادله رو به معادله تبدیل کنه، کافی نمی باشد؟ کافی هست.

دوماً بنده میتونم بگم با فرض اینکه اگر چند متغیر مثبت دیگه هم حتی اضافه کنیم باز تمام آنها رو با یک متغیر نشان دهیم مثل m.
سوماً تعریف یا فکر میکنم اصل تبدیل نابرابری به برابری ، از وجود داشتن مقدار مثبت مثل p صحبت می کند که بتوان نابرابری رو به برابری تبدیل کرد.

چهارماً اگر با این فرض که افزودن چند متغیر ، جوابهای متفاوتی رو تولید می کند ، پس این نکته درسی که سالهای سال کتب کمک آموزشی یا اشخاص استفاده می کردند ، روال غلطی داشته، (البته دور از ذهنم نیست اما حتماً دلیلی داشته که استفاده میشه این روش)
 سپاس فراوان  که وقت گذاشتید.

آنچه که بنده خودم میتونم بگم اینکه m یه چیز مثبت باید باشه اما بقیه متغیر های معادله نامنفی اند، حالا این مورد چقدر میتونه تاثیر بذاره برام سواله؟!

فکر می کنم جواب رو هم اکنون پیدا کردم، دقیقاً همین تاثیر مثبت بودن m که باید نامنفی باشد.

 انگار میخوام m مثبت رو تبدیل به m نامنفی کنم و بعد با تغییر متغیری که نامنفی شده جواب رو بیابیم که میشه همون ۳۵ .

Answer 2

برای حل نامعادله خطی $ x_{۱} + x_{۲} + x_{۳} \leq 4$ از روش (بنظرم پرخطای) تبدیل به $ x_{۱} + x_{۲} + x_{۳} \prec 5 $ استفاده میکنیم: حال ابتدا نامعادله مذکور را با افزودن mمثبت به سمت چپ، به معادله تبدیل می کنیم. $$ x_{۱} + x_{۲} + x_{۳}+m=5$$ که$ x_{i} $ها نامنفی اند و mمثبته که باید نامنفی بشه تا بتوان از نکته تعداد جوابهای صحیح و نامنفی استفاده کرد: پس $$m \geq 1 \rightarrow m-1 \geq 0$$ ,$$ w=m-1 \geq 0$$

حال داریم: $$x_{۱} + x_{۲} + x_{۳}+w+1=5$$ که $$x_{۱} + x_{۲} + x_{۳}+w=4$$ و تعداد جوابهای صحیح نامنفی این معادله خطی برابر با : $ \binom{n+k-1}{k-1} = \binom{4+4-1}{4-1} = \binom{7}{3} =35$

پس آنچه که در این مسئله اهمیت دارد همان نامنفی بودن متغیر ها هست.