Олимпиадная комбинаторика: методы и стратегии

Основы перечисления: правила суммы и произведения, сочетания и перестановки

Добро пожаловать в курс «Олимпиадная комбинаторика». Мы начинаем наше путешествие с фундамента, на котором строится вся дискретная математика. Комбинаторика — это искусство подсчета. Но не простого пересчета предметов пальцем, а нахождения количества вариантов с помощью логики и формул, даже если этих вариантов миллиарды.

В олимпиадных задачах часто спрашивают: «Сколькими способами можно...?» или «Существует ли такая комбинация...?». Чтобы отвечать на эти вопросы, нам нужно освоить четыре кита комбинаторики: правило суммы, правило произведения, перестановки и сочетания.

Два главных правила логики

Прежде чем учить сложные формулы, нужно понять логику выбора. Все комбинаторные задачи сводятся к двум ситуациям: когда мы выбираем «ИЛИ» то, «ИЛИ» это, и когда мы выбираем «И» то, «И» это.

Правило суммы (Логика «ИЛИ»)

Представьте, что вы собираетесь на олимпиаду и хотите взять с собой один фрукт для перекуса. В вазе лежат 3 яблока и 2 груши. Сколькими способами вы можете выбрать один фрукт?

Очевидно, что вы можете взять любое из яблок или любую из груш. Поскольку вы берете только один предмет, варианты складываются.

Где — общее количество способов выбора, — количество яблок, — количество груш.

Формальное определение: Если элемент можно выбрать способами, а элемент — способами, причём выбор исключает одновременный выбор (то есть множества вариантов не пересекаются), то выбрать «либо , либо » можно способами.

!Схема, иллюстрирующая правило суммы: выбор одного предмета из двух непересекающихся групп.

Правило произведения (Логика «И»)

Теперь усложним задачу. Вы хотите взять с собой перекус, состоящий из одного фрукта и одного напитка. У вас есть те же 3 яблока и 2 вида сока (апельсиновый и яблочный). Сколько существует вариантов набора «фрукт + сок»?

Здесь мы совершаем два последовательных выбора. С каждым из 3 яблок мы можем взять любой из 2 соков.

Где — общее количество пар, — количество способов выбрать фрукт, — количество способов выбрать сок.

Формальное определение: Если элемент можно выбрать способами и после каждого такого выбора элемент можно выбрать способами, то пару « и » можно выбрать способами.

!Дерево вариантов, показывающее, как для каждого первого выбора открывается несколько вторых выборов.

> Важно: Правило произведения работает только тогда, когда выбор второго элемента не зависит от того, какой именно первый элемент мы выбрали (или количество вариантов для второго шага остается неизменным).

Факториал: инструмент для больших чисел

В комбинаторике мы постоянно перемножаем последовательные числа (например, ). Для этого придумали специальное обозначение — факториал.

Где (читается «эн факториал») — произведение всех натуральных чисел от 1 до .

Особый случай, который нужно запомнить:

Где — факториал нуля, который по определению равен единице. Это необходимо для того, чтобы комбинаторные формулы работали корректно.

Перестановки (Permutations)

Представьте, что у вас есть 3 разные книги, и вы хотите расставить их на полке в ряд. Сколькими способами это можно сделать?

На первое место можно поставить любую из 3 книг.

На второе место — любую из 2 оставшихся.

На третье место — 1 последнюю книгу.

По правилу произведения: способов.

Это и есть перестановка. Перестановками из элементов называются такие соединения, которые состоят из одних и тех же элементов и отличаются друг от друга только порядком их следования.

Формула количества перестановок:

Где — количество перестановок из элементов, — факториал числа .

Пример: Сколькими способами можно выстроить очередь из 5 человек?

Размещения (Arrangements)

Иногда нам нужно не просто переставить все элементы, а выбрать только часть из них и расставить по порядку. Это называется размещением.

Задача: В классе 10 учеников. Нужно выбрать старосту и его заместителя. Сколькими способами это можно сделать?

Здесь важен порядок: быть старостой или заместителем — это разные роли.

Старостой может стать любой из 10 человек.

Заместителем — любой из 9 оставшихся.

Итого: способов.

Формула размещений из по :

Где — количество размещений, — общее количество элементов, — количество выбираемых элементов, — знак факториала.

Давайте проверим формулу на нашем примере:

Сочетания (Combinations)

Это, пожалуй, самая популярная концепция в олимпиадах. Сочетания возникают, когда нам не важен порядок.

Задача: В классе 10 учеников. Нужно выбрать двух дежурных, которые пойдут за мелом. Сколькими способами это можно сделать?

В отличие от задачи про старосту, здесь пара «Иванов и Петров» — это то же самое, что «Петров и Иванов». Они оба просто дежурные, у них равные права.

