المپدیا

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

ابزار کاربر

ابزار سایت


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

سوال ۱۳

یک جدول ۸ در ۸ داریم. هر خانه یک خانه‌ی قرینه نسبت به نقطه‌ی وسط دارد. برای مثال خانه‌ی ۳ در شکل قرینه خانه‌ی ۱ نسبت به نقطه‌ی وسط می‌باشد. همچنین هر خانه یک خانه‌ی قرینه نسبت به خط عمودی مرکزی نیز دارد. برای مثال خانه‌ی ۲ قرینه‌ی خانه‌ی ۱ نسبت به خط عمودی مرکزی می‌باشد. می‌خواهیم این جدول را با 3 رنگ، رنگ کنیم به شرطی که هر خانه‌ی این جدول حداقل با یکی از دو خانه‌ی قرینه‌ی خود (قرینه نسبت به خانه‌ی مرکز و قرینه نسبت به خط عمودی وسط) همرنگ باشد. به چند طریق می‌توان این کار را انجام داد؟

  1. ۱۵۱۶
  2. ۱۶۱۵
  3. ۳۱۶
  4. ۳۶۴
  5. ۹۱۶

راهنمایی

خانه‌هایی را که قرینه یکدیگر هستند، در یک دسته قرار دهید و ساختار همه‌ی دسته‌های ایجاد شده را بررسی کنید.

راهنمایی

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

پاسخ

گزینه‌ی ۱ درست است.

یک خانه را به همراه قرینه‌ی آن نسبت به خط عمودی و نسبت نقطه‌ی مرکز و همچنین به همراه قرینه‌ی نسبت به خط عمودی قرینه‌ی نسبت به مرکز آن را (در مجموع چهار خانه) را در نظر می‌گیریم. این چهار خانه یا همگی همرنگ هستند یا ضربدری همرنگ هستند و یا دوتای پایین همرنگ و دوتای بالا نیز همرنگ می‌باشند. پس در مجموع ۳ + ۶ + ۶ حالت داریم و چون تعداد این چهارتایی‌ها برابر ۱۶ می‌باشد در مجموع ۱۵ به توان ۱۶ حالت داریم.


ابزار صفحه