اثبات این سوال را من با استقرا انجام دادم

پایه استقرا برای n=1 که واضح است.

فرض می کنیم که حکم برای n-1 درست باشد و حالا حکم را برای n اثبات می کنم.

حالا عملیات زیر را انجام می دهم:

1- مقدار i و s را برابر 1 قرار بده.

2- در صندوقچه ی شماره ی i را باز کن و x را برابر تعداد یاقوت های آن (در همان لحظه) قرار بده و در صندوقچه را ببند.

3- دوباره در صندوقچه ی i را باز کن و y را برابر تعداد یاقوت های آن (در همان لحظه) قرار بده و در صندوقچه را ببند.

4- اگر x>0 و y=0 بود، s را برابر صفر قرار بده و به خط 6 برو؛ در غیر اینصورت به خط 5 برو.

5- اگر i=n بود به خط 6 برو؛ در غیر اینصورت i را یکی زیاد کن و به خط 2 برو.

6- پایان.

اگر بعد از پایان اجرای الگوریتم بالا، مقدار s برابر 1 بود، یعنی عدد نوشته شده زیر هر صندوقچه، با شماره ی همان صندوقچه برابر است و یا تعداد یاقوتهای موجود در آن صندوقچه، برابر صفر بوده است.در اینصورت با باز و بست کردن هیچ صندوقچه ای، یاقوتی از آن صندوقچ به صندوقچه ی دیگری منتقل نمی شود (چرا؟) و به راحتی می توان تعداد کل یاقوت ها را به دست آورد.

اما اگر s صفر باشد، یعنی صندوقچه ای وجود داشته که عدد زیرش با شماره ی خودش برابر نبوده و تعداد ناصفری یاقوت داشته است. با توجه به روند اجرای الگوریتم، واضح است که صندوقچه ی شماره ی i این ویژگی دارد؛ به عبارتی عددی مانند j زیر صندوقچه ی i نوشته شده که i≠j (توجه کنید که ما فعلا نمی دانیم j چه عددی است). حالا دوباره در صندوقچه ی i را باز می کنیم و می بندیم تا مطمئن شویم خالی شده است و بعد، آن را کنار می گذاریم. حالا تمام یاقوت ها داخل n-1 صندوقچه ی دیگر است که طبق فرض استقرا می توانیم طوری عملیات باز و بست کردن صندوقچه ها را انجام دهیم که از تعداد کل یاقوت ها مطلع شویم. البته باید بعد از هر عملیاتی که انجام می دهیم، یکبار هم در صندوقچه ی i (که آن را کنار گذاشته بودیم) بازو بست کنیم (چرا؟). باا این حساب، اگر صندوقچه ای داشته باشیم که عدد نوشته شده زیر آن برابر i باشد، در عملیات هایی که طبق فرض استقرا انجام می دهیم مثل آن است که عدد نوشته شده زیرش برابر j باشد (j همان عددی است که زیر صندوقچه ی i نوشته شده بود). با این کار می توانیم، تعداد کل یاقوت های موجود د n صندوقچه را نیز به دست آوریم و حکم اثبات می شود.