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