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