====== سوال ۵ ======
{{:سوالات_المپیاد:مرحله‌ی_اول:دوره‌ی_۱۲:512.png |}}
شکل روبه‌رو ‎۱۲‎ رأس دارد که ‎۱۱‎ زوج آن با پاره‌خط‌هایی به‌هم وصل شده‌اند.
می‌خواهیم هرکدام از رأس‌ها را با یکی از سه رنگ موجود رنگ کنیم به طوری  که هیچ ‎۲‎ رأس متصل به‌هم، یک‌رنگ نشوند. به‌چند طریق این کار ممکن است؟‎‎


  - کم‌تر از ‎۱۰۰۰‎ طریق
  - بین ‎۱۰۰۰‎ و ‎۳۰۰۰‎ طریق
  - بین ‎۳۰۰۰‎ و ‎۶۰۰۰‎ طریق
  - بین ‎۶۰۰۰‎ و ‎۲۰۰۰۰‎‎ طریق
  - بین ‎۲۰۰۰۰‎ و ‎۱۰۰۰۰۰‎‎ طریق


<پاسخ>
گزینه (۴) درست است.


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


</پاسخ>


  * [[سوال ۶|سوال بعد]]
  * [[سوال ۴|سوال قبل]]