Доказательства и комбинаторные модели
Строить доказательства, контрпримеры и конечные подсчёты, не заменяя обоснование перебором примеров.
Объяснения и разобранные примеры
Как доказать чётность выражения без перебора чисел
доказать чётность выражения без перебора чисел. Произведение n(n+1) чётно для любого целого n: из двух соседних целых одно чётное.
Когда принцип ящиков гарантирует совпадение
Когда принцип ящиков гарантирует совпадение. Если семнадцать книг распределены по пяти полкам, хотя бы на одной полке окажется не меньше четырёх книг.
Как контрпример отличает утверждение от обратного
контрпример отличает утверждение от обратного. Из «если P, то Q» автоматически не следует «если Q, то P».
Как перечислить положительные дроби, не пропустив знаменатель
перечислить положительные дроби, не пропустив знаменатель. Положительные рациональные числа можно перечислить по возрастанию суммы числителя и знаменателя, оставляя только несократимые дроби.
Бесконечный спуск: почему меньших положительных решений не хватит
Бесконечный спуск: почему меньших положительных решений не хватит. Бесконечный спуск превращает предполагаемое решение в другое с меньшей положительной целочисленной мерой.
Почему раскраска доски может запретить покрытие домино
Почему раскраска доски может запретить покрытие домино. Прямоугольное домино 1 на 2 закрывает две соседние по стороне клетки разных цветов шахматной раскраски.
Принцип крайнего: зачем выбирать самый большой элемент
Принцип крайнего: зачем выбирать самый большой элемент. Принцип крайнего предлагает исследовать элемент с предельным свойством: наибольший, наименьший, самый длинный или ближайший.
Математическая индукция: зачем нужны база и переход
Математическая индукция: зачем нужны база и переход. Математическая индукция требует доказать начальный случай и переход от произвольного допустимого k к k+1.
Как построение нового числа доказывает бесконечность простых
построение нового числа доказывает бесконечность простых. Для любого конечного списка простых возьмём их произведение и прибавим единицу.
Как неизменный остаток запрещает достижение игрового состояния
неизменный остаток запрещает достижение игрового состояния. Если каждый разрешённый ход меняет число на кратное m, его остаток по модулю m сохраняется.
Как посчитать допустимые порядки при заданных зависимостях
посчитать допустимые порядки при заданных зависимостях. Допустимый порядок сохраняет каждую исходную зависимость.
Как взаимно однозначное соответствие доказывает равенство количеств
взаимно однозначное соответствие доказывает равенство количеств. Биекция сопоставляет каждому объекту одного набора ровно один объект другого без совпадения образов разных объектов и без пропусков целевого набора.
Почему число раскрасок с точностью до поворота нельзя всегда делить на число поворотов
Почему число раскрасок с точностью до поворота нельзя всегда делить на число поворотов. Лемма Бёрнсайда считает классы раскрасок как среднее число раскрасок, сохраняемых каждым разрешённым преобразованием.
Почему все бесконечные двоичные последовательности нельзя перечислить
Почему все бесконечные двоичные последовательности нельзя перечислить. Для любого предполагаемого списка бесконечных двоичных последовательностей можно изменить диагональные биты и получить последовательность, отличающуюся от каждой строки хотя бы в одном месте..
Как отражение плохого пути считает допустимые скобочные структуры
отражение плохого пути считает допустимые скобочные структуры. У правильной последовательности из n пар скобок баланс никогда не отрицателен и в конце равен нулю.
Почему доказательство через противоположное условие сохраняет утверждение
Почему доказательство через противоположное условие сохраняет утверждение. Высказывания P⇒Q и ¬Q⇒¬P равносильны.
Чем определение отличается от доказанного признака
Чем определение отличается от доказанного признака. Определение закрепляет значение понятия.
Как один набор пар даёт два способа подсчёта
один набор пар даёт два способа подсчёта. При двойном подсчёте один и тот же конечный набор объектов считают двумя способами.
Как коэффициент произведения кодирует набор допустимых выборов
коэффициент произведения кодирует набор допустимых выборов. Для каждого независимого выбора записывают сумму разрешённых степеней x.
Почему диагональная сумма сочетаний даёт следующее сочетание
Почему диагональная сумма сочетаний даёт следующее сочетание. Для целых n≥r≥0 сумма C(r,r)+C(r+1,r)+…+C(n,r) равна C(n+1,r+1).
Почему разбиения числа отличаются от упорядоченных сумм
Почему разбиения числа отличаются от упорядоченных сумм. В разбиении числа перестановка положительных слагаемых не создаёт нового объекта.
Как разбор случаев доказывает утверждение без пропусков
разбор случаев доказывает утверждение без пропусков. Разбор случаев доказывает общее утверждение, если каждый допустимый объект попадает хотя бы в один рассмотренный случай и внутри каждого случая получен нужный вывод..
Как запрещённые позиции превращают перестановку в задачу включения-исключения
запрещённые позиции превращают перестановку в задачу включения-исключения. Из всех перестановок исключают нарушения запретов по включению-исключению.
Как распределить одинаковые предметы с нижними границами
распределить одинаковые предметы с нижними границами. Из каждой переменной вычитают её обязательный минимум.
Частые вопросы
Как работать с темой «Доказательства и комбинаторные модели»?
Выберите объяснение из списка, восстановите ход примера своими словами и ответьте на проверочный вопрос. Если к теме подключён инструмент, им можно проверить свои данные.
Можно ли вернуться к более простой теме?
Да. Откройте учебную карту или ссылки на необходимые основы перед списком материалов. Уровень по классу помогает выбрать сложность и не ограничивает доступ.