← Назад к темам

🧠 Логика и основные методы рассуждений

Принципы доказательств, принцип Дирихле, математическая индукция

Теоретические основы

Принцип Дирихле (Pigeonhole Principle)

Если $n+1$ объектов помещаются в $n$ ящиков, то хотя бы в одном ящике окажется более одного объекта.

Обобщённый принцип: Если $kn+1$ объектов помещается в $n$ ящиков, то хотя бы в одном ящике окажется не менее $k+1$ объектов.

Математическая индукция

Схема доказательства:

  1. База индукции: Проверить утверждение для $n = n_0$ (обычно $n_0 = 1$)
  2. Индукционное предположение: Предположить, что утверждение верно для $n = k$
  3. Индукционный переход: Доказать, что из истинности для $n = k$ следует истинность для $n = k+1$
Лемма о рукопожатиях: В любом графе сумма степеней всех вершин равна удвоенному числу рёбер: $\sum_{v} \deg(v) = 2|E|$

📋 Основные определения и логические законы

Логические законы

Закон исключённого третьего: $A \lor \neg A$ (любое утверждение либо истинно, либо ложно)

Закон двойного отрицания: $\neg \neg A \equiv A$

Законы де Моргана:

  • $\neg (A \land B) \equiv \neg A \lor \neg B$
  • $\neg (A \lor B) \equiv \neg A \land \neg B$

Закон непротиворечивости: $\neg (A \land \neg A)$ (утверждение не может быть одновременно истинным и ложным)

Закон контрапозиции: $(A \rightarrow B) \equiv (\neg B \rightarrow \neg A)$

Логические законы для утверждений с кванторами

Законы де Моргана для кванторов:

  • $\neg \forall x P(x) \equiv \exists x \neg P(x)$
  • $\neg \exists x P(x) \equiv \forall x \neg P(x)$

Вынесение кванторов за скобки:

  • $\forall x (P(x) \land Q(x)) \equiv \forall x P(x) \land \forall x Q(x)$
  • $\exists x (P(x) \lor Q(x)) \equiv \exists x P(x) \lor \exists x Q(x)$

Перестановка кванторов:

  • $\forall x \forall y P(x,y) \equiv \forall y \forall x P(x,y)$
  • $\exists x \exists y P(x,y) \equiv \exists y \exists x P(x,y)$
  • $\forall x \exists y P(x,y) \not\equiv \exists y \forall x P(x,y)$ (в общем случае)

Сокращённые записи:

  • $\exists x \in S : A(x)$ означает "существует элемент $x$ из множества $S$ такой, что $A(x)$ истинно"
  • $\forall x \in S : A(x)$ означает "для всех элементов $x$ из множества $S$ утверждение $A(x)$ истинно"
Основные определения

Упорядоченная пара: $(a,b)$ - объект, где важен порядок элементов. $(a,b) = (c,d) \Leftrightarrow a = c \land b = d$

Декартово произведение: $A \times B = \{(a,b) : a \in A, b \in B\}$

Бинарное отношение: $R \subseteq A \times B$ - подмножество декартова произведения

Функция: $f: A \rightarrow B$ - бинарное отношение, где каждому элементу из $A$ соответствует единственный элемент из $B$

Образ множества: $f(X) = \{f(x) : x \in X\}$ для $X \subseteq A$

Прообраз множества: $f^{-1}(Y) = \{x \in A : f(x) \in Y\}$ для $Y \subseteq B$

Композиция функций: $(g \circ f)(x) = g(f(x))$

Биекция: функция, которая является одновременно инъективной (взаимно однозначной) и сюръективной (на все множество)

Принципы математической индукции (формальная запись)

Принцип математической индукции:

Пусть $P(n)$ - утверждение о натуральном числе $n$. Если:

  1. $P(1)$ истинно (база индукции)
  2. $\forall k \in \mathbb{N}: P(k) \rightarrow P(k+1)$ (индукционный переход)

То $\forall n \in \mathbb{N}: P(n)$ истинно.

Принцип полной математической индукции:

Пусть $P(n)$ - утверждение о натуральном числе $n$. Если:

  1. $P(1)$ истинно (база индукции)
  2. $\forall k \in \mathbb{N}: (P(1) \land P(2) \land \ldots \land P(k)) \rightarrow P(k+1)$ (сильный индукционный переход)

То $\forall n \in \mathbb{N}: P(n)$ истинно.

Легкий
В компании из нечетного числа людей не может оказаться так, что каждый пожал руку ровно 3 другим; а вот в компании из четного числа людей это возможно
💡 Решение

Это классическое применение леммы о рукопожатиях.

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

