المپدیا

پاسخ ۳۲ است.

صفحه‌ را به صورت شطرنجی با دو رنگ سفید و سیاه رنگ‌آمیزی کنید. در مثال ۳۲، مرتضی می‌تواند تمام مهره‌های خود را بر خانه‌های سیاه شده قرار دهد.

در صورتی که تعداد مهره‌های مرتضی کمتر یا مساوی ۳۲ باشد ابوالفضل به چه نحوی به حالت نهایی دست یابد؟

اگر بیش از ۳۲ مهره گذاشته شده باشد، یعنی بیش از نیمی از خانه‌های جدول پر شده‌اند. پس کمتر از نیمی از خانه‌ها خالی هستند.

کافیست تمام خانه‌های خالی را مهره گذاری کنیم. سپس همه‌ی مهره‌ها را حذف کنیم. حداکثر چند مرحله طول خواهد کشید؟

سعی کنید نشان دهید نمی‌توان در مهره‌گذاری راهنمایی دوم با کمتر از ۳۲ مرحله به جدول مورد نظر رسید.

به کمک برهان خلف حکم راهنمایی ۶ را ثابت کنید.

فرض کنید بتوان در کمتر از ۳۲ مرحله جدول را خالی کرد. پس عملیاتی وجود داشته که طی آن،‌ ابوالفضل بیش از یک مهره‌ی اولیه را برداشته است. او می‌بایست چند عملیات پیش از این گام زده باشد تا بتواند زیرجدول مذکور را برای عملیات انتخاب کند؟

نشان دهید حداقل به تعداد مهره‌های داخل زیر‌جدول می‌بایست مهره گذاشته باشد.

نتیجه بگیرید حذف کردن مهره‌ها به شکل زیرجدول‌های ۱×۱ فرایندی بهینه است.