سوال ۵۴
دو نفر این بازی را روی شکل زیر انجام می دهند: هر کدام از این دو بازیکن در نوبت خودش یکی از دایره‌هایی را که تا کنون رنگ نشده است با یکی از دو رنگ آبی یا قرمز رنگ می‌کند٬ به شرطی که هیچ‌گاه دو دایره‌ای که با یک خط به هم متصل‌اند با یک رنگ رنگ‌آمیزی نشوند. کسی که نتواند در نوبت خودش دایره‌ای را رنگ کند٬ بازنده‌ی بازی محسوب می‌شود.
آیا بازیکن اول می‌تواند طوری بازی کند که همواره برنده شود؟
پاسخ
معلوم است که در هر حال از سه راس $B،A$ و $C$ دقیقا و راس واز سه راس $E،D$ و $F$ حداقل دو راس قابل رنگ کردن می‌باشند؛ یعنی بازی یا بعد از رنگ کردن راس چهارم پایان می‌پذیرد و یا بعد از رنگ کردن راس پنجم٬ که به ترتیب دو شکل الف و ب به‌دست می‌آید:
(در حالت الف اگر به جای دو راس $A$ و $C$، دو راس $A$ و $B$ و یا دو راس $B$ و $C$ رنگ شوندنیز بحث عوض نمی‌شود.)
در حالت الف نفر دوم و در حالت ب نفر اول برنده می‌شود٬ بنابراین اگر نفر دوم کار کند که رنگ دو راس $D$ و $F$ متفاوت باشند٬ آن‌گاه نفر دوم برنده خواهد شد.
ابزار صفحه
کلیه‌ی حقوق این سایت متعلق به کمیته‌ی ملی المپیاد کامپیوتر ایران است.
