Processing math: 100%

المپدیا

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

ابزار کاربر

ابزار سایت


سوالات المپیاد:مرحله ی دوم:دوره ی ۲۵:سوال سه

توپ‌های بهروز

بهروز b جعبه و n نوع توپ دارد(bn). در هر جعبه، تعدادی توپ وجود دارد. توجه کنید یک نوع توپ می‌تواند در چند جعبه وجود داشته باشد. می‌دانیم هر n جعبه‌ای را در نظر بگیریم، می‌توان از هر یک، ۱ توپ انتخاب کرد؛ طوری که هیچ دو توپی از n توپ انتخاب شده، هم‌نوع نباشند. فرض کنید مجموع تعداد توپ‌های جعبه‌ها s باشد. کمینه‌ی ممکن s را بیابید (در واقع شما باید یک s را پیدا کنید که حالتی با s توپ داشته باشیم؛ ولی هیچ حالتی با s1 توپ وجود نداشته باشد).

پاسخ

ثابت می‌کنیم پاسخ برابر n×(bn+1) است.

ابتدا ثابت می‌کنیم در هر آرایش، حداقل این تعداد توپ داریم. هر نوع توپی که در نظر بگیرید، باید در حداقل bn+1 جعبه آمده باشد. برهان خلف می‌زنیم. فرض کنید این طور نباشد. یعنی یک نوع توپ وجود دارد که در حداقل n جعبه نیامده است. آن n جعبه را در نظر بگیرید. نمی‌توان از آن‌ها توپ‌هایی انتخاب کرد که تمام انواع توپ‌ها انتخاب شوند و با فرض مسئله به تناقض می‌رسیم. پس sn×(bn+1) است.

حال ثابت می‌کنیم آرایشی با n×(bn+1) توپ وجود دارد. حکم را با استقرا روی b ثابت می‌کنیم. برای پایه، حالت b=n را در نظر می‌گیریم. برای هر نوع توپ، یک جعبه‌ی جدا در نظر می‌گیریم و یک توپ از آن نوع در جعبه‌ی مذکور می‌گذاریم. به این ترتیب آرایشی با n×(bn+1)=n توپ ارائه می‌شود. حال فرض کنید حکم برای b=k برقرار باشد. ثابت می‌کنیم حکم برای b=k+1 نیز برقرار است. یک جعبه را کنار می‌گذاریم و در k جعبه‌ی باقی‌مانده، آرایشی با n×(kn+1) توپ، مطابق فرض استقرا ارائه می‌کنیم. حال در جعبه‌ی کنار گذاشته شده از هر نوع توپ، یکی می‌گذاریم. به این ترتیب یک آرایش مطلوب به دست می‌آید که n×(kn+2) توپ دارد و حکم ثابت می‌شود.


ابزار صفحه