Клетчатая решётка (координатная плоскость) и точки, отрезки, прямые на ней
Ошибка.
Попробуйте повторить позже
Лес представляет собой координатную плоскость, в некоторых узлах которой растут ёлки. Всего ёлок больше миллиона. Докажите, что можно срубить более 100000 ёлок так, чтобы расстояние между любыми двумя срубленными ёлками было больше 3. (Узлом называется точка, обе координаты которой целые; ёлки считаем точками.)
Источники:
Раскрасим узлы в 10 цветов так, чтобы узлы одного цвета образовывали сетку из квадратов со стороной . Например, пусть цвет узла с
координатами (
) определяется остатком от деления числа
на 10 (считаем, что деревья растут в центрах
квадратов):
0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 0 |
7 | 8 | 9 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
4 | 5 | 6 | 7 | 8 | 9 | 0 | 1 | 2 | 3 | 4 |
1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 0 | 1 |
8 | 9 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
5 | 6 | 7 | 8 | 9 | 0 | 1 | 2 | 3 | 4 | 5 |
2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 0 | 1 | 2 |
9 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
6 | 7 | 8 | 9 | 0 | 1 | 2 | 3 | 4 | 5 | 6 |
3 | 4 | 5 | 6 | 7 | 8 | 9 | 0 | 1 | 2 | 3 |
0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 0 |
По принципу Дирихле, в какой-то из десяти цветов окрасились более 100 тысяч ёлок. Тогда все эти ёлки можно срубить, поскольку
расстояние между любыми двумя из них не меньше .
Специальные программы

Программа
лояльности v2.0
Приглашай друзей в Школково и получай вознаграждение до 10%!

Крути рулетку
и выигрывай призы!
Крути рулетку и покупай курсы со скидкой, которая привязывается к вашему аккаунту.

Бесплатное онлайн-обучение
Для школьников из приграничных территорий России, проживающих в ДНР, ЛНР, Херсонской, Запорожской, Белгородской, Курской, Брянской областях и Крыму.

Налоговые вычеты
Узнай, как получить налоговый вычет при оплате обучения в «Школково».

Специальное предложение
для учителей
Бесплатный доступ к любому курсу подготовки к ЕГЭ, ОГЭ и олимпиадам от «Школково». Мы с вами делаем общее и важное дело, а потому для нас очень значимо быть чем-то полезными для учителей по всей России!

Вернём деньги за курс
за твою сотку на ЕГЭ
Сдать экзамен на сотку и получить обратно деньги за подготовку теперь вполне реально!