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