المپدیا

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

ابزار کاربر

ابزار سایت


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

سوال ۱۳

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

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

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

راهنمایی

خانه‌ی به رنگ آبی در چه جایگاه‌هایی ممکن است قرار بگیرد؟

راهنمایی

در راستای راهنمایی پیشین، دقت کنید که اگر خانه‌ی آبی در ستون راست نباشد، طبق اصل لانه کبوتری حداقل دو خانه‌ی همرنگ در آن ستون قرار خواهند گرفت.

راهنمایی

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

راهنمایی

بر روی باقی خانه‌های سطر پایین حالت‌بندی کنید. آیا تمام حالت‌های ممکن بدون در نظر گرفتن نام رنگ‌ها یکسان نیستند؟

پاسخ

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

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


ابزار صفحه