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