المپدیا

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

ابزار کاربر

ابزار سایت


سوالات المپیاد:دوره‌ی تابستان:متفرقه:سوال ۷

زوج‌های فرد

روی هر راس گراف $G$ یک عدد قرار دارد. دو نفر بازی زیر را روی این گراف انجام می‌دهند:

هر نفر در نوبت خود یک یال را انتخاب می‌کند و اگر اعداد دو سر این یال $a$‌ و $b$ باشند اعداد روی این دو راس را به $a+b$ تغییر می‌دهد و اگر $a+b$ فرد بود یال انتخاب شده را حذف می‌کند. کسی که بتواند اعداد روی تمامی راس‌ها را فرد کند بازی را برده است. اگر در ابتدا تعداد اعداد زوج، فرد باشد ثابت کنید نفر اول همواره می‌تواند طوری بازی کند که نبازد.


ابزار صفحه