المپدیا

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

ابزار کاربر

ابزار سایت


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

سوال ۳

شکل زیر جزیره‌ای را نشان می‌دهد که ۱۶ خانه دارد. مساحت هر خانه هم یک واحد است. ۴تا از این خانه‌ها در شکل مشخص شده‌اند حاوی معدن طلا هستند.

یک «مزرعه»٬ یک مستطیل روی این جزیره است که اضلاع آن دقیقا روی مرزهای خانه‌ها قرار دارد و مساحت آن حداقل یک واحد است. ارزش یک مزرعه برابر تعداد معادن طلای داخل آن است. برای مثال٬ ارزش مزرعه‌ی شامل سه ستون سمت چپ و دو سطر بالایی (به مساحت ۶) برابر ۲ و ارزش مزرعه‌ای که شامل تمام خانه‌های جدول باشد٬ برابر ۴ است.

مجموع ارزش‌های تمام مزرعه‌های متفاوت این جزیره کدام است؟

  1. ۱۰۴
  2. ۲۴
  3. ۲۴۰
  4. ۱۲۰
  5. ۹۶

پاسخ

گزینه‌ی(۵) درست است.

در یک روش می‌توان مسئله را به چند بخش تقسیم کنیم که در هر گام تعداد مزرعه‌ها با ۱ تا ۴ معدن را شمرده و در نهایت آن‌ها را با ضریبشان با هم جمع کنیم.

اگر از نگاهی دیگر به مسئله نگاه کنیم می‌توانیم برای هر معدن طلا تعداد مزارع مستطیلی شامل آن را بشماریم. به دلیل تقارن شکل کافی است فقط یکی از معادن را به‌دست آورده و در ۴ ضرب کنیم.

برای این‌کار تعداد مستطیل‌هایی را که معدن بالایی در آن قرار دارد را می خواهیم بشماریم. ۳ حالت برای به‌دست آوردن یکی از ضلع‌های عمودی و ۲ حالت برای انتخاب ضلع دیگر داریم که معدن در مستطیل قرار بگیرد. برای ضلع‌های افقی مستطیل هم ۱ حالت برای ضلع بالایی و ۴ حالت برای انتخاب ضلع پایینی داریم که در کل برابر است با $۳×۲×۱×۴$ که ۲۴ حالت می شود. حال چون ۴ معدن داریم تعداد کل برابر $۴×۲۴$ یعنی ۹۶ می‌باشد.


ابزار صفحه