المپدیا

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

ابزار کاربر

ابزار سایت


سوالات المپیاد:مرحله ی دوم:دوره ی ۱۹:سوال چهار

درخت رنگارنگ

منظور از «درخت» تعدادی دایره است که با پاره‌خط‌هایی به هم متصل شده‌اند طوری که پاره‌خط‌ها همدیگر را قطع نمی‌کنند و بین هر دو دایره دقیقاً یک مسیر از طریق پاره‌خط‌های واصل وجود دارد.

مریم و مینا بازی «رنگ‌آمیزی» زیر را بر روی یک درخت دل‌خواه انجام می‌دهند: با شروع از مریم٬ هر کس در نوبت خود یکی از دایره‌هایی که هنوز رنگ‌ نشده را با یکی از ۶ رنگ قرمز٬ آبی٬ سبز٬ زرد٬ بنفش یا نارنجی رنگ می‌کند ولی باید رنگی که انتخاب می‌کند با رنگ هیچ کدام از دایره‌هایی که با یک پاره‌خط به این دایره متصل هستند و تاکنون رنگ شده‌اند یکی نباشد. مینا می‌خواهد بازی را به بن‌بست بکشاند یعنی وضعیتی ایجاد کند که هنوز دایره‌ی رنگ‌نشده‌ای وجود داشته باشد ولی حرکت دیگری ممکن نباشد. نشان دهید مریم می‌تواند با یک روش بازی خوب٬ مینا را ناکام بگذارد!


ابزار صفحه