Тема КФУ (олимпиада Казанского Федерального Университета)

Комбинаторика на КФУ

Вспоминай формулы по каждой теме

Решай новые задачи каждый день

Вдумчиво разбирай решения

ШКОЛКОВО.
Готовиться с нами - ЛЕГКО!

Подтемы раздела кфу (олимпиада казанского федерального университета)

Решаем задачи

Ошибка.
Попробуйте повторить позже

Задача 1#106014

В каждую клетку таблицы $21×22$ вписано число $1$ или $− 1.$ Под каждым столбцом записано произведение всех чисел столбца, а рядом с каждой строкой — произведение чисел строки. Какое наименьшее неотрицательное значение может принимать сумма всех этих произведений?

Показать ответ и решение

Сначала рассмотрим “крайнюю” ситуацию. Если во всех клетках таблицы числа равны $+ 1,$ то и все произведения равны $+ 1,$ а их общая сумма равна $21+ 22=43.$

Если мы сменим знак в одной из клеток, то изменится знак в произведении чисел одной строки и одного столбца. Значит, сумма всех произведений изменится на величину $± 2±2,$ то есть это изменение может равняться $4,0$ или $− 4.$ Таким образом, после замены знаков в нескольких клетках таблицы значение суммы может измениться лишь на слагаемое, кратное $4.$

Взяв за основу таблицу, заполненную числами $+ 1,$ и меняя знаки в соответствующих клетках (чтобы придти к исходной таблице), мы получим значение суммы $43 − 4k.$ Наименьшее неотрицательное значение выражения $43 − 4k,$ очевидно, равно $3,$ и оно достигается при целом $k =10.$

Осталось привести пример таблицы, для которой указанное значение суммы произведений равно $3.$ Расставим сначала во всех клетках таблицы $21× 22$ числа $+ 1,$ а затем заменим знак $+$ на $−$ у $10$ чисел, стоящих, например, на диагонали, идущей из левого верхнего угла в нижний. Для полученной таблицы сумма всех произведений равна $43− 10⋅4 =3.$

Ответ:

$3$

Бандлы и наборы

Комбо-тарифы сразу по нескольким предметам

Ошибка.
Попробуйте повторить позже

Задача 2#88475

Сеть дорог соединяет $n$ населенных пунктов. Из каждого пункта выходит не более $3$ дорог. Если между какими-либо двумя пунктами нет дороги, то есть третий пункт, соединенный с ними обоими. Каково максимальное возможное значение $n?$

Показать ответ и решение

Будем называть населенные пункты точками. Возьмем любую точку $A.$ Она соединена не более, чем с тремя точками $B,C,D.$ Любая другая точка $X$ должна быть соединена с одной из точек $B,C,D$ (поскольку она не соединена с $A$ ). Но каждая из них уже соединена с $A,$ так что может быть соединена не более чем с двумя другими точками, Следовательно, общее число точек не более $1+ 3+ 3⋅2= 10.$

Пример, показывающий, что $10$ точек возможно можно построить, например, так. Обозначим точки $A,B,C,D,E,F,G,H,I,J.$ Проведем дороги $AB,AC,AD,BE,BF, CG,CH,DI,DJ,EH,EJ,FG,F I,GJ$ и $HI.$

Ответ:

$10$

Курсы

Всё необходимое для достижения цели

Интенсивы

Глубокий разбор тем, требующих дополнительного внимания