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