لم : اگر دو دسته 2^k مهره ای داشته باشیم که بدانیم وزن یک دسته از دسته دیگر بیشتر است ، میتوانیم با k مرحله یک سکه ی خسیس و یک سکه ی سرحال پیدا کنیم .

اثبات لم : حکم را به استقرای ریاضی روی k ثابت میکنیم .

پایه : k = 0 یک سکه ی خسیس داریم و یک سکه ی سرحال ( چون باید یکی بزرگتر از دیگری باشه ! ) پس با 0 مرحله می شود !

فرض : اگر دو دسته 2^k مهره ای داشته باشیم که بدانیم وزن یک دسته از دسته دیگر بیشتر است ، میتوانیم با k مرحله یک سکه ی خسیس و یک سکه ی سرحال پیدا کنیم .

حکم : اگر دو دسته 2^{k + 1} مهره ای داشته باشیم که بدانیم وزن یک دسته از دسته دیگر بیشتر است ، میتوانیم با1 + k مرحله یک سکه ی خسیس و یک سکه ی سرحال پیدا کنیم .

دسته ی با وزن بیشتر را A مینامیم و دسته ی دیگر را B ! حال A و B را به دو قسمت مساوی a₁ و b₁ - a₂ و b₂ تقسیم میکنیم . a₁ را با b₁ مقایسه کرده ، اگر یکی از دیگری بزرگتر بود که طبق فرض استقرا به حکم خواهیم رسید ، در غیر این صورت میدانیم که چون A > B پس حتما a₂ و b₂ برابر نیستند . پس طبق فرض استقرا به حکم رسیدیم .

حکم را به استقرای ریاضی روی n ثابت میکنیم .

پایه : n = 1 با صفر مرحله میفهمیم .

فرض : 2ⁿ سکه داریم که 2^{n - 1} از آنها سرحال و بقیه خسته هستند . با حداکثر n - 1 مرحله میتوان دو سکه پیدا که یکی خسته و دیگری سرحال باشد .

حکم : 2^{n + 1} سکه داریم که 2ⁿ از آنها سرحال و بقیه خسته هستند . با حداکثر n مرحله میتوان دو سکه پیدا که یکی خسته و دیگری سرحال باشد .

سکه ها را به چهار بخش 2^{n - 1} تایی تقسیم میکنیم و به ترتیب آنها را a₄ a₃ a₂ a₁ مینامیم .

حال a₁ را با a₂ مقایسه میکنیم . اگر

1) مساوی نبودند : طبق لم به حکم خواهیم رسید . زیرا طبق لم n - 1 مرحله + یک مقایسه = n

2) مساوی باشند : a₂ را در نظر نمیگیریم و الگوریتم روبه رو را اجرا میکنیم : a₁ را دو بخش میکنیم . اگر دو بخش مساوی باشند یک بخش را نگه داشته و باز همین الگوریتم را انجام میدهیم و در غیر اینصورت طبق لم اگر دو بخش ، 2ⁱ مهره داشته باشد 1 + n - 2 - i مقایسه انجام داده ایم که طبق لم i تا مقایسه هم داریم پس حداقل n - 1 مرحله نیاز داریم . حال فرض میکنیم تا آخر الگوریتم یعنی پس از n - 2 مرحله همه با هم برابر می شوند پس دو دسته ی a₁ و a₂ مهره هایشان از یک نوع هستند و a₃ و a₄ از نوع دیگر پس یکی از مهره های a₁ و یکی از a₃ را میگیریم .

با تشکر از تمام کسانی که در نوشتن این اثبات ما را کمک کردند :-)