المپدیا

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

ابزار کاربر

ابزار سایت


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

سوال ۱۴

می‌خواهیم در خانه‌های جدول روبه‌رو ۴ مهره بگذاریم به قسمی که در هر خانه بیش از یک مهره قرار نگیرد و از هر دو خانه‌ای که با هم تنها در یک راس مشترک هستند٬ لااقل یکی خالی باشد. به چند حالت می‌توان این کار را انجام داد؟

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

پاسخ

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

معلوم است که در هر یک از دو شبکه‌ی $2\times2$ موجود در سمت چپ و نیز سمت راست شکل حداکثر دو مهره می‌تواند قرار گیرد و چون در شکل دقیقا ۴ مهره موجود است پس در هر یک از آن شبکه‌ها دقیقا ۲ مهره موجود خواهد بود. طرق قرار دادن دو مهره در شبکه‌ی سمت چپ و به دنبال آن قرار دادن دو مهره در شبکه‌ی سمت راست به شکل زیر می‌باشد:


ابزار صفحه