تقسیم 200 توپ در 100 جعبه

اگر همه‌ی جعبه‌ها شامل دو توپ باشند، آنگاه مسئله حل شده است. در غیر این صورت، حتما دو جعبه وجود دارند که تعداد توپ‌های متفاوتی دارند. فرض کنید جعبه‌ها را طوری مرتب کنیم که تعداد توپ‌های دو جعبه‌ی اول متفاوت باشند و فرض کنیم $x_i$ تعداد توپ‌های جعبه‌ی $i$-ام را نشان دهد. قرار می‌دهیم:

$S_1=x_1$

$S_2=x_1+x_2$

$\vdots$

$S_{100}=x_1+x_2+\ldots+x_{100}$

اکنون اگر دوتا از $S_k$ ها دارای باقی‌مانده‌ی یکسانی در تقسیم بر 100 باشند، آنگاه تفاضل آنها مجموعی به صورت

$x_i+x_{i+1}+\ldots+x_j$

است که بر 100 بخشپذیر است و مقدار آن نیز کوچکتر از تعداد تمام توپ‌ها، یعنی 200، است. بنابراین،

$x_i+x_{i+1}+\ldots+x_j=100$

و این یعنی مجموع توپ‌های موجود در جعبه‌های $i, i+1, \ldots , j$ برابر با 100 است.

اکنون فرض کنید چنین اتفاقی نیفتد، یعنی تمام مجموع‌های به شکل

$x_1+x_2+...+x_r$

دارای باقی‌مانده‌های متفاوتی در تقسیم بر 100 باشند. در این صورت $x_2$ را به لیست $S_k$ ها اضافه می‌کنیم. یعنی لیست زیر را در نظر می‌گیریم:

$x_1$

$x_2$

$x_1+x_2$

$x_1+x_2+x_3$

$\vdots$

$x_1+x_2+...+x_{100}$

این لیست دارای 101 عضو است و بنابراین طبق اصل لانه‌ی کبوتری، دو عضو آن دارای باقی‌مانده‌ی یکسانی در تقسیم بر 100 هستند. از آنجا که فرض کرده بودیم تا قبل از اضافه کردن $x_2$ به لیست $S_k$ ها هیچ دو مجموعی دارای باقی‌مانده‌ی یکسان در تقسیم بر 100 نیستند، پس مجموعی مثل $S$ در میان $S_k$ ها وجود دارد که باقی‌مانده‌ی آن در تقسیم بر 100 دقیقا مانند باقی‌مانده‌ی تقسیم $x_2$ بر 100 است. از طرفی فرض کرده بودیم

$x_1 \neq x_2$

و بنابراین

$S \neq x_1$

اکنون $S-x_2$ بر 100 بخشپذیر است و مقداری کوچکتر از 200 (تعداد تمام توپ‌ها) دارد. پس

$S-x_2=x_1+x_3+...+x_t=100$

که اثبات را کامل می‌کند.