Если бы мы считали как в размещениях (), мы бы посчитали каждую пару дважды (АБ и БА). Чтобы получить верный ответ, нужно поделить результат размещений на количество перестановок внутри выбранной группы.

Формула сочетаний из по :

Где (читается «це из эн по ка») — число сочетаний, — всего элементов, — сколько выбираем.

Решение задачи про дежурных:

!Визуальное сравнение: когда порядок важен, вариантов больше. Когда порядок не важен, дубликаты отбрасываются.

Как не запутаться: алгоритм выбора формулы

Главная сложность для новичка — понять, какую формулу применить. Задайте себе вопрос: «Важен ли порядок?»

| Вопрос | Тип соединения | Формула | Пример | | :--- | :--- | :--- | :--- | | Участвуют ВСЕ элементы, порядок важен? | Перестановка | | Расставить 5 книг на полке | | Выбираем ЧАСТЬ, порядок важен? | Размещение | | Выбрать 3 призеров (золото, серебро, бронза) из 10 | | Выбираем ЧАСТЬ, порядок НЕ важен? | Сочетание | | Выбрать 3 человек в команду из 10 |

Олимпиадная стратегия: Метод малых чисел

Если вы на олимпиаде забыли формулу или сомневаетесь, важен ли порядок, используйте метод малых чисел.

Пример: Вам нужно выбрать 3 человек из 100. Вы сомневаетесь, это или . Упростите задачу: выберите 2 человек из 3 (А, Б, В). Попробуйте перечислить варианты:

Если порядок не важен (команда): АБ, АВ, БВ. Всего 3. (Это работает формула сочетаний: ).

Если порядок важен (должности): АБ, БА, АВ, ВА, БВ, ВБ. Всего 6. (Это формула размещений: ).

Так вы быстро поймете структуру задачи и сможете применить формулу для больших чисел.

В следующей статье мы разберем более сложные методы, такие как принцип Дирихле и метод шаров и перегородок, но без уверенного владения и двигаться дальше невозможно. Практикуйтесь на задачах ниже!

Принцип Дирихле и метод крайнего в логических задачах

Приветствую вас на второй лекции курса «Олимпиадная комбинаторика». В прошлый раз мы учились считать количество вариантов, используя формулы сочетаний и перестановок. Сегодня мы сместим фокус с вопроса «Сколько?» на вопросы «Существует ли?» и «Можно ли утверждать наверняка?».

В олимпиадной математике есть методы, которые кажутся очевидными на уровне интуиции, но обладают сокрушительной мощностью при строгом доказательстве. Речь пойдет о двух столпах логики: Принципе Дирихле и Методе крайнего.

Принцип Дирихле: Кролики и клетки

Петер Густав Лежён Дирихле, немецкий математик XIX века, сформулировал утверждение, которое в англоязычной литературе называют «Pigeonhole Principle» (Принцип голубей и ящиков), а в русскоязычной традиции часто иллюстрируют кроликами.

Базовая формулировка

Представьте простую ситуацию: у вас есть 5 кроликов и всего 4 клетки. Вы хотите рассадить всех кроликов по клеткам. Как бы вы ни старались, неизбежно произойдет одно событие.

Теорема: Если кроликов рассадить в клеток, то хотя бы в одной клетке окажется не менее двух кроликов.

Здесь: * — количество клеток (контейнеров, групп). * — количество кроликов (предметов, элементов).

Это утверждение доказывается методом «от противного». Предположим, что в каждой клетке сидит не более одного кролика. Тогда всего кроликов не больше, чем . Но по условию у нас кролик. Противоречие. Значит, наше предположение неверно, и где-то сидят двое.

!Визуализация ситуации, когда количество предметов превышает количество контейнеров.

Примеры из жизни и олимпиад

Пример 1: Дни рождения В классе 370 учеников. Докажите, что найдутся двое, отмечающие день рождения в один день.

Решение: В году максимум 366 дней (если год високосный). Пусть «клетки» — это дни года (), а «кролики» — это ученики (). Так как , то по принципу Дирихле хотя бы в один день родились как минимум двое.

Пример 2: Волосы на голове Известно, что на голове человека не более 150 000 волос. В Москве живет более 12 миллионов человек. Докажите, что в Москве найдутся два человека с абсолютно одинаковым количеством волос.

Решение: «Клетки» — это возможные количества волос (от 0 до 150 000). Всего вариантов . «Кролики» — жители Москвы (). Поскольку многократно превышает , таких людей тысячи.

Обобщенный принцип Дирихле

Что если кроликов намного больше, чем клеток? Если мы посадим 10 кроликов в 3 клетки, то где-то будет уже не двое, а больше.

