سوال ۹
اشکان ۱۶ مهره در خانهی بالا سمت چپ یک جدول $۴\times۴$ قرار داده است. او در هر مرحله میتواند یک خانه که بیشتر از یک مهره دارد را انتخاب کرده٬ ابتدا یکی از مهرههای آن را نابود کند٬ سپس از مهرههای باقی مانده تعدادی را در همان خانه مورد نظر باقی بگذارد٬ تعداد دلخواهی را به خانه سمت راست آن (در صورت وجود) و نهایتا تعداد دلخواهی را به خانه پایین آن (در صورت وجود) انتقال دهد.
هدف اشکان این است که با مجموعه ای از این حرکت ها به وضعیتی برسد که در آن تعداد خانههای مهره دار بیشینه باشد. این مقدار بیشینه چقدر است؟
- ۱۰
- ۱۱
- ۱۲
- ۱۳
- ۹
پاسخ
گزینهی «۲» درست است.
ابتدا ثابت میکنیم جواب از 11 بیشتر نیست . از برهان خلف استفاده میکنیم . فرض کنیم جواب 12 داشته باشیم . میدانیم در هر مرحله حداکثر میتوانیم به دو خانه جدید مهره برسانیم بنابراین در هر مرحله، با از دست دادن یک مهره حداکثر دو خانه جدید را میپوشانیم. فرض کنیم توانستیم 12 خانه را بپوشانیم چون از ابتدا در خانه (1,1) مهره بوده بنابراین 11 خانه جدید را پوشاندیم. چون با ازدست دادن یک مهره حداکثر دو خانه جدید دیده میشود برای دیدن این 11 خانه باید حداقل 6 مهره از دست بدهیم. پس در نهایت حداکثر 10 مهره خواهیم داشت. پس نمی توانیم 12 خانه را بپوشانیم .
حال جواب 11 را ارائه میکنیم :
- مرحلهیک : 13 مهره به (2,1)، 1 مهره به (1,2)
- مرحله دو : 10 مهره به (3,1)، 1 مهره به (2,2)
- مرحله سه : 7 مهره به (3,2)، 1 مهره به (4,1)
- مرحله چهار : 4 مهره به (3,3)، 1 مهره به (4,2)
- مرحله پنج : 1 مهره به (4,3)، 1 مهره به (,34)
▸ سوال قبل | سوال بعد ◂ |