Клетчатая решётка (координатная плоскость) и точки, отрезки, прямые на ней
Ошибка.
Попробуйте повторить позже
Лес представляет собой координатную плоскость, в некоторых узлах которой растут ёлки. Всего ёлок больше миллиона. Докажите, что можно срубить более 100000 ёлок так, чтобы расстояние между любыми двумя срубленными ёлками было больше 3. (Узлом называется точка, обе координаты которой целые; ёлки считаем точками.)
Источники:
Подсказка 1
Когда нас просят доказать, что что-либо возможно, то один из вариантов решения это просто привести пример. Так и в этой задаче, нам нужно придумать пример вырубки ёлок, удовлетворяющей условию.
Подсказка 2
Получается, нам нужно выбрать больше 100000 ёлок так, чтобы расстояние между любыми двумя из них было больше 3. Может быть не понятно, по какому принципу их вообще выбирать. В таких случаях полезно каким-либо образом разбить ёлки на группы так, чтобы одна из групп была искомой. Но на какое количество групп разбивать?
Подсказка 3
Вспомним принцип Дирихле и посмотрим на числа. Заметим, что если разбить ёлки на 10 групп, то в одной из них точно будет больше 100000 штук. Тогда нам нужно, чтобы внутри каждой группы расстояния между любыми двумя ёлками было более 3.
Подсказка 4
Если не получается придумать разбиение, попробуйте посмотреть на эту задачу по-другому. Например, попытаться разбивать не ёлки, а узлы. Так же не забывайте про количество групп, попробуйте использовать остатки при делении на 10.
Раскрасим узлы в 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%!
Крути рулетку
и выигрывай призы!
Крути рулетку и покупай курсы со скидкой, которая привязывается к вашему аккаунту.
Бесплатное онлайн-обучение
Для школьников из приграничных территорий России, проживающих в ДНР, ЛНР, Херсонской, Запорожской, Белгородской, Курской, Брянской областях и Крыму.
Налоговые вычеты
Узнай, как получить налоговый вычет при оплате обучения в «Школково».
Специальное предложение
для учителей
Бесплатный доступ к любому курсу подготовки к ЕГЭ, ОГЭ и олимпиадам от «Школково». Мы с вами делаем общее и важное дело, а потому для нас очень значимо быть чем-то полезными для учителей по всей России!
Вернём деньги за курс
за твою сотку на ЕГЭ
Сдать экзамен на сотку и получить обратно деньги за подготовку теперь вполне реально!