Формулировка: Если предметов разложены в ящиков, то найдется ящик, в котором лежит не менее чем предметов.

Где: * — гарантированное минимальное количество предметов в одной из групп. * — общее количество предметов. * — количество групп (ящиков). * — функция «потолок», означающая округление числа до ближайшего целого вверх.

Разбор примера: В мешке лежат шарики 4 цветов. Какое наименьшее число шариков нужно вытащить не глядя, чтобы среди них гарантированно нашлось 3 шарика одного цвета?

Здесь логика работает в обратную сторону. Мы ищем . Нам нужно, чтобы в одной «клетке» (цвете) оказалось 3 предмета. «Худший» сценарий — мы вытаскиваем шарики так, чтобы равномерно заполнять цвета, не допуская появления тройки. Мы можем вытащить по 2 шарика каждого из 4 цветов: шариков. Девятый шарик неизбежно упадет в одну из цветовых групп, где уже есть 2 шарика, и образует тройку.

Ответ: .

Применение в геометрии

Принцип Дирихле работает не только с дискретными объектами, но и с площадями.

Задача: В квадрат со стороной 1 метр бросили 5 точек. Докажите, что расстояние между какими-то двумя точками меньше 0,71 метра.

Решение:

Разобьем квадрат на 4 маленьких квадрата со стороной 0,5 м (проведем средние линии).

У нас 5 точек («кролики») и 4 маленьких квадрата («клетки»).

Значит, в один маленький квадрат попадут как минимум 2 точки.

Максимальное расстояние внутри квадрата со стороной — это его диагональ.

Посчитаем диагональ по теореме Пифагора:

Где: * — длина диагонали. * — сторона малого квадрата (0,5).

Так как , утверждение доказано.

!Геометрическая интерпретация принципа Дирихле: разбиение фигуры на части.

Метод крайнего (Принцип крайнего элемента)

Второй мощный инструмент логики — это рассмотрение «крайних» случаев. Когда вы не знаете, с чего начать распутывать задачу, найдите в ней что-то самое большое, самое маленькое, самое левое или самое узкое.

Суть метода: рассмотреть элемент, обладающий экстремальным свойством, и показать, что это приводит к противоречию или решению.

Алгоритм метода крайнего

Выбор: Выберите элемент с экстремальным значением (максимум, минимум, граница).

Анализ: Посмотрите, как этот элемент взаимодействует с соседями или окружающей средой.

Вывод: Докажите, что свойства этого элемента распространяются на всё множество или ведут к противоречию.

Классический пример: Шахматная доска

Задача: В каждой клетке шахматной доски написано число. Известно, что каждое число равно среднему арифметическому своих соседей (по вертикали и горизонтали). Докажите, что все числа на доске равны.

Решение методом крайнего:

Возьмем самое большое число на доске. Пусть это число .

Рассмотрим его соседей. Пусть у него 4 соседа: .

По условию:

Где — максимальное число, — значения в соседних клетках.

Так как — самое большое число на доске, то ни один из соседей не может быть больше ( и т.д.).

Если хотя бы один сосед строго меньше , то среднее арифметическое будет строго меньше . Но у нас равенство.

Значит, все соседи тоже равны .

Теперь применим ту же логику к соседям соседей. Цепочка пойдет дальше и заполнит всю доску. Все числа равны .

Пример: Точки на плоскости

Задача: На плоскости дано конечное множество точек, не все из которых лежат на одной прямой. Докажите, что существует прямая, проходящая ровно через две точки из этого множества (прямая Сильвестра).

Это сложная теорема, но она доказывается методом крайнего. Мы рассматриваем все возможные пары «прямая — точка» и выбираем ту пару, где расстояние от точки до прямой минимально (но не равно нулю). Анализ этой «крайней» конфигурации позволяет доказать утверждение.

Комбинирование методов

Часто в олимпиадах эти методы идут рука об руку. Принцип Дирихле доказывает существование некоторой конфигурации, а метод крайнего помогает упорядочить элементы для поиска решения.

Совет профессора: * Видите фразу «Докажите, что найдется...» или «Существует ли...»? Сразу проверяйте Принцип Дирихле. * Видите задачу про набор чисел, расстановку по кругу или на доске, где есть усреднение или неравенства? Ищите Крайний элемент.

В следующей статье мы перейдем к теме «Инварианты и полуинварианты», где научимся решать задачи про процессы и изменения состояний. А пока — закрепите материал на задачах ниже!

Формула включений-исключений и рекуррентные соотношения

Приветствую вас на третьей лекции курса «Олимпиадная комбинаторика». Мы уже научились считать простые комбинации и доказывать существование объектов с помощью принципа Дирихле. Но что делать, если условия задачи переплетаются, создавая сложные пересечения множеств? Или если решение для объектов зависит от решения для ?

