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