الف) دو رنگ آمیزی متفاوت نشان می دهیم که به ازای هر دور به طول 𝑛 جواب هایی که ابوالفضل به مظفر میدهد، یکسان باشد. در رنگ آمیزی اول، رنگ هر یال به جز یال هایی که به رأس با شمارهی ۱ وصل هستند، آبی میباشد. در رنگ آمیزی دوم رنگ هر یال به جز یالهایی که به رأس با شمار هی ۲ وصل هستند، آبی میباشد. دقت کنید که در هر دور به طول 𝑛 درجهی هر رأس دقیقاً ۲ است. در نتیجه، جواب تمام سوال ها در دو رنگ آمیزی ذکر شده، عدد ۲ خواهد بود. بنابراین مظفر حتی با داشتن جواب تمام سوالات نمیتواند تفاوتی بین این دو رنگ آمیزی پیدا کند.

ب) برای هر یال 𝑒 مقدار 𝑓(𝑒) را برابر ۱ می گذاریم اگر این یال قرمز باشد و در غیر این صورت آن را صفر می گذاریم. یک مثلث در گراف در نظر بگیرید که از رأسهای 𝑣۱, 𝑣۲, 𝑣۳ تشکیل شده باشد. حال دور هامیلتونی 𝑣۱, 𝑣۲, . . . , 𝑣𝑛 و دور 𝑣۱, 𝑣۳, 𝑣۴, . . . , 𝑣𝑛 که دوری به طول 𝑛 − ۱ است را در نظر بگیرید. از تفاضل تعداد یال های قرمز این دو دور، مظفر میتواند به مقدار

𝑓({𝑣۱, 𝑣۲}) + 𝑓({𝑣۲, 𝑣۳}) − 𝑓({𝑣۱, 𝑣۳})

دست پیدا کند. به طور مشابه مظفر میتواند

𝑓({𝑣۱, 𝑣۲}) + 𝑓({𝑣۱, 𝑣۳}) − 𝑓({𝑣۲, 𝑣۳})

را به دست آورد. از جمع زدن این دو عبارت مقدار ۲(𝑓({𝑣۱, 𝑣۲}) حاصل میشود. در نتیجه، به ازای هر یال دلخواه 𝑒 مث ل {𝑣۱, 𝑣۲} ، ابوالفضل می تواند 𝑓(𝑒) را به دست آورد و رنگ یال 𝑒 را تشخیص دهد.

سلام برای قسمت الف: اگر تمام یال های متصل به یک راس را قرمز کنیم (و بقیه یال ها را آبی کنیم)، در هر دور ۱۴۰۰ راسی دقیقا دو یال قرمز وجود خواهد داشت. بنابراین ۱۴۰۰ نوع رنگ آمیزی مختلف (به ازای انجام همین کار روی هریک از ۱۴۰۰ راس) وجود دارد که در آنها، همواره ۲ یال قرمز در هر دور ۱۴۰۰ راسی وجود دارد. یعنی در هر یک از این رنگ آمیزی ها، مظفر نمی‌تواند با قطعیت رنگ آمیزی ها مشخص کند.