Регион 2018
Готовиться с нами - ЛЕГКО!
Ошибка.
Попробуйте повторить позже
Дана клетчатая доска 
Фигура гепард из произвольной клетки 
бьёт все клетки квадрата 
с центральной клеткой
за исключением клеток, находящихся с 
в одном столбце или одной строке. Какое наибольшее количество гепардов, не бьющих друг
друга, можно расставить на доске?
Источники:
Подсказка 1
Так как здесь у нас речь идёт про фигуру, бьющую определённым образом поля, то давайте попробуем для оценки разбить доску на части. Доска у нас 1000 на 1000. И гепард бьёт клетки в определённом квадрате. Тогда на какие части хорошо бы разбить доску? К тому же они должны быть удобными для работы и оценки.
Подсказка 2
Верно, давайте разобьём доску на квадраты 10 на 10. Тогда нужно понять, сколько там может стоять максимум гепардов. Пусть мы поставили одного гепарда куда-то в квадрат. Могут ли в таком случае другие два гепарда встать в разных вертикалях и горизонталях?
Подсказка 3
Да, такого не может произойти, так как в таком случае они будут бить друг друга, даже если будут стоять на одной вертикали и горизонтали с исходным. Значит, всех гепардов в квадрате 10 на 10 мы ставим в один ряд, откуда их не более 10. Остался пример. Так как мы всю задачу как-то работали с числом 10, то как лучше всего их расположить в таком случае?
Подсказка 4
Верно, мы можем расположить их в один столбец с интервалом в 10 клеток. Тогда несложно увидеть, что всё сработает. Победа!
Разобьём доску на 
квадратов 
Покажем, что в каждом квадрате может стоять не более 
гепардов, не бьющих друг друга
— отсюда будет следовать, что общее число гепардов не может превосходить 
Рассмотрим произвольный квадрат 
размера 
и произвольного гепарда 
в нём. Гепард 
бьёт все клетки квадрата, кроме
клеток, лежащих с ним в одной строке или в одном столбце. Если один из остальных гепардов 
в квадрате 
стоит в одной строке с 
а ещё один, 
— в одном столбце с 
то 
и 
стоят в разных строках и столбцах и, следовательно, бьют друг друга; это
невозможно. В противном случае, без ограничения общности, все гепарды в квадрате 
стоят в одной строке с 
то есть их не больше
Таким образом, мы доказали, что общее число гепардов не может превосходить 
осталось привести пример,
когда эта оценка достигается. Пронумеруем столбцы доски подряд числами 
Расставим гепардов на все
клетки столбцов, номера которых делятся на 
Этих гепардов будет 
и они не будут бить друг
друга.
Специальные программы
Программа
лояльности v2.0
Приглашай друзей в Школково и получай вознаграждение до 10%!
Крути рулетку
и выигрывай призы!
Крути рулетку и покупай курсы со скидкой, которая привязывается к вашему аккаунту.
Бесплатное онлайн-обучение
Для школьников из приграничных территорий России, проживающих в ДНР, ЛНР, Херсонской, Запорожской, Белгородской, Курской, Брянской областях и Крыму.
Налоговые вычеты
Узнай, как получить налоговый вычет при оплате обучения в «Школково».
Специальное предложение
для учителей
Бесплатный доступ к любому курсу подготовки к ЕГЭ, ОГЭ и олимпиадам от «Школково». Мы с вами делаем общее и важное дело, а потому для нас очень значимо быть чем-то полезными для учителей по всей России!
Вернём деньги за курс
за твою сотку на ЕГЭ
Сдать экзамен на сотку и получить обратно деньги за подготовку теперь вполне реально!
