Processing math: 88%

المپدیا

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

ابزار کاربر

ابزار سایت


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

مافیلا

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


ابزار صفحه