المپدیا

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

ابزار کاربر

ابزار سایت


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

سوال ۱۴

در شکل روبه‌رو٬ می‌خواهیم دایره‌ها را با ۳ رنگ آبی٬ قرمز و سبز رنگ‌آمیزی کنیم٬ به طوری که٬ رنگ هر دایره و دو دایره‌ی زیر آن٬ که به آن متصل‌اند (اگر وجود داشته باشد)٬ با هم برابر باشد و یا رنگ هر سه آن‌ها متفاوت باشد. به چند طریق می‌توان این رنگ‌آمیزی را انجام داد؟

  1. ۳۴۲
  2. ۸۲۷
  3. ۹۲۷
  4. ۸۵۴۱
  5. ۸۴۰۲

پاسخ

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

به دایره‌هایی که هیچ دایره‌ای زیر آن‌ها نیست «میوه» می‌گوییم.

با تعیین وضعیت میوه‌ها، رنگ بقیه‌ی دایره‌ها منحصر به فرد تعیین می‌شود.(چرا؟)

شکل زیر را در نظر بگیرید. برای b و c سه رنگ وجود دارد. در صورتی که رنگ آن‌ها یکی شود، $a$ هم باید با آن‌ها هم‌رنگ باشد و در غیر این‌صورت‌ باید به رنگ سوم درآید. در شکل 6 میوه داریم پس طبق اصل ضرب به $3^6$ حالت می‌توان شکل را رنگ کرد.


ابزار صفحه