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