المپدیا

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

ابزار کاربر

ابزار سایت


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

مافیلا

فرض کنید $m$ و $k$ دو عدد طبیعی باشند. مافیلاباس تضمین کرده است که اگر $n$ نقطه‌ی دل‌خواه در صفحه داشته باشیم که $n \ge m$ و بتوان هر $m$ نقطه از آن‌ها را توسط $k$ خط پوشاند، آن گاه می‌توانیم تمام $n$ نقطه را توسط $k$ خط بپوشانیم. ثابت کنید اگر $m < \binom{k+2}{2}$ باشد، تضمین مافیلاباس اشتباه است.


ابزار صفحه