Представим людей как вершины графа, а рукопожатия как рёбра. По лемме о рукопожатиях:

$$\sum_{i=1}^{n} \deg(v_i) = 2|E|$$

Если каждый из $n$ людей пожал руку ровно 3 другим, то сумма степеней равна $3n$.

Поскольку $3n$ должно равняться $2|E|$, то $3n$ должно быть четным.

Но если $n$ нечетно, то $3n$ нечетно, что противоречит условию $3n = 2|E|$.

Пример для четного числа людей:
При $n = 4$ людях каждый может пожать руку 3 другим. Тогда сумма степеней = $4 \times 3 = 12 = 2 \times 6$, что означает 6 рукопожатий.
Легкий
Утверждение о том, что существует сколько угодно подряд идущих составных чисел
💡 Решение

Теорема: Для любого натурального $n$ существует $n$ подряд идущих составных чисел.

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

Рассмотрим числа $(n+1)! + 2, (n+1)! + 3, \ldots, (n+1)! + (n+1)$.

Покажем, что все эти $n$ чисел составные:

  • $(n+1)! + 2$ делится на 2 (так как $(n+1)!$ содержит множитель 2)
  • $(n+1)! + 3$ делится на 3 (так как $(n+1)!$ содержит множитель 3)
  • $\vdots$
  • $(n+1)! + (n+1)$ делится на $(n+1)$
Пример для $n = 3$:
$4! = 24$, рассматриваем числа: $26, 27, 28$
• $26 = 2 \times 13$ (составное)
• $27 = 3^3$ (составное)
• $28 = 4 \times 7$ (составное)
Легкий
Доказательство бесконечности множества простых чисел
💡 Решение (Доказательство Евклида)

Теорема: Множество простых чисел бесконечно.

Доказательство от противного:

Предположим, что существует лишь конечное число простых чисел: $p_1, p_2, \ldots, p_k$.

Рассмотрим число $N = p_1 \cdot p_2 \cdot \ldots \cdot p_k + 1$.

Число $N > 1$, поэтому оно либо простое, либо имеет простой делитель.

Случай 1: Если $N$ простое, то мы нашли простое число, не входящее в наш список.

Случай 2: Если $N$ составное, то у него есть простой делитель $p$. Но $p$ не может быть равен ни одному из $p_1, p_2, \ldots, p_k$, поскольку:

$$N \equiv 1 \pmod{p_i} \text{ для всех } i = 1, 2, \ldots, k$$

Таким образом, $p$ - новое простое число, не входящее в наш список.

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

Легкий
Доказательство иррациональности √2
💡 Решение

Теорема: $\sqrt{2}$ - иррациональное число.

Доказательство от противного:

Предположим, что $\sqrt{2}$ рационально, т.е. $\sqrt{2} = \frac{p}{q}$, где $p, q$ - натуральные числа, $\gcd(p,q) = 1$.

Возведём обе части в квадрат:

$$2 = \frac{p^2}{q^2}$$ $$2q^2 = p^2$$

Из последнего равенства следует, что $p^2$ четно, а значит и $p$ четно.

Пусть $p = 2k$, тогда:

$$2q^2 = (2k)^2 = 4k^2$$ $$q^2 = 2k^2$$

Значит, $q^2$ тоже четно, а следовательно, и $q$ четно.

Но если и $p$, и $q$ четны, то $\gcd(p,q) \geq 2$, что противоречит условию $\gcd(p,q) = 1$.

Вывод: $\sqrt{2}$ не может быть представлено в виде дроби, следовательно, оно иррационально.

Легкий
Доказательство принципа Дирихле в общем виде
💡 Решение
Принцип Дирихле (обобщенная формулировка)

Если $n$ объектов помещаются в $k$ ящиков, то хотя бы в одном ящике окажется не менее $\lceil \frac{n}{k} \rceil$ объектов.

Доказательство от противного:

Предположим, что в каждом ящике находится менее $\lceil \frac{n}{k} \rceil$ объектов.

Тогда в каждом ящике не более $\lceil \frac{n}{k} \rceil - 1$ объектов.

Общее количество объектов не превышает:

$$k \cdot (\lceil \frac{n}{k} \rceil - 1)$$

Поскольку $\lceil \frac{n}{k} \rceil \geq \frac{n}{k}$, то:

$$k \cdot (\lceil \frac{n}{k} \rceil - 1) \geq k \cdot (\frac{n}{k} - 1) = n - k$$

Но поскольку $\lceil \frac{n}{k} \rceil$ - наименьшее целое число $\geq \frac{n}{k}$, имеем $\lceil \frac{n}{k} \rceil - 1 < \frac{n}{k}$, откуда:

$$k \cdot (\lceil \frac{n}{k} \rceil - 1) < k \cdot \frac{n}{k} = n$$

Получаем противоречие: общее количество объектов меньше $n$, хотя по условию их ровно $n$.

Средний
Для любого n найдется число из одних единиц и нулей, которое делится на n
💡 Решение

Теорема: Для любого натурального $n$ существует число, состоящее только из цифр 0 и 1, которое делится на $n$.

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

Рассмотрим числа: $1, 11, 111, 1111, \ldots$

Рассмотрим остатки этих чисел при делении на $n$:

$$r_1 = 1 \bmod n$$ $$r_2 = 11 \bmod n$$ $$r_3 = 111 \bmod n$$ $$\vdots$$ $$r_{n+1} = \underbrace{111\ldots1}_{n+1} \bmod n$$

У нас есть $n+1$ остаток, но возможных значений остатков только $n$ (от 0 до $n-1$).

По принципу Дирихле найдутся два числа с одинаковыми остатками или найдется число с остатком 0.

Если какое-то число дает остаток 0, то оно делится на $n$ - готово!

Иначе найдутся $r_i = r_j$ ($i < j$). Тогда их разность:

$$\underbrace{111\ldots1}_{j} - \underbrace{111\ldots1}_{i} = \underbrace{111\ldots1}_{j-i} \cdot 10^i$$

делится на $n$.

Если $\gcd(10, n) = 1$, то $\underbrace{111\ldots1}_{j-i}$ делится на $n$.

Если $\gcd(10, n) > 1$, рассматриваем более сложную конструкцию с числами вида $10^a \cdot k$ где $k$ состоит из единиц.

Средний
На плоскости провели n прямых так, что любые две проведённые прямые пересекаются, и никакие три прямые не пересекаются в одной точке. На сколько частей прямые поделят плоскость?
💡 Решение

Обозначим через $R(n)$ количество областей, на которые $n$ прямых делят плоскость.

Рекуррентное соотношение:

При добавлении $(n+1)$-й прямой к $n$ уже проведенным прямым:

  • Новая прямая пересекает каждую из $n$ прямых в разных точках
  • Получается $n$ точек пересечения на новой прямой
  • Эти $n$ точек делят новую прямую на $n+1$ отрезок
  • Каждый отрезок проходит через отдельную область
  • Следовательно, количество областей увеличивается на $n+1$

Получаем рекуррентное соотношение:

$$R(n+1) = R(n) + (n+1)$$

с начальным условием $R(0) = 1$ (без прямых плоскость - одна область).

Решение рекуррентности:

$$R(n) = R(0) + \sum_{k=1}^{n} k = 1 + \frac{n(n+1)}{2}$$

Ответ:

$$R(n) = 1 + \frac{n(n+1)}{2} = \frac{2 + n^2 + n}{2} = \frac{n^2 + n + 2}{2}$$
Проверка:
• $n = 0$: $R(0) = 1$ ✓
• $n = 1$: $R(1) = 2$ ✓
• $n = 2$: $R(2) = 4$ ✓
• $n = 3$: $R(3) = 7$ ✓
Средний
Клетки квадратной таблицы 15 × 15 раскрашены в красный, синий и зелёный цвета. Тогда найдутся по крайней мере две строки, в которых клеток хотя бы одного цвета поровну
💡 Решение (Принцип Дирихле)

Анализ задачи:

В каждой строке 15 клеток, раскрашенных в 3 цвета. Пусть в строке $i$ есть $r_i$ красных, $s_i$ синих и $g_i$ зеленых клеток, где $r_i + s_i + g_i = 15$.

Характеристика строки:

Каждую строку можно охарактеризовать тройкой $(r_i, s_i, g_i)$ неотрицательных целых чисел с суммой 15.

Подсчет возможных троек:

Количество способов представить 15 в виде суммы трех неотрицательных слагаемых равно количеству сочетаний с повторениями:

$$\binom{15 + 3 - 1}{3 - 1} = \binom{17}{2} = \frac{17 \cdot 16}{2} = 136$$

Применение принципа Дирихле:

У нас есть 15 строк и 136 возможных характеристик. Поскольку $15 < 136$, принцип Дирихле не применяется напрямую.

Более тонкий анализ:

Рассмотрим не полные характеристики, а только количества клеток каждого цвета по модулю некоторого числа или другие инварианты.

Альтернативное решение:

Рассмотрим векторы $(r_i, s_i, g_i)$ как точки в $\mathbb{Z}^3$. Поскольку строк 15, а различных остатков при делении на 7 для каждой координаты по 7, получаем $7^3 = 343$ возможных классов эквивалентности по модулю 7.

