سوال ۵

شکل روبه‌رو ‎۱۲‎ رأس دارد که ‎۱۱‎ زوج آن با پاره‌خط‌هایی به‌هم وصل شده‌اند. می‌خواهیم هرکدام از رأس‌ها را با یکی از سه رنگ موجود رنگ کنیم به طوری که هیچ ‎۲‎ رأس متصل به‌هم، یک‌رنگ نشوند. به‌چند طریق این کار ممکن است؟‎‎

  1. کم‌تر از ‎۱۰۰۰‎ طریق
  2. بین ‎۱۰۰۰‎ و ‎۳۰۰۰‎ طریق
  3. بین ‎۳۰۰۰‎ و ‎۶۰۰۰‎ طریق
  4. بین ‎۶۰۰۰‎ و ‎۲۰۰۰۰‎‎ طریق
  5. بین ‎۲۰۰۰۰‎ و ‎۱۰۰۰۰۰‎‎ طریق

پاسخ

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

یکی از رئوس از درجه‌ی واحد راانتخاب و آن را با یکی از سه رنگ موجود رنگ می‌کنیم. راس متصل به آن٬ سپس راس متصل به دومی و … را به دو طریق می‌توانیم رنگ کنیم٬ بنابراین تعداد روش‌های مطلوب برابر $3\times2^{11}$ یعنی ۶۱۴۴ خواهد شد.