Принцип крайнего, индукция и другие методы в комбигео

Оценка. Докажем индукцией по ( — натуральные), что из множества целочисленных точек точке

можно выбрать не более так, чтобы для каждой отмеченной точки количество точек, больших её, и количество точек, меньших её, отличались не более, чем на База для верна. Предположим, что утверждение верно при

Рассмотрим где Предположим, что среди отмеченных точек есть точки и такие, что Предположим, что существует отмеченная точка большая Тогда для точки должна найтись точка большая её (так как больше хотя бы отмеченных точек), и так далее, откуда получаем противоречие. Аналогично, для точки нет отмеченной точки, меньшей её. Из наших рассуждений сразу следует, что для точки есть ровно одна точка, меньшая её, и для точки есть ровно одна отмеченная точка, большая Тогда все оставшиеся отмеченные точки лежат в прямоугольниках и Причем точки и нельзя сравнить ни с какими другими отмеченными точками. Тогда по предположению индукции всего отмеченных точек не более

То есть внутри можно отметить не более точек.

Пример. Будем отмечать точки с координатами Если то будет отмечено ровно точек. Если то будет отмечено точек. Если то будет отмечено точек.