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