Но более простой подход: рассмотрим только пары значений. Для каждого цвета в строке может быть от 0 до 15 клеток - всего 16 вариантов. Но нас интересуют совпадения.

Ключевая идея: Среди 15 строк найдутся две с одинаковым распределением цветов по принципу Дирихле, если правильно выбрать характеристику.
Легкий
Имеется 100 камней. Известно, что массы всех камней попарно различны. За одно взвешивание можно узнать про любые два камня, какой из них тяжелее. Какое наименьшее число взвешиваний необходимо и достаточно, чтобы найти самый тяжелый камень среди них?
💡 Решение

Задача: Найти максимальный элемент среди 100 различных элементов.

Нижняя оценка:

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

Каждое сравнение может исключить не более одного камня из претендентов на звание самого тяжелого.

Следовательно, нужно не менее $100 - 1 = 99$ сравнений.

Верхняя оценка (алгоритм турнира):

Можно найти максимум за ровно 99 сравнений:

Алгоритм "Турнир на выбывание"
  1. Разбиваем 100 камней на 50 пар
  2. Сравниваем камни в каждой паре (50 сравнений)
  3. Остается 50 "победителей"
  4. Повторяем процесс: 25 пар → 25 сравнений → 25 победителей
  5. Продолжаем до тех пор, пока не останется 1 камень

Подсчет сравнений:

$50 + 25 + 12 + 6 + 3 + 1 + 1 + 1 = 99$ сравнений

Альтернативно: на каждом сравнении исключается ровно один камень, поэтому нужно исключить $100 - 1 = 99$ камней.

Ответ: Необходимо и достаточно ровно 99 взвешиваний.
Легкий
Если на плоскости проведено несколько прямых, то можно раскрасить получившиеся области в два цвета так, что соседние области будут покрашены в разные цвета
💡 Решение

Теорема: Плоскость, разделенная прямыми линиями, можно раскрасить в два цвета так, что любые две соседние области имеют разные цвета.

Доказательство (индукция по количеству прямых):

База индукции: При $n = 0$ прямых вся плоскость - одна область, красим её в любой цвет.

Индукционный переход: Пусть утверждение верно для $n$ прямых. Добавим $(n+1)$-ю прямую.

По предположению индукции, области, образованные первыми $n$ прямыми, уже правильно раскрашены в два цвета
Новая прямая разделяет плоскость на две полуплоскости
В одной полуплоскости оставляем раскраску без изменений
В другой полуплоскости меняем цвет каждой области на противоположный
Области по разные стороны от новой прямой теперь имеют разные цвета
Области, не пересекаемые новой прямой, сохраняют правильную раскраску
Геометрическая интуиция: Каждая прямая "переворачивает" раскраску по одну сторону от себя, обеспечивая правильное чередование цветов.
Связь с теорией графов: Это эквивалентно утверждению, что планарный граф, образованный пересечениями прямых, является двудольным в двойственном смысле.
Легкий
Любой клетчатый квадрат размера 2n × 2n без любой клетки можно разрезать на уголки, состоящие из трёх клеток
💡 Решение

Теорема: Квадрат $2n \times 2n$ с удаленной одной клеткой можно замостить L-тримино (уголками из 3 клеток).

Доказательство (математическая индукция):

База индукции ($n = 1$):

Квадрат $2 \times 2$ без одной клетки представляет собой L-тримино. Утверждение верно.

Индукционный переход:

Пусть утверждение верно для квадрата $2k \times 2k$. Докажем для квадрата $2(k+1) \times 2(k+1)$.

Разделим квадрат $2(k+1) \times 2(k+1)$ на четыре квадрата размера $2k \times 2k$
Удаленная клетка находится в одном из четырех квадратов
В центре большого квадрата поместим один L-тримино так, чтобы он занял по одной клетке в трех квадратах, не содержащих удаленную клетку
Теперь в каждом из четырех квадратов $2k \times 2k$ есть ровно одна "удаленная" клетка
По предположению индукции каждый такой квадрат можно замостить L-тримино
Визуализация для n=2:
Квадрат 4×4 разбивается на четыре квадрата 2×2, в центре ставится L-тримино, затем каждый квадрат 2×2 с "дыркой" заполняется одним L-тримино.
Количественная проверка: В квадрате $2n \times 2n$ всего $4n^2$ клеток. После удаления одной остается $4n^2 - 1$ клеток. Поскольку $4n^2 - 1 = 3 \cdot \frac{4n^2-1}{3}$ и $4n^2 - 1$ всегда делится на 3, замощение возможно.