Сегодня мы вооружимся двумя инструментами «тяжелой артиллерии» комбинаторики: Формулой включений-исключений для работы с пересекающимися множествами и Рекуррентными соотношениями для сведения больших задач к малым.

Часть 1. Формула включений-исключений

В первой лекции мы обсуждали правило суммы: если мы выбираем «ИЛИ то, ИЛИ это», варианты складываются. Но это правило работает идеально только тогда, когда варианты не пересекаются. А что, если пересекаются?

Проблема двойного подсчета

Представьте, что в классе 30 учеников. 20 из них изучают английский язык, а 15 — французский. Сколько учеников изучают хотя бы один язык, если известно, что 10 человек учат оба языка сразу?

Если мы просто сложим , то получим 35, что даже больше количества учеников в классе. Ошибка возникла потому, что тех 10 полиглотов, которые знают оба языка, мы посчитали дважды: один раз как «англичан» и второй раз как «французов».

Чтобы получить верный ответ, нужно вычесть лишнее:

Где: * — количество элементов, принадлежащих хотя бы одному из множеств (объединение). * — количество элементов в первом множестве (английский). * — количество элементов во втором множестве (французский). * — количество элементов, принадлежащих обоим множествам одновременно (пересечение).

Подставим числа: . Значит, 25 человек учат языки, а 5 человек не учат ни одного.

!Визуализация пересечения множеств: область пересечения учитывается дважды при простом сложении.

Формула для трех и более множеств

Что если добавить третий язык — немецкий? Логика усложняется. Сначала мы складываем всех учеников по отдельности. Затем вычитаем всех, кто попал в пересечения пар (чтобы убрать двойной подсчет). Но при этом мы случайно вычли тех, кто учит все три языка, слишком много раз! Их нужно вернуть обратно.

Формула для трех множеств:

Где: * — размеры отдельных множеств. * и другие парные пересечения — количество элементов, общих для двух множеств. * — количество элементов, общих для всех трех множеств.

Общий принцип:

Включить (сложить) размеры всех одиночных множеств.

Исключить (вычесть) размеры всех парных пересечений.

Включить (прибавить) размеры всех тройных пересечений.

Исключить (вычесть) размеры всех четверных пересечений.

И так далее, чередуя знаки плюс и минус до самого конца.

!Три множества образуют сложную структуру пересечений: центральная часть принадлежит всем трем кругам.

Классическая задача: Беспорядок (Субфакториал)

Задача: Секретарь написал 5 писем и подписал 5 конвертов. Сколькими способами он может разложить письма по конвертам так, чтобы ни одно письмо не попало в свой конверт?

Такие перестановки без неподвижных точек называются деранжиментами (или беспорядками). Обозначаются (субфакториал) или .

Решение через формулу включений-исключений: Всего перестановок . Вычтем те, где хотя бы одно письмо на месте, добавим те, где хотя бы два на месте, и так далее.

Где: * — число беспорядков для элементов. * — факториал числа (общее число перестановок). * Слагаемые в скобках — знакочередующийся ряд обратных факториалов.

Для :

Где — это , а дроби соответствуют членам ряда.

Часть 2. Рекуррентные соотношения

Иногда посчитать количество вариантов «в лоб» невозможно, но легко выразить ответ для через ответы для предыдущих чисел (). Это и есть рекуррентный метод.

Пример с кузнечиком

Задача: Кузнечик прыгает по числовой прямой. Он начинает в точке 0 и хочет попасть в точку . За один прыжок он может переместиться на 1 или на 2 единицы вправо. Сколькими способами он может добраться до точки ?

Обозначим количество способов попасть в точку как .

Рассмотрим последний прыжок кузнечика. Он мог попасть в точку только двумя способами:

Прыжком длины 1 из точки .

Прыжком длины 2 из точки .

Значит, количество способов попасть в равно сумме способов попасть в и в .

Где: * — искомое количество способов для точки . * — количество способов добраться до предыдущей точки. * — количество способов добраться до пред-предыдущей точки.

Это знаменитые числа Фибоначчи. Нам осталось только найти базу (начальные значения): * В точку 1 можно попасть 1 способом (прыжок 1). . * В точку 2 можно попасть 2 способами (1+1 или сразу 2). .

Дальше просто считаем: , , и так далее.

Линейные однородные рекуррентные соотношения

В олимпиадах часто встречаются последовательности, заданные уравнением вида:

Где и — постоянные коэффициенты.

Как найти формулу -го члена, не считая все предыдущие? Существует мощный алгебраический метод — характеристическое уравнение.

Алгоритм решения:

Заменяем на , на , а на (свободный член). Получаем квадратное уравнение:

