مسابقهی شماره ۲۰۶
در اطراف یک جادهی دایرهای-شکل، n پمپبنزین قرار داند که مجموع بنزینهای همه آنها دقیقا بهاندازه مصرف یک اتومبیل برای یک بار دور زدن جاده است. نشان دهید مکانی وجود دارد که اتومبیل میتواند با شروع از آنجا و با باک خالی فقط با استفاده از بنزینهای پمپ اطراف جاده یک بار جاده را دور بزند.
به راحتی و با استفاده از استقرا میتوان این مساله را حل کرد. حکم بهوضوح برای n=1 برقرار است. حال اگر حکم برای k پمپ بنزین برقرار باشد بایستی اثبات کنیم که برای k+1 پمپ بنزین نیز حکم صحیح است. اگر از پمپ بنزین x به y برسیم (و پمپ بنزین دیگری در مسیرمان قرار نداشته باشد)، میتوان فرض کرد که پمپ بنزین y را حذف کردهایم و همهٔ بنزین آن را به پمپ بنزین x منتقل کردهایم. حال k پمپ بنزین داریم که بنا بر فرض استقرا اتومبیل میتواند همهٔ مسیر را طی کند. لذا حکم به استقرا ثابت میگردد.