آرین و پارمیس در حال انجام یک بازی روی یک گراف هستند و میخواهند رأسهای آن را رنگآمیزی کنند. در ابتدای بازی، رأسهای گراف، قرمز، آبی، یا بدون رنگ هستند. بازی را آرین شروع میکند و بعد از هر نفر، نوبت به شخص دیگر میرسد. آرین در هر نوبتش، یک رأسِ بدون رنگ را که حداقل یک همسایهی قرمز دارد، انتخاب، و آن را قرمز میکند. به طور مشابه، پارمیس هم در هر نوبت خود، یک رأسِ بدون رنگ را که حداقل یک همسایهی آبی دارد، انتخاب، و آن را آبی میکند. هر کسی که نتواند رأس جدیدی را رنگآمیزی کند، بازی را میبازد. دو رأس را همسایه مینامیم اگر بینشان یالی وجود داشته باشد.
در این سوال، بازی روی گراف زیر انجام میشود. قبل از شروع بازی، ابتدا دو رأس متفاوت قرمز و آبی میشوند و سپس بازی آغاز میگردد. در چند مورد از وضعیتهای شروع بازی، آرین میتواند طوری بازی کند که مستقل از نحوهی بازی پارمیس، همواره برندهی بازی باشد؟ دو وضعیت شروع بازی را متفاوت میدانیم اگر رنگ حداقل یک رأس در این دو وضعیت متفاوت باشد.
پاسخ
گزینه (5) درست است.
در این سوال، بازی روی گراف زیر انجام میشود. این بار قبل از شروع بازی، ابتدا آرین یک رأس را انتخاب، و آن را قرمز میکند، و بعد از آن، پارمیس به انتخاب خودش، یک رأس دیگر را آبی میکند، و سپس بازی شروع میشود. تعداد رأسهایی را بیابید که آرین اگر قبل از شروع بازی، یکی از آنها را انتخاب کرده باشد، مستقل از نحوهی بازی پارمیس یا رأسی که پارمیس قبل از شروع بازی انتخاب میکند، بتواند همواره برندهی بازی باشد.
پاسخ
گزینه (5) درست است.