بازی دو نفره «یال‌ها در گراف» به این صورت است:

گراف $G$ با $n$ راس $1,2,…,n$ و بدون یال را در نظر بگیرید. دو بازیکن به ترتیب یکی بعد از دیگری بازی می‌کنند( یک بازیکن در نوبت‌های زوج و دیگری در نوبت‌های فرد) در نوبت $i$ ام بازیکنی که نوبتش است باید یالی از گراف را وصل کند که اختلاف اعداد دو سر آن یال دقیقا $n-i$ باشد و با یال‌های قبلی کشیده شده در نوبت‌های قبل دوری در $G$ تشکیل ندهد. بازیکنی که نتواند در نوبتش یالی بکشد بازنده است.

الگوریتمی چند جمله‌ای بر حسب $n$ پیدا کنید که با گرفتن $n$، برنده‌ی بازی را پیدا کند و به جای او بازی کند.

• سوال بعد