Клетчатые задачи и комбинаторные подсчёты на СПБГУ
Ошибка.
Попробуйте повторить позже
В некоторых клетках полоски 
поставлено по одной фишке. В каждую из пустых клеток записывается число, равное модулю
разности количества фишек слева и справа от этой клетки. Известно, что все записанные числа различны и отличны от нуля. Какое
наименьшее количество фишек может быть расставлено в клетках?
Источники:
Подсказка 1!
Итак, попробуем проанализировать, как вообще выглядят эти числа в пустых клетках. Давайте подумаем, насколько они могут быть большие, и какая у них может быть четность!
Подсказка 2!
Да, так как при переходе через фишку модуль разности изменяется на четное число, разности всегда одной четности, и, конечно, не могут быть больше n (за n возьмем число фишек)! Так-так-так, ну, теперь давайте поймем, а сколько их вообще тогда может быть?
Подсказка 3!
Верно, их не больше половины n. А всего их 2021-n... Попробуйте доделать оценку и пример!
Пусть количество расставленных фишек равно 
Заметим, что числа в пустых клетках лежат в диапазоне от 
до 
и имеют
одинаковую четность, поскольку при переходе через блок из фишек размера 
значение числа поменяется на 
чётность модуля не
поменяется. По принципу Дирихле количество пустых клеток (равное 
) не больше половины, то есть не больше ![[n+1]
2 .](/api/latex-service/v1/GetSession/79260/index-6f6e6b5095b9ffb089a203698e5b4a45.svg)
То
есть
![[n+ 1] n +1 4041
2021− n≤ --2- ≤ --2- =⇒ n≥ --3-= 1347](/api/latex-service/v1/GetSession/79260/index-61211eaf7ee0b97eaad835d610c64bc5.svg)
Осталось привести пример для 
где единицами обозначены фишки, а нулями — пустые клетки. Здесь в пустых ячейках окажутся числа
Специальные программы
Программа
лояльности v2.0
Приглашай друзей в Школково и получай вознаграждение до 10%!
Крути рулетку
и выигрывай призы!
Крути рулетку и покупай курсы со скидкой, которая привязывается к вашему аккаунту.
Бесплатное онлайн-обучение
Для школьников из приграничных территорий России, проживающих в ДНР, ЛНР, Херсонской, Запорожской, Белгородской, Курской, Брянской областях и Крыму.
Налоговые вычеты
Узнай, как получить налоговый вычет при оплате обучения в «Школково».
Специальное предложение
для учителей
Бесплатный доступ к любому курсу подготовки к ЕГЭ, ОГЭ и олимпиадам от «Школково». Мы с вами делаем общее и важное дело, а потому для нас очень значимо быть чем-то полезными для учителей по всей России!
Вернём деньги за курс
за твою сотку на ЕГЭ
Сдать экзамен на сотку и получить обратно деньги за подготовку теперь вполне реально!
