المپدیا

دانش‌نامه‌ی المپیاد کامپیوتر ایران

ابزار کاربر

ابزار سایت


سوالات المپیاد:مرحله ی اول:دوره ی ۲۲:سوال ۹

سوال ۹

اشکان ۱۶ مهره در خانه‌ی بالا سمت چپ یک جدول $۴\times۴$ قرار داده است. او در هر مرحله می تواند یک خانه که بیشتر از یک مهره دارد را انتخاب کرده٬ ابتدا یکی از مهره‌های آن را نابود کند٬ سپس از مهره های باقی مانده تعدادی را در همان خانه مورد نظر باقی بگذارد٬ تعداد دلخواهی را به خانه سمت راست آن (در صورت وجود) و نهایتا تعداد دلخواهی را به خانه پایین آن (در صورت وجود) انتقال دهد.

هدف اشکان این است که با مجموعه ای از این حرکت ها به وضعیتی برسد که در آن تعداد خانه های مهره دار بیشینه باشد. این مقدار بیشینه چقدر است؟

  1. ۱۰
  2. ۱۱
  3. ۱۲
  4. ۱۳
  5. ۹

پاسخ

گزینه ی «۲» درست است.

ابتدا ثابت می کنیم جواب از 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)

ابزار صفحه