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

الف) مظفر ادعا می‌کند پس از آن که تعداد یال‌های قرمز در هر یک از دورهای ۱۴۰۰ رأسی را از ابوالفضل بپرسد، می‌تواند رنگ یال‌های گراف ابوالفضل را در هر شکلی از رنگ‌آمیزی بفهمد. نشان دهید ادعای مظفر اشتباه است. (۱۰نمره)

ب) به مظفر نشان دهید اگر دست از لجبازی بردارد و علاوه بر دورهای ۱۴۰۰ رأسی، تعداد یال‌های قرمز در هر یک از دورهای ۱۳۹۹ رأسی را هم بپرسد، آنگاه می‌تواند رنگ یال‌های گراف ابوالفضل را در هر شکلی از رنگ‌آمیزی بفهمد(۱۴نمره)

• سوال بعد
• سوال قبل