المپدیا

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

ابزار کاربر

ابزار سایت


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

می‌دونیم همه ماها تو اصل هشتی

یک گراف ساده را نیمایی گوییم، اگر ۳۰ رأسی بوده و هم‌چنین دور به طول کم‌تر از شش نداشته باشد. بیشینه‌ی عدد رنگی رأسی در میان تمام گراف‌های ساده‌ی نیمایی را $k$ در نظر بگیرید. شما در این سوال باید دو عدد طبیعی $a$ و $b$ ارائه دهید و اثبات کنید که $a \le k \le b$ است.

نحوه‌ی امتیازدهی: در صورتی که $b-a \le 1$ باشد تا سقف ۱۰۰ امتیاز، در صورتی که $b-a = 2$ باشد تا سقف ۵۰ امتیاز و در صورتی که $b-a = 3$ باشد تا سقف ۲۰ امتیاز خواهید گرفت.


ابزار صفحه