سوال ۱۸
در یکی ردیف از خانه‌ها که از دو طرف نامتناهی است، تعدادی توپ قرار دارد. در هر حرکت، یک توپ را برمی‌داریم و دو توپ را از همان خانه، یکی را به طرف چپ و دیگری را به طرف راست، پرتاب می‌کنیم. هر توپ پرتاب شده از روی خانه‌های دارای توپ رد می‌شود تا به خانه‌ای خالی برسد و در همانجا متوقف می‌شود.
در ابتدا یک توپ داریم که می‌توانیم آن را هر جای ردیف خانه‌ها که بخواهیم قرار دهیم. بعد از قرار دادن توپ، می‌توانیم به تعداد دل‌خواهی حرکت بالا را انجام دهیم. اگر ردیف در ابتدا خالی باشد، به کدام یک از حالت‌های زیر می‌توان رسید؟
- ۱ و ۲
- ۱ و ۴
- ۲ و ۳
- ۳ و ۴
- ۱ و ۲ و ۳ و ۴
پاسخ
گزینه‌ی (2) درست است.
شکل 1 و 4:
اگر در هر مرحله مجموعه‌ی خانه‌های دارای مهره را در نظر بگیریم بازه‌ای را تشکیل می‌دهند که یک خانه‌ی خالی در بین آن‌ها است. با استقرا این ادعا را اثبات می‌کنیم:
پایه‌ی استقرا: پس از حرکت اول دو خانه داریم که از یکدیگر یک خانه فاصله دارند.
گام استقرا: هر خانه‌ای که در این مرحله انتخاب شود ابتدا دو خانه را اضافه می‌کند که با این کار بازه‌ای با طول بزرگ‌تر تشکیل می‌شود که خانه‌ی خالی ندارد (در یکی از جهت‌ها خانه‌ی خالی پر می‌شود). سپس مهره‌ی خانه‌ی انتخاب شده حذف می‌گردد که چون این خانه در دو سر بازه‌ی جدید نیست همواره بازه‌ای با یک خانه‌ی خالی باقی می‌ماند.
با این نتیجه می‌توان دریافت که هیچ‌گاه به شکل‌های 2 و 3 نمی‌توان رسید.