شکل بالا جزیرهای را نشان میدهد که ۱۶ خانه (مربع کوچک) دارد. مساحت هر خانه هم یک واحد است. ۴تا از این خانهها در شکل مشخص شدهاند حاوی معدن طلا هستند.
یک «مزرعه»٬ یک مستطیل روی این جزیره است که اضلاع آن دقیقا روی مرزهای خانهها قرار دارد و مساحت آن حداقل یک واحد است. ارزش یک مزرعه برابر تعداد معادن طلای داخل آن است. برای مثال٬ ارزش مزرعهی شامل سه ستون سمت چپ و دو سطر بالایی (به مساحت ۶) برابر ۲ و ارزش مزرعهای که شامل تمام خانههای جدول باشد٬ برابر ۴ است.
مجموع ارزشهای تمام مزرعههای متفاوت این جزیره کدام است؟
الف) ۱۰۴ ب) ۲۴ ج) ۲۴۰ د) ۱۲۰ هـ)۹۶
[جواب این سوال المپیاد کامپیوتر، در ادامه در دسترس می باشد.]
پاسخ
گزینهی(هـ) درست است.
در یک روش میتوان مسئله را به چند بخش تقسیم کنیم که در هر گام تعداد مزرعهها با ۱ تا ۴ معدن را شمرده و در نهایت آنها را با ضریبشان با هم جمع کنیم.
اگر از نگاهی دیگر به مسئله نگاه کنیم میتوانیم برای هر معدن طلا تعداد مزارع مستطیلی شامل آن را بشماریم. به دلیل تقارن شکل کافی است فقط یکی از معادن را بهدست آورده و در ۴ ضرب کنیم.
برای اینکار تعداد مستطیلهایی را که معدن بالایی در آن قرار دارد را می خواهیم بشماریم. ۳ حالت برای بهدست آوردن یکی از ضلعهای عمودی و ۲ حالت برای انتخاب ضلع دیگر داریم که معدن در مستطیل قرار بگیرد. برای ضلعهای افقی مستطیل هم ۱ حالت برای ضلع بالایی و ۴ حالت برای انتخاب ضلع پایینی داریم که در کل برابر است با ۳×۲×۱×۴ که ۲۴ حالت می شود. حال چون ۴ معدن داریم تعداد کل برابر ۴×۲۴ یعنی ۹۶ میباشد.
جواب این سؤال المپیاد کامپیوتر، منتشر شده است.