المپدیا

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

ابزار کاربر

ابزار سایت


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

بازی همه زوج

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

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

$(a$ $G$ گراف $Q_k$ (مکعب $k$ بعدی) و تعداد اعداد زوج حداقل $2^{k-1}+1$ باشد.

$(b$ $G$ گراف $K_n$ (گراف کامل $n$ راسی) و تعداد اعداد زوج و فرد هر کدام حداقل ۲ باشد.


ابزار صفحه