برای اثبات هر دو قسمت مسئله از لم زیر که اثبات آن با توجه به الگوریتم بدیهی است، استفاده می‌کنیم:

لم: در صورتی که در یک دور از اجرای الگوریتم، دانش‌آموز $S$ در المپیاد $O$ پذیرفته شد، در دورهای بعد، در هر دور لااقل یک نفر به المپیاد $O$ درخواست می‌دهد و نمره‌ی کسی که در این المپیاد پذیرفته می‌شود بیش‌تر یا مساوی با نمره‌ی $S$ در این المپیاد است.

اثبات: چون دانش‌آموز $S$ در المپیاد $O$ پذیرفته شده است، پس در این دور اجرای الگوریتم تغییری در لیست المپیادهایی که $S$ در آن‌ها حذف شده است، به وجود نمی‌آید. پس در دور بعدی نیز $S$ باز به $O$ درخواست می‌دهد. بنابراین تنها در صورتی ممکن است $S$ در $O$ پذیرفته نشود که یک دانش‌آموز که در $O$ نمره‌ای بیش از $S$ کسب کرده است، برای این المپیاد درخواست‌ دهد و در آن پذیرفته گردد. بنابراین در هر دور اجرای الگوریتم لااقل یک نفر در این المپیاد پذیرفته می‌شود که نمره‌ی او از نمره‌ی $S$ بیش‌تر است.

الف) با توجه به الگوریتم دیده می‌شود که در هر دور اجرای الگوریتم، حداقل یک دانش‌آموز در یک المپیاد رد می‌شود. بنابراین الگوریتم حداکثر $n^2$ دور می‌تواند طول بکشد و نهایتا متوقف خواهد شد. برای اثبات این که الگوریتم تنها زمانی پایان می‌یابد که در هر المپیاد یک دانش‌آموز پذیرفته شده باشد، کافی است ثابت کنیم که هیچ‌گاه شرط خاتمه‌ی بند ۱ الگوریتم برقرار نمی‌شود؛ یعنی هیچ‌گاه ممکن نیست که یک دانش‌آموز در همه‌ی المپیاد‌ها رد شده باشد. اگر یک دانش‌آموز مانند $S$ در یک دور در همه‌ی المپیاد‌ها رد شده باشد، باید یک المپیاد مانند $O$ وجود داشته باشد که هیچ‌کس به آن دخواست نداده است. (چون در غیر این صورت به هر یک ا ز المپیاد‌ها باید دقیقا یک درخواست داده شده باشد.) ولی چون $S$ در $O$ رد شده است، ئس باید یک بار به $O$ درخواست داده باشد. ولی بنا به لم، در این صورت باید در این دور هم لااقل یک نفر به $O$ درخواست داده باشد. این تناقض ثابت می‌کند که دانش‌آموزی که در همه‌ی المپیاد‌ها رد شده باشد، وجود ندارد.

ب) دو زوج مانند $(O,S)$ و $(O',S')$ در نظر می‌گیریم. فرض کنیم که علاقه‌ی $S$ به $O'$ بیش از علاقه‌ی او به $O$ است. بنابراین چون در نهایت $S$ در $O$ پذیرفته شده است، پس باید یک بار به $O'$ هم درخواست داده باشد. در نتیجه بنا به لم باید پس از این درخواست در هر دور دانش‌آموزی در $O'$ پذیرفته شود که نمره‌ی او از نمره‌ی $S$ در $O'$ بیش‌تر باشد. بنابراین نمره‌ی $S'$ هم باید از نمره‌ی $S$ در $O'$ بیش‌تر باشد. بنابراین با توجه به تعریف گزینش پایدار، گزینش به‌دست آمده توسط الگوریتم یک گزینش پایدار است.