المپدیا

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

ابزار کاربر

ابزار سایت


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

سوال ۱۳

شکل زیر را در نظر بگیرید:

به چند طریق می‌توان سه خانه را قرمز، سه خانه را سبز، سه خانه را زرد و یک خانه را آبی کرد، طوری که هیچ دو خانه‌ی هم‌رنگی هم‌سطر یا هم‌ستون نباشند؟

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

پاسخ

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

در سطر پایین و ستون راست، دقیقن یک خانه از هر کدام از رنگ‌ها داریم. با توجه به این که دقیقن یک خانه‌ی آبی وجود دارد، پس خانه‌ی $A$ باید آبی باشد (در غیر این صورت دست کم دو خانه‌ی آبی جداگانه در سطر پایین و ستون راست خواهیم داشت). رنگ سه خانه‌ی $B$، $C$ و $D$ باید متفاوت باشد، پس $3!=6$ حالت دارد. بدون از دست دادن کلیت مسئله فرض کنید رنگ این سه خانه به ترتیب قرمز، سبز و زرد باشد. خانه‌ی $E$ نمی‌تواند سبز باشد (زیرا یک خانه‌ی سبز هم‌ستون دارد). هم‌چنین اگر خانه‌ی $E$ قرمز باشد، هیچ خانه‌ی دیگری نمی‌تواند قرمز باشد. پس این حالت هم منتفی است، زیرا سه خانه‌ی قرمز باید داشته باشیم. پس $E$ حتمن زرد است. به استدلال مشابه $F$ باید قرمز باشد. دو قسمت $1 \times 2$ در جدول باقی می‌ماند که هر کدام دو حالت برای رنگ‌آمیزی دارند، زیرا هر کدام یک خانه‌ی سبز دارند و با نشاندن خانه‌های سبز، رنگ بقیه‌ی خانه‌ها به طور یک‌تا تعیین می‌شود. پس در کل $$3! \times 2 \times 2 = 24$$ حالت داریم.


ابزار صفحه