Вспоминай формулы по каждой теме
Решай новые задачи каждый день
Вдумчиво разбирай решения
ШКОЛКОВО.
Готовиться с нами - ЛЕГКО!
Подтемы раздела игры
Решаем задачу:

Ошибка.
Попробуйте повторить позже

Задача 1#73188

Коля и Саша играют в игру на клетчатой доске 100× 100.  Коля начинает и своим ходом красит одну клетку в красный цвет, а Саша — в синий. Ходят по очереди, перекрашивать ранее закрашенные клетки нельзя. В конце игры Коля ищет красный клетчатый прямоугольник наибольшей площади, и Саша платит ему столько рублей, сколько в этом прямоугольнике клеток. Какой наибольший заработок может гарантировать себе Коля, как бы ни играл Саша?

Показать ответ и решение

Играя за Сашу, поделим всю доску на квадратики 2 ×2,  затем введём шахматную раскраску на них. “Чёрные” квадратики будем красить “вертикально”, то есть на ход Пети закрашивать вторую клетку из вертикальной доминошки, в которую он попал. В “белых” будем действовать аналогично “горизонтально”. В итоге все квадратики будут иметь один из видов (заменим красный и синий цвета на крестики и нолики)

|---|--| |--|---| |--|---||--|---| |--|---| |--|---|
|∘--|∘-| |×-|-×-| |×-|-∘-||-∘|-×-| |×-|-∘-| |∘-|-×-|
-×---×-- -∘---∘-- -×---∘-|--∘--×-| -∘---×-- -×---∘--

При этом первые два не могут быть рядом (будем звать их горизонтальными), как и 3,4  (вертикальные), а 5,6  можно получить в любом квадратике (диагональные). Нетрудно видеть, что при таких условиях из них можно сложить “полосу” не длиннее четырёх крестиков (ширины 1  ). Для этого нужно взять горизонтальный, а затем добавить по бокам вертикальный и диагональный, либо наоборот. Если же рассматривать полосу ширины два, то она не может иметь длину больше двух. Действительно, либо она идёт прямо по квадратику и имеет длину не более одного, либо идёт между квадратиками, тогда хотя бы один из них не является вертикальным (считаем, что полоса ориентирована вертикально), откуда даже её общая часть с ними имеет длину не более единицы. В итоге максимальная длина такой полосы, если она находится на пересечении 4  квадратиков, будет равна 2,  площадь — 4.  Полоса длины три или четыре (а шире их не бывает) имеет длину не более единицы, поскольку иначе бы существовал квадратик полностью из крестиков либо два горизонтальных/вертикальных были бы рядом. В результате такая стратегия приводит к максимальному выигрышу 4  для Коли.

Чтобы добиться этого выигрыша, Коле нужно покрасить фигуру ниже (можно убедиться, что так сделать можно всегда, если Саша хочет избежать фигуры площади 4  )

|--|--|---|--|
|⋅-|⋅-|-∘-|⋅-|
|⋅-|∘-|-×-|⋅-|
|⋅-|×-|-×-|⋅-|
|⋅-|∘-|-×-|⋅-|
-⋅--⋅---∘--⋅-|

Где нолики стоят там, где они должны быть, чтобы фигура площади 4  не получилась уже на следующем ходу. Далее Коля может воспользоваться неограниченной с двух сторон последовательностью из двух крестиков в центре — её нетрудно за два хода “вытянуть” до длины 4.

Ответ:

 4

Специальные программы

Все специальные программы

Программа
лояльности v2.0

Приглашай друзей в Школково и получай вознаграждение до 10%!

Крути рулетку
и выигрывай призы!

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

Бесплатное обучение
в Школково

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

Налоговые вычеты

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

Специальное предложение
для учителей

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

Вернём деньги за курс
за твою сотку на ЕГЭ

Сдать экзамен на сотку и получить обратно деньги за подготовку теперь вполне реально!

cyberpunkMouse
cyberpunkMouse
Рулетка
Вы можете получить скидку в рулетке!