Где — неизвестная переменная, корни которой мы ищем.

Находим корни уравнения и .

Если корни разные (), то общая формула имеет вид:

Где и — константы, которые нужно найти.

Если корень один (), формула меняется:

Где множитель добавляется ко второму слагаемому.

Пример: Дана последовательность: , и . Найти .

Характеристическое уравнение: .

Корни (по теореме Виета): .

Общий вид: .

Подставим и для поиска констант:

* *

Решая эту систему уравнений, находим . Итоговая формула:

Где — значение -го члена последовательности.

Задача о Ханойской башне

Классический пример рекурсии. Есть 3 стержня и дисков разного размера. Нужно перенести пирамиду с первого стержня на третий, перекладывая по одному диску и не кладя больший диск на меньший.

Пусть — минимальное число ходов. Чтобы перенести самый большой нижний диск, нужно сначала убрать все верхних дисков на вспомогательный стержень ( ходов). Затем переложить большой диск (1 ход). Затем вернуть дисков на него ( ходов).

Где — число ходов для дисков.

Это соотношение легко разворачивается в формулу:

Стратегия применения

Когда вы видите задачу на олимпиаде:

Есть ли пересечения? Если объекты могут обладать несколькими свойствами одновременно (быть и четными, и делиться на 3), используйте Формулу включений-исключений.

Можно ли свести к меньшему? Если задача для объектов выглядит пугающе, попробуйте выразить её через . Если получится — перед вами Рекуррентное соотношение.

В следующей лекции мы погрузимся в мир Графов, где научимся визуализировать связи между объектами и решать задачи о маршрутах и знакомствах. А пока — закрепите материал на задачах ниже!

Идеи инварианта, полуинварианта и раскрасок на клетчатой доске

Добро пожаловать на четвёртую лекцию курса «Олимпиадная комбинаторика». В предыдущих статьях мы учились считать количество вариантов и доказывать существование объектов. Мы рассматривали ситуации, которые можно назвать «статичными»: сколько способов расставить книги, как выбрать группу людей, как разложить шары по ящикам.

Сегодня мы переходим к «динамике». В олимпиадной математике огромный пласт задач посвящен процессам, изменениям и играм. Что будет, если хамелеоны начнут менять цвет? Можно ли замостить доску доминошками? Остановится ли робот, выполняющий странную программу?

Чтобы решать такие задачи, нам понадобятся три мощных идеи: инвариант (то, что не меняется), полуинвариант (то, что меняется только в одну сторону) и раскраски (скрытые свойства геометрических фигур).

Инвариант: Неизменная суть в хаосе перемен

Представьте, что вы наблюдаете за сложным процессом. Всё меняется, перемешивается, исчезает. Но если вы найдете характеристику, которая остается постоянной на каждом шаге, вы сможете предсказать результат, даже не прослеживая весь процесс целиком. Эта характеристика и называется инвариантом.

Четность как самый популярный инвариант

Самый простой и часто встречающийся инвариант — это четность.

Задача: На доске написано 10 чисел: 1, 2, 3, ..., 10. За один ход разрешается стереть любые два числа и и написать вместо них их сумму . Какое число останется на доске после 9 ходов?

Если пытаться перебирать варианты, можно запутаться. Но давайте посмотрим на сумму всех чисел на доске.

Пусть — сумма чисел на доске. Когда мы стираем и и пишем , общая сумма не меняется.

Где: * — сумма чисел после хода. * — сумма чисел до хода. * — стертые числа.

Значит, сумма всех чисел — это инвариант. Она не меняется. Исходная сумма:

Где — сумма арифметической прогрессии от 1 до 10.

Так как сумма не меняется, последнее оставшееся число тоже будет равно 55. Здесь инвариантом была сама сумма. Но часто инвариантом является лишь четность суммы.

Пример с хамелеонами: На острове живут 13 серых, 15 бурых и 17 малиновых хамелеонов. Когда встречаются два хамелеона разного цвета, они оба меняют свой цвет на третий (например, серый и бурый становятся малиновыми). Могут ли в какой-то момент все хамелеоны стать одного цвета?

Обозначим количество хамелеонов как . При встрече (например, 1-го и 2-го типа) происходит следующее: * уменьшается на 1. * уменьшается на 1. * увеличивается на 2.

Посмотрим на остатки от деления на 3. и .

Это значит, что остатки от деления количества хамелеонов каждого цвета на 3 меняются одинаково (ко всем прибавляется 2, что равносильно вычитанию 1 по модулю 3).

Однако более простой инвариант здесь — разность количеств. Рассмотрим разность . После встречи (уменьшение обоих на 1) она станет:

