المپدیا

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

ابزار کاربر

ابزار سایت


سوالات المپیاد:مرحله ی اول:دوره ی ۱۷:سوال ۳۹

سوال 39

به چند طریق می‌توان خانه‌های سفید شکل روبه‌رو را با ۱۰ تا از قطعه‌های (۱) و (۲) به‌طور کامل پوشاند؟

  1. ۶
  2. ۱۲
  3. ۱۸
  4. ۱۶
  5. هیچ‌کدام

پاسخ

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

جدول را به صورت زیر شطرنجی رنگ می‌کنیم.

چون هر قطعه دو خانه از یک رنگ را پر می‌کند، پس پر کردن خانه‌های سفید و خانه‌های خاکستری مستقل از هم هستند.

برای پر کردن خانه‌های خاکستری تنها 2 حالت داریم (خانه‌ی (1, 3) با چه خانه‌ای جفت شود).

برای خانه‌های سفید روی جهت قطعه‌های (1, 2) و (1, 4) و (5, 2) و (5, 4) حالت‌بندی می‌کنیم:

  1. در همه‌ی این خانه‌ها قطعه اول را بگذاریم(بقیه خانه‌ها یکتا تعیین می‌شوند).
  2. در همه‌ی این خانه‌ها قطعه دوم را بگذاریم(بقیه خانه‌ها یکتا تعیین می‌شوند).
  3. در خانه‌های (5, 4) و (1, 2) قطعه‌ی اول و در دو خانه‌ی دیگر قطعه‌ی دوم را قرار دهیم در این‌صورت بقیه خانه‌ها دو حالت دارند.
  4. در قسمت بالا برای دقیقن یک خانه از این 4 خانه جهت قطعه را عوض کنیم در این‌صورت بقیه خانه‌ها یکتا تعیین می‌شوند.

پس در کل 8 حالت برای چینش خانه‌های سفید داریم. در نتیجه برای کل جدول 16 حالت داریم.


ابزار صفحه