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