المپدیا

دانش‌نامه‌ی المپیاد کامپیوتر ایران

ابزار کاربر

ابزار سایت


سوالات المپیاد:دوره ی تابستان:دوره ی ۲۳:ترکیبیات:سوال ۴

سوال ۴

گراف کاملی با ‎۲۰۱۴‎ راس در اختیار داریم. دو راس ‎$v$‎ و ‎$u$‎ داده شده‌اند. دو نفر بازی زیر را روی این گراف انجام می‌دهند‎:‎

هر نفر در نوبت خود یکی از یال‌های گراف باقیمانده را حذف می‌کند. در صورتی که پس از حرکت یک نفر، هیچ مسیری از راس ‎$u$‎ به راس ‎$v$‎ وجود نداشته باشد او بازنده خواهد شد.

در صورتی که هر بازیکن به بهترین شکل بازی خود را انجام دهد، چه کسی استراتژی برد دارد؟ ادعای خود را بیان و اثبات کنید.


ابزار صفحه