ابوال و جبارزید با هم بازی می کنند.ابتدا ابوال یک گراف کامل ۲۰۲۲ راسی با رأس های $v_1$ تا $v_{2022}$ در ذهن خود می سازد که هر یال آن آبی یا قرمز است. جبارزید باید رنگ تمام یال های این گراف را بفهمد. ابتدا جبارزید مجموعه ای از یال های گراف را به ابوال می دهد. او باید به تعداد یال های مجموعه، به ابوال پول بدهد. سپس ابوال علاوه بر گفتن رنگ هر یال مجموعه، به ازای هر دور همیلتونی گراف، تعدادی یال های قرمز آن دور را می‌گوید. ابوال برای این کار (گفتن تعداد یال های قرمز دورهای هملیتونی)، پولی از جبارزید نمی گیرد. اگر هر دو نفر به‌طور بهینه بازی کنند، جبارزید چقدر پول به ابوال خواهد داد؟
نکته: با ارائه ی یک کران بالا و یک کران پایین برای پاسخ مسئله که اختلاف آن ها حداکثر ۱۰ باشد، تا سقف ۸۰ امتیاز می توانید بگیرید. هم چنین مقدار پاسخ مسئله به ازای گراف n رأسی ( به جای ۲۰۲۲) $f(n)$ بنامید. در صورت ارائه ی $θ(f(n))$ به جای پاسخ مسئله تا سقف ۵۰ امتیاز می توانید بگیرید.

• سوال قبل