Разность количеств любых двух цветов при их встрече не меняется! А если встречаются, например, 1-й и 3-й типы, то уменьшается на 1, а увеличивается на 2. Изменение разности:

Где — изменение разности количеств хамелеонов.

Это значит, что разность не меняется по модулю 3. Исходные разности:

Если бы все хамелеоны стали одного цвета (например, 45 серых, 0 бурых, 0 малиновых), то разности были бы равны (делится на 3) или . То есть разность должна делиться на 3. Но у нас исходные разности на 3 не делятся. Значит, такое состояние недостижимо.

!Иллюстрация процесса смены цвета хамелеонов, показывающая изменение их количества.

Раскраски: Геометрический инвариант

Когда задача касается клетчатой доски, фигур, замощений или разрезаний, самым мощным методом является раскраска. Мы искусственно раскрашиваем клетки в разные цвета, чтобы выявить скрытые закономерности.

Шахматная раскраска

Классическая задача, которую должен знать каждый олимпиадник:

Задача: Из шахматной доски вырезали две противоположные угловые клетки (например, a1 и h8). Можно ли замостить оставшуюся фигуру костяшками домино ?

Решение: Каждая костяшка домино всегда покрывает ровно одну черную и ровно одну белую клетку. Значит, если фигуру можно замостить, то в ней должно быть поровну черных и белых клеток.

На обычной доске 32 белых и 32 черных клетки. Угловые клетки a1 и h8 — одного цвета (на стандартной доске они обе черные, если a1 черная). Если мы вырезали две черные клетки, осталось: * 32 белых * 30 черных

, поэтому замостить доску невозможно.

!Визуализация задачи о вырезанных углах: видно нарушение баланса цветов.

Раскраска в полоску и 4 цвета

Иногда шахматной раскраски (в 2 цвета) недостаточно.

Задача: Можно ли замостить доску плитками размером ?

Всего клеток 100, плитка занимает 4 клетки. делится на , так что по площади противоречий нет. Применим раскраску.

Раскрасим доску в 4 цвета диагональными полосами или просто линейно: 1 2 3 4 1 2 3 4 ... 1 2 3 4 1 2 3 4 ...

Любая плитка , положенная горизонтально, закроет по одной клетке каждого цвета (1, 2, 3, 4). Плитка, положенная вертикально, закроет 4 клетки одного цвета (так как в столбце цвет повторяется).

Это не дает противоречия сразу. Попробуем другую раскраску — в 2 цвета полосками. Чередуем вертикальные столбцы: Черный, Белый, Черный, Белый... Любая горизонтальная плитка накроет 2 черные и 2 белые клетки. Любая вертикальная плитка накроет 4 клетки одного цвета (либо 4 черные, либо 4 белые).

Пусть плиток лежат вертикально на черных полосах, а плиток — вертикально на белых. Общее количество черных клеток на доске при вертикальной полосатой раскраске — 50. Белых тоже 50.

Уравнение для черных клеток:

Где: * — количество горизонтальных плиток. * — количество вертикальных плиток на черных полосах. * — всего черных клеток.

Делим на 2:

Отсюда следует, что (количество горизонтальных плиток) должно быть нечетным.

Теперь повернем раскраску на 90 градусов (горизонтальные полосы). Аналогично получим, что количество вертикальных плиток должно быть нечетным.

Всего плиток .

Сумма двух нечетных чисел должна быть четной. Но 25 — нечетное число. Противоречие. Замощение невозможно.

Полуинвариант: Доказательство остановки

Инвариант — это величина, которая не меняется. Полуинвариант — это величина, которая меняется монотонно (всегда возрастает или всегда убывает).

Этот метод идеально подходит для задач, где нужно доказать, что процесс конечен (то есть когда-нибудь остановится) или зациклится.

Принцип работы

Придумываем числовую характеристику системы .

Показываем, что на каждом шаге процесса строго уменьшается (или увеличивается).

Показываем, что не может уменьшаться бесконечно (например, она не может быть меньше нуля или принимает только целые значения).

Вывод: Процесс обязан остановиться.

Задача о парламенте

Задача: В парламенте у каждого депутата не более 3 врагов. Докажите, что парламент можно разбить на две палаты так, чтобы у каждого депутата в его палате было не более одного врага.

Решение: Давайте разобьем депутатов на две палаты случайным образом. Возможно, условие не выполнено: у кого-то в его палате 2 или 3 врага.

Запустим процесс: если у депутата в его текущей палате врагов, переведем его в другую палату.

Почему ему там станет лучше? Всего у него врагов. Если в своей палате у него врага, то в чужой — не более врага. Условие для него выполнится.

Но переходя, он может испортить жизнь другим! Вдруг процесс пересаживания будет идти вечно?

Введем полуинвариант — общее количество пар врагов, сидящих в одной палате.

Когда депутат переходит из палаты №1 в палату №2:

Исчезают пары врагов, которые были у него в палате №1 (их было ).

Появляются новые пары врагов в палате №2 (их станет ).

Изменение полуинварианта:

Где: * — изменение числа «враждебных пар» внутри палат. * — число пар после перехода. * — число пар до перехода.

На каждом шаге общее число пар врагов внутри палат уменьшается как минимум на 1. Так как число пар врагов конечно и не может быть отрицательным, процесс пересаживания гарантированно остановится. В конечный момент ни один депутат не захочет пересаживаться, а значит, у каждого будет не более 1 врага в своей палате.

Стратегия выбора метода

Как понять, что использовать на олимпиаде?

| Признак задачи | Рекомендуемый метод | | :--- | :--- | | Есть процесс, шаги, операции. Спрашивают «Какое состояние будет в конце?» или «Возможно ли такое состояние?» | Инвариант (четность, остаток от деления, сумма) | | Спрашивают «Остановится ли процесс?» или «Существует ли стабильное состояние?» | Полуинвариант (ищите то, что уменьшается) | | Задача про доску, фигурки, замощение, разрезание. | Раскраска (шахматная, полосатая, в 4 цвета) |

В следующей статье мы перейдем к одной из самых обширных и красивых тем комбинаторики — Графам. Мы узнаем, как рисовать связи между объектами и решать задачи о мостах, дорогах и рукопожатиях, используя язык вершин и ребер. А пока — проверьте свое понимание инвариантов на задачах ниже!

Элементы теории графов и их применение в комбинаторике

Приветствую вас на пятой лекции курса «Олимпиадная комбинаторика». Мы уже прошли путь от простых подсчетов до сложных логических конструкций с инвариантами и раскрасками. Сегодня мы познакомимся с языком, на котором говорит современная дискретная математика — с теорией графов.

Многие олимпиадные задачи, которые на первый взгляд кажутся запутанными историями о городах и дорогах, знакомствах на вечеринке или рукопожатиях, на самом деле решаются в одну строчку, если перевести их на язык графов. Граф — это не график функции, как в алгебре. Это структура, показывающая связи между объектами.

Что такое граф?

В комбинаторике граф — это набор точек, некоторые из которых соединены линиями.

* Точки называются вершинами (vertices). * Линии называются ребрами (edges).

Формально граф задается парой множеств:

Где: * — сам граф. * — множество вершин (объектов). * — множество ребер (связей между парами вершин).

Пример из жизни: Представьте карту авиаперелетов. Города — это вершины, а рейсы между ними — это ребра. Или социальную сеть: люди — это вершины, а факт дружбы — ребро.

!Схематичное изображение графа с обозначением основных элементов.

Лемма о рукопожатиях

Самое первое и важное понятие в теории графов — это степень вершины. Степенью вершины называют количество ребер, выходящих из неё (или количество «соседей» у этой вершины).

Обозначается как или .

Существует фундаментальная теорема, которую часто называют «Леммой о рукопожатиях»:

Теорема: Сумма степеней всех вершин графа равна удвоенному количеству ребер.

Где: * — знак суммирования по всем вершинам из множества . * — степень конкретной вершины . * — общее количество ребер в графе.

Доказательство: Каждое ребро соединяет две вершины. Когда мы считаем степени вершин, мы учитываем каждое ребро дважды: один раз для одного конца, второй раз — для другого. Поэтому сумма степеней ровно в два раза больше числа ребер.

Важное следствие: В любом графе количество вершин с нечетной степенью всегда четно.

Это следствие — мощнейший инструмент для доказательства невозможности. Если в задаче получается, что нечетное число людей сделали нечетное число рукопожатий — такая ситуация невозможна.

Задача: Может ли в государстве быть 15 городов, каждый из которых соединен дорогами ровно с 3 другими?

Решение: Предположим, что такой граф существует. Посчитаем сумму степеней:

Где — сумма степеней всех вершин.

Но по лемме о рукопожатиях сумма степеней должна быть четным числом (так как она равна ). Число 45 — нечетное. Противоречие. Значит, такой системы дорог не существует.

Связность и деревья

Граф называется связным, если из любой вершины можно добраться до любой другой, двигаясь по ребрам.

Цикл — это замкнутый путь, который начинается и заканчивается в одной и той же вершине и не проходит через другие вершины дважды.

Особый вид графа, который обожают составители олимпиад — это дерево. Дерево — это связный граф, в котором нет циклов.

У деревьев есть удивительное свойство, связывающее число вершин и ребер:

Где: * — количество ребер в дереве. * — количество вершин в дереве.

Если у вас есть городов, и вы хотите соединить их минимальным количеством дорог так, чтобы все были связаны, вам понадобится ровно дорога. Любая лишняя дорога создаст цикл. Удаление любой дороги разрушит связность.

!Визуальное сравнение дерева и графа с циклом.

Двудольные графы

Вспомните нашу прошлую лекцию о раскрасках. Графы дают этому методу строгое обоснование.

Граф называется двудольным, если его вершины можно разбить на два множества (доли) так, что все ребра соединяют только вершины из разных долей. Внутри одной доли ребер нет.

Это эквивалентно тому, что вершины графа можно раскрасить в два цвета (например, черный и белый) так, что любое ребро соединяет разноцветные вершины.

Критерий двудольности: Граф является двудольным тогда и только тогда, когда в нем нет циклов нечетной длины.

Пример: Рассмотрим шахматную доску как граф. Клетки — это вершины. Если у клеток есть общая сторона, они соединены ребром. Поскольку шахматная доска раскрашена в черный и белый цвета, и соседние клетки всегда разного цвета, этот граф — двудольный. Именно поэтому путь коня, который всегда прыгает с черного на белое и наоборот, так удобно анализировать через двудольность.

Теорема Рамсея: Порядок в хаосе

Одна из самых красивых тем, связывающая принцип Дирихле и графы — это теория Рамсея. Она утверждает, что в любой достаточно большой структуре обязательно найдется упорядоченная подструктура.

Классическая задача («Проблема вечеринки»): Докажите, что среди любых 6 человек найдутся либо трое, которые все знают друг друга, либо трое, которые все не знают друг друга.

Перевод на язык графов: Возьмем 6 вершин (люди). Если люди знакомы, соединим их красным ребром. Если не знакомы — синим. Нам нужно доказать, что в этом графе обязательно найдется либо красный треугольник (3 знакомых), либо синий треугольник (3 незнакомых).

Доказательство:

Возьмем любую вершину . Из неё выходит 5 ребер к другим людям.

По принципу Дирихле, среди 5 ребер найдутся как минимум 3 ребра одного цвета. Пусть для определенности это 3 красных ребра, идущих к вершинам .

Теперь посмотрим на отношения между и .

* Если хотя бы одно ребро между ними (например, ) красное, то мы получаем красный треугольник (так как и уже красные). * Если же все ребра между и синие, то мы нашли синий треугольник .

В обоих случаях утверждение доказано. Это частный случай теоремы Рамсея для .

Эйлеровы графы и мосты Кёнигсберга

История теории графов началась в 1736 году, когда Леонард Эйлер решил задачу о семи мостах Кёнигсберга. Жители города спрашивали: можно ли пройти по всем мостам ровно по одному разу и вернуться в начало?

Эйлер заменил части суши вершинами, а мосты — ребрами. Получился мультиграф (граф, где между вершинами может быть несколько ребер).

Эйлеров цикл — это маршрут, который проходит по каждому ребру графа ровно один раз и возвращается в исходную точку.

Теорема Эйлера: Связный граф содержит эйлеров цикл тогда и только тогда, когда степени всех его вершин четны.

Если же в графе есть ровно две вершины нечетной степени, то существует эйлеров путь (можно пройти все ребра, но начало и конец будут в разных точках).

В задаче о мостах Кёнигсберга все 4 вершины имели нечетную степень. Поэтому пройти по мостам было невозможно.

Планарные графы и формула Эйлера

Граф называется планарным, если его можно нарисовать на плоскости так, чтобы ребра не пересекались (кроме как в вершинах).

Для любого связного планарного графа справедлива знаменитая формула Эйлера:

Где: * — количество вершин. * — количество ребер. * — количество граней (областей, на которые граф делит плоскость, включая внешнюю бесконечную область).

Пример: Нарисуем квадрат с диагональю (без пересечения ребер). * Вершины . * Ребра (4 стороны + 1 диагональ). * Грани (два треугольника внутри и одна внешняя область).

Проверка: . Формула работает.

Эта формула помогает решать задачи о разрезании плоскости и построении коммуникаций. Например, с её помощью доказывается, что невозможно соединить 3 дома с 3 колодцами так, чтобы трубы не пересекались (граф не планарный).

Заключение

Теория графов — это универсальный язык комбинаторики. Когда вы встречаете задачу на олимпиаде:

Попробуйте обозначить объекты точками, а связи — линиями.

Посчитайте степени вершин (помните про четность!).

Если есть два типа объектов или состояний — ищите двудольность.

Если нужно гарантировать наличие группы — вспоминайте Рамсея.

В следующей, заключительной статье нашего вводного курса, мы разберем «Методы решения нестандартных олимпиадных задач», где объединим все изученные подходы в единую стратегию победы. А пока — закрепите материал на задачах ниже!