Введение 0:00 Приветствие и приглашение подписаться на канал. Объяснение темы лекции: величины, которые не меняются в процессе операций. Упоминание актуальности темы и её применения в олимпиадных задачах.
Задача с фишками 0:55 Описание задачи: нужно переставить 100 фишек в обратном порядке, меняя их через одну. Пронумерование фишек и анализ условий задачи. Вывод: переставить фишки в обратном порядке невозможно, так как чётность позиций не меняется.
Задача с платками 3:53 Описание ситуации: в раздевалке 20 платков и 17 девочек, каждая девочка либо забирает, либо вешает платок. Анализ изменения чётности количества платков после каждой девочки. Вывод: после ухода всех девочек должно остаться нечётное количество платков, что противоречит условию задачи.
Анализ величины x 6:52 Введение величины x = количество платков - количество девочек. Рассмотрение изменений величины x при действиях девочек. Подтверждение, что величина x не меняется, и вывод о невозможности ситуации, когда в итоге остаётся 10 платков.
Определение синонимов 9:01 Рассматриваются слова, состоящие из двух букв «м» и «о». Слова считаются синонимами, если можно добавлять или убирать «о» или «мм» без изменения смысла. Вопрос: являются ли синонимами слова «омм-о-о» и «о-о-мм»?
Анализ количества букв 9:59 Количество букв «м» и «о» в словах не одинаково. Разность между количеством букв «м» и «о» является инвариантом. Доказывается, что слова «омм-о-о» и «о-о-мм» не могут быть синонимами, так как инвариант не равен нулю.
Таблица с суммой чисел 11:59 В таблице m на n сумма чисел в любой строке или столбце равна 1. Доказывается, что m = n, используя два способа подсчёта суммы чисел: по строкам и по столбцам. Подчёркивается, что сумма чисел во всей таблице остаётся неизменной при любых манипуляциях.
Процесс суммирования цифр 13:55 Из числа x вычитается сумма его цифр, результат записывается на доске. Процесс повторяется до получения однозначного числа. Задача: определить, какое однозначное число останется после операций с числом 8^1989.
Признаки делимости 15:50 Используются признаки делимости на 3 и 9 для анализа процесса суммирования. Число сравнимо с суммой его цифр по модулю 9. Выясняется, что исходное число сравнимо с 8 по модулю 9.
Решение задачи 17:47 Определяется, что однозначное число, которое останется в конце, равно 8. Объясняется, что из всех однозначных чисел только 8 сравнимо с 8 по модулю 9. Подтверждается, что в итоге останется число 8.
Операция с числами 18:44 Заданы 20 натуральных чисел. Производится операция: вместо двух чисел a и b записывается a + b - 1. После 19 операций остаётся одно число.
Анализ процесса 19:42 Количество чисел уменьшается на 1 после каждой операции. Рассматривается инвариант: сумма всех чисел минус количество операций.
Понятие полуинварианта 20:42 Полуинвариант — это величина, которая меняется по известным правилам. В данном случае сумма чисел уменьшается на 1 после каждой операции.
Расчёт суммы чисел 21:42 Сумма чисел от 1 до 20: 20 * 21 / 2 = 210. Количество операций: 19. Итоговая сумма: 210 - 19 = 191.
Задача о бурьяне 22:42 Поле 10x10 клеток, 9 клеток поросли бурьяном. Клетка зарастает бурьяном, если хотя бы две соседние клетки уже заражены. Необходимо доказать, что всё поле не сможет зарасти бурьяном.
Анализ процесса заражения 23:38 Если клетки изолированы, заражение не произойдёт. При наличии двух соседних заражённых клеток происходит вторичное заражение. Если заражены две соседние клетки, заражаются все клетки с двумя соседями.
Заражение клеток 25:34 Клетки, имеющие две соседние с бурьяном стороны, заражаются. Клетка с тремя соседями также заражается. Клетка, окружённая бурьяном со всех сторон, заражается.
Анализ границы заросшего участка 26:23 Рассматривается изменение границы заросшего участка. Изначально две клетки образуют прямоугольник с периметром 8, который превращается в квадрат 2x2. Аналогично, три клетки образуют прямоугольник 3x2.
Примеры зарастания 27:20 Две клетки, имеющие контакт с третьей, образуют прямоугольник с периметром 8. Три клетки, окружённые четырьмя, образуют прямоугольник 3x3. Вокруг одной клетки все клетки зарастают, образуя квадрат 3x3.
Инвариантность периметра 28:20 Периметр заражённых клеток не увеличивается в процессе заражения. Возможны случаи, когда периметр уменьшается. Периметр остаётся неизменным или уменьшается при заражении.
Максимальный периметр 30:13 Максимальный периметр возможен при изолированных клетках 36. Если клетки изначально вместе, периметр уменьшается. Изначальный периметр меньше или равен 36.
Итог 31:13 Конечный периметр при заражении всего поля должен быть 40. Так как периметр не увеличивается, это невозможно. Всё поле зарасти бурьяном не может.
Введение в задачу 32:01 На доске написаны числа: 1, 1/2, 1/3 и так далее до 1/100. Из двух чисел а и б получается новое число: а + б + аб. Операция повторяется 99 раз, в конце остаётся одно число.
Анализ формата записи 33:01 Формат записи чисел напоминает решение уравнений и неравенств. Выражение 1 + а + б + аб похоже на 1 + а * 1 + б. Важно учесть отличие на единицу.
Построение инварианта 34:01 Строится инвариант для 100 чисел: 1 + а1 + а2 + а3 + ... + а100. Вместо двух скобок записывается одна: 1 + а1 + а2 + а1 * а2.
Применение операции 35:02 Две скобки заменяются одной: 1 + а1 + а2 + а1 * а2 = 1 + а1 + а2 + а1 * а2. Процесс повторяется, количество скобок уменьшается.
Финальная операция 37:01 На последнем шаге две скобки снова заменяются одной. В итоге остаётся выражение 1 + ат, где ат = ока + арен + ока * арен. Последнее число отличается от скобки на единицу.
Подсчёт итогового числа 38:58 Итоговое число равно сумме всех скобок минус один: 1 + ат - 1. Раскрываются скобки, проводится подсчёт.
