Разбор экзаменационных задач

Подробные решения с теоретическими основами

🏠 Главная 🧠 Логика 🔢 Комбинаторика 🕸️ Графы 📊 Информация
Задача #1 0.5 балла
Верен ли следующий логический закон? $\exists x \forall y P(x,y) \to \forall y \exists x P(x,y)$

💡 Решение

📚 Теория: Кванторы в логике предикатов

Квантор существования $\exists x$ означает "существует такой x"

Квантор всеобщности $\forall y$ означает "для всех y"

Порядок кванторов имеет критическое значение!

Анализ утверждения:

Левая часть: $\exists x \forall y P(x,y)$ - "существует такой x, что для всех y выполняется P(x,y)"

Правая часть: $\forall y \exists x P(x,y)$ - "для каждого y существует такой x, что выполняется P(x,y)"

Ответ: ДА, логический закон верен

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

Пусть левая часть истинна. Тогда существует элемент $a$ такой, что $P(a,y)$ истинно для всех $y$.

Рассмотрим произвольное $y_0$. Поскольку $P(a,y_0)$ истинно, то существует $x = a$ такой, что $P(x,y_0)$ истинно.

Значит, $\forall y \exists x P(x,y)$ истинно.

Пример: Пусть P(x,y) означает "x больше y". Если существует число, большее всех остальных, то для каждого числа найдется число, большее его.
Задача #2 0.5 балла
Перечисли все сочетания без повторений из 5 элементов по 3.

💡 Решение

📚 Теория: Сочетания без повторений

Сочетания из n элементов по k: $C_n^k = \binom{n}{k} = \frac{n!}{k!(n-k)!}$

Порядок элементов в сочетании не важен

Пусть множество элементов: {1, 2, 3, 4, 5}

$C_5^3 = \frac{5!}{3!(5-3)!} = \frac{5!}{3! \cdot 2!} = \frac{120}{6 \cdot 2} = 10$

Все сочетания:

  1. {1, 2, 3}
  2. {1, 2, 4}
  3. {1, 2, 5}
  4. {1, 3, 4}
  5. {1, 3, 5}
  6. {1, 4, 5}
  7. {2, 3, 4}
  8. {2, 3, 5}
  9. {2, 4, 5}
  10. {3, 4, 5}

Итого: 10 сочетаний

Задача #3 0.5 балла
Даны множества V = {1,2,3,4,5,6}; E = {{1,2},{1,3},{2,4},{3,4},{3,5},{4,6},{5,6}}. Является ли двудольным граф G = (V,E)?

💡 Решение

📚 Теория: Двудольные графы

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

Эквивалентно: граф двудолен ⟺ он не содержит циклов нечётной длины

Метод решения: Попробуем раскрасить граф в два цвета

Строим граф:

Рёбра: (1,2), (1,3), (2,4), (3,4), (3,5), (4,6), (5,6)

Степени вершин: deg(1)=2, deg(2)=2, deg(3)=3, deg(4)=3, deg(5)=2, deg(6)=2

Раскраска:

Начинаем с вершины 1 (цвет A):

  • 1 → A (красный)
  • 2, 3 → B (синий) - соседи вершины 1
  • 4 → A (красный) - сосед вершин 2 и 3
  • 5 → A (красный) - сосед вершины 3
  • 6 → B (синий) - сосед вершин 4 и 5
Множества:
A = {1, 4, 5}
B = {2, 3, 6}

Проверяем: все рёбра действительно соединяют вершины из разных множеств.

Ответ: ДА, граф является двудольным
Задача #4 0.5 балла
Даны множества A = {1,2,3,4}, B = {2,3,4,5}. Является ли функцией из A в B множество C = {{1,2},{3,4},{2,3},{4,5}}?

💡 Решение

📚 Теория: Функции

Функция f: A → B - это соответствие, при котором каждому элементу из A сопоставляется ровно один элемент из B

Условия: 1) Каждый элемент A имеет образ в B; 2) У каждого элемента A единственный образ

Анализ множества C:

C = {(1,2), (3,4), (2,3), (4,5)}

Проверяем условия функции:

  • Элемент 1 ∈ A: образ 2 ∈ B ✓
  • Элемент 2 ∈ A: образ 3 ∈ B ✓
  • Элемент 3 ∈ A: образ 4 ∈ B ✓
  • Элемент 4 ∈ A: образ 5 ∈ B ✓

Проверяем единственность образов:

Каждый элемент из A встречается в качестве первой компоненты ровно один раз.

Ответ: ДА, C является функцией из A в B

Функция f: A → B определена как:

f(1) = 2, f(2) = 3, f(3) = 4, f(4) = 5

Это биективная функция (взаимно-однозначное соответствие)

Задача #5 1.5 балла
Докажи, что если на плоскости проведено несколько прямых, то можно раскрасить получившиеся области в два цвета так, что любые две соседние области будут покрашены в разные цвета.

💡 Решение

📚 Теория: Раскраска плоскости и двудольность

Это классическая задача о 2-раскраске дуального графа

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

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

База: При n = 1 прямая делит плоскость на 2 области. Раскрасим их в разные цвета.

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

Алгоритм:

  1. По предположению индукции, n прямых создают правильно раскрашенные области
  2. Новая прямая пересекает плоскость, разделяя некоторые области пополам
  3. В каждой области, которую пересекает новая прямая, меняем цвет одной из половин
  4. Поскольку прямая разделяет каждую область на две части, соседние области по-прежнему имеют разные цвета

Геометрическое объяснение:

Каждая прямая создаёт "переключатель" цветов. Области по разные стороны от прямой должны иметь разные цвета.

Важно: Это работает только для прямых (не для окружностей или других кривых), так как прямые не создают циклов нечётной длины в дуальном графе.
Вывод: Двухцветная раскраска всегда возможна
Задача #6 1.0 балл
Сколько различных натуральных делителей имеет число 10!?

💡 Решение

📚 Теория: Количество делителей числа

Если $n = p_1^{a_1} \cdot p_2^{a_2} \cdot ... \cdot p_k^{a_k}$, то количество делителей:

$\tau(n) = (a_1 + 1)(a_2 + 1)...(a_k + 1)$

Шаг 1: Найдем разложение 10! на простые множители

$10! = 1 \cdot 2 \cdot 3 \cdot 4 \cdot 5 \cdot 6 \cdot 7 \cdot 8 \cdot 9 \cdot 10$

Шаг 2: Подсчитаем степени простых чисел

Степень простого p в n!: $\sum_{i=1}^{\infty} \lfloor \frac{n}{p^i} \rfloor$

Степень 2: $\lfloor \frac{10}{2} \rfloor + \lfloor \frac{10}{4} \rfloor + \lfloor \frac{10}{8} \rfloor = 5 + 2 + 1 = 8$

Степень 3: $\lfloor \frac{10}{3} \rfloor + \lfloor \frac{10}{9} \rfloor = 3 + 1 = 4$

Степень 5: $\lfloor \frac{10}{5} \rfloor = 2$

Степень 7: $\lfloor \frac{10}{7} \rfloor = 1$

Шаг 3: Получаем разложение

$10! = 2^8 \cdot 3^4 \cdot 5^2 \cdot 7^1$

Шаг 4: Применяем формулу для количества делителей

$\tau(10!) = (8+1)(4+1)(2+1)(1+1) = 9 \cdot 5 \cdot 3 \cdot 2 = 270$
Ответ: 270 различных натуральных делителей
Задача #7 1.5 балла
Докажи, что в любом связном графе можно выделить остовное дерево.

💡 Решение

📚 Теория: Остовные деревья

Остовное дерево - подграф, который является деревом и включает все вершины исходного графа

Дерево - связный граф без циклов

В дереве с n вершинами ровно n-1 рёбер

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

Алгоритм построения остовного дерева:

  1. Начальный шаг: Берём исходный связный граф G = (V, E)
  2. Пока граф содержит циклы:
    • Найдём любой цикл в графе
    • Удалим одно ребро из этого цикла
    • Граф остаётся связным (так как были альтернативные пути)
  3. Завершение: Когда циклов не остаётся, получаем дерево

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

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

Альтернативные алгоритмы:

Алгоритм Краскала: Добавляем рёбра в порядке возрастания весов, избегая циклов

Алгоритм Прима: Растём дерево от выбранной вершины, добавляя минимальные рёбра

Поиск в глубину (DFS): Строим дерево поиска

Доказательство существования (от противного):

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

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

Вывод: В любом связном графе существует остовное дерево
Задача #8 1.5 балла
Докажи, что для любого n найдется число из одних единиц и нулей, которое делится на n.

💡 Решение

📚 Теория: Принцип Дирихле и остатки

Принцип Дирихле: Если n+1 объект помещены в n ящиков, то в одном ящике окажется больше одного объекта

Остатки при делении на n: {0, 1, 2, ..., n-1}

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

Случай 1: Если НОД(n, 10) = 1

Рассмотрим последовательность чисел:

$a_1 = 1$

$a_2 = 11$

$a_3 = 111$

$a_k = \underbrace{111...1}_{k \text{ единиц}}$

Рассмотрим остатки $r_k = a_k \bmod n$ для $k = 1, 2, ..., n$

У нас есть n чисел $r_1, r_2, ..., r_n$, каждое из которых может принимать значения от 0 до n-1.

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

Если все остатки различны, то один из них равен 0, и мы нашли нужное число.

Если есть одинаковые остатки $r_i = r_j$ при $i < j$, то $a_j - a_i$ делится на n.

Ключевое наблюдение:

$a_j - a_i = \underbrace{111...1}_{j} - \underbrace{111...1}_{i} = \underbrace{111...1}_{j-i} \cdot 10^i$

Если НОД(n, 10) = 1, то $10^i$ взаимно прост с n, значит $\underbrace{111...1}_{j-i}$ делится на n.

Случай 2: Если НОД(n, 10) ≠ 1

Пусть n = $2^a \cdot 5^b \cdot m$, где НОД(m, 10) = 1

По первому случаю, существует число $k$ из единиц, делящееся на m.

Тогда число $k \cdot 10^{\max(a,b)}$ из единиц и нулей делится на n.

Пример: Для n = 6:

1 ≡ 1 (mod 6)

11 ≡ 5 (mod 6)

111 ≡ 3 (mod 6)

1111 ≡ 1 (mod 6)

Остатки повторились: 1111 - 1 = 1110 делится на 6

Вывод: Для любого n существует число из 0 и 1, делящееся на n
Задача #9 1.5 балла
Дана задача: «сколькими способами можно выложить 10 одинаковых синих и 5 одинаковых красных шаров в ряд так, чтобы никакие два красных шара не оказались рядом?» Рассмотрим следующее решение этой задачи. Расставим сначала красные шары, и между каждыми двумя красными шарами поставим по одному синему, чтобы никакие два красных не стояли рядом. Тогда у нас останется еще 6 синих шаров, для которых мы не выбрали место. Каждый из них мы можем поставить либо слева от всех шаров, либо справа от всех шаров, либо в любой из 4 промежутков между красными шарами. Поскольку все синие шары одинаковые и важно лишь количество синих шаров в каждой из этих позиций, можно считать, что для каждого из оставшихся 6 синих шаров есть ровно 6 возможных позиций. Итого способов их расставить 6⁶. Ответ: 6⁶. Где ошибка в этом рассуждении? Объясни, какой именно логический переход в рассуждении является неверным. Приведи верное рассуждение и верный ответ на задачу.

💡 Решение

📚 Теория: Размещения с ограничениями

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

Ключевая проблема: различие между размещением различимых и неразличимых объектов

Анализ ошибки:

Ошибка в рассуждении: Автор считает, что каждый из 6 оставшихся синих шаров независимо выбирает одну из 6 позиций. Это дало бы $6^6$ способов, если бы шары были различимы.

Проблема: Синие шары одинаковые! Важно только количество шаров в каждой позиции, а не то, какой именно шар куда попал.

Правильное решение:

Шаг 1: Размещаем 5 красных шаров с разделителями

К_С_К_С_К_С_К_С_К (где К - красный, С - синий разделитель)

Использовано: 5 красных + 4 синих = 9 шаров

Осталось: 10 - 4 = 6 синих шаров

Шаг 2: Размещаем 6 оставшихся синих шаров

У нас есть 6 позиций:

  • Слева от первого красного
  • Между 1-м и 2-м красными
  • Между 2-м и 3-м красными
  • Между 3-м и 4-м красными
  • Между 4-м и 5-м красными
  • Справа от последнего красного

📚 Правильный подход: Звёзды и палочки

Нужно распределить 6 одинаковых шаров по 6 различным позициям

Это классическая задача "звёзды и палочки"

Формула: Количество способов разместить n одинаковых объектов в k различных групп:

$\binom{n + k - 1}{k - 1} = \binom{n + k - 1}{n}$

Применение: n = 6 шаров, k = 6 позиций

$\binom{6 + 6 - 1}{6 - 1} = \binom{11}{5} = \frac{11!}{5! \cdot 6!} = \frac{11 \cdot 10 \cdot 9 \cdot 8 \cdot 7}{5 \cdot 4 \cdot 3 \cdot 2 \cdot 1} = 462$
Правильный ответ: 462 способа

Проверка через другой подход:

Можно также решить как размещение 10 синих шаров в 11 промежутков, образованных 5 красными шарами (включая крайние позиции), при условии, что между красными шарами должен быть хотя бы один синий.

Вывод: Ошибка в том, что $6^6$ учитывает порядок размещения различимых объектов, а нам нужно количество способов размещения неразличимых объектов.

Задача #10 1.5 балла
Турниром называется ориентированный граф, в котором для любой пары различных вершин u,v присутствует ровно одно из рёбер (u,v) или (v,u). Докажи, что в любом турнире есть гамильтонов путь.

💡 Решение

📚 Теория: Турниры и гамильтоновы пути

Турнир - полный ориентированный граф (для каждой пары вершин есть ровно одна ориентированная дуга)

Гамильтонов путь - путь, проходящий через каждую вершину ровно один раз

В турнире из n вершин ровно $\binom{n}{2}$ дуг

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

База индукции: n = 1, 2

n = 1: тривиально, путь из одной вершины

n = 2: есть дуга (u,v) или (v,u), получаем путь длины 1

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

Пусть утверждение верно для всех турниров с n-1 вершинами. Рассмотрим турнир T с n вершинами.

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

  1. Выберем произвольную вершину v
  2. Удалим v из турнира, получим турнир T' с n-1 вершинами
  3. По предположению индукции, в T' есть гамильтонов путь P = $v_1 \to v_2 \to ... \to v_{n-1}$
  4. Вставим v в подходящее место в этом пути

Ключевое наблюдение:

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

Лемма о вставке: Если в турнире есть путь $v_1 \to v_2 \to ... \to v_k$, то для любой вершины u существует позиция, куда можно вставить u, сохранив свойство пути.

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

Рассмотрим последовательность дуг от u к вершинам пути:

  • Если $(u, v_1) \in E$, то вставляем u в начало: $u \to v_1 \to ... \to v_k$
  • Если $(v_k, u) \in E$, то вставляем u в конец: $v_1 \to ... \to v_k \to u$
  • Иначе найдём первый индекс i такой, что $(v_i, u) \in E$ и $(u, v_{i+1}) \in E$
  • Вставляем u между $v_i$ и $v_{i+1}$: $v_1 \to ... \to v_i \to u \to v_{i+1} \to ... \to v_k$

Почему такой индекс существует:

Поскольку турнир - полный граф, для каждой пары $(v_i, v_{i+1})$ либо $(u, v_i) \in E$ и $(v_{i+1}, u) \in E$, либо $(v_i, u) \in E$ и $(u, v_{i+1}) \in E$

Альтернативное доказательство (конструктивное):

Алгоритм:

  1. Начинаем с произвольной вершины
  2. Пока не посетили все вершины:
  3. Из текущей вершины идём к любой непосещённой вершине
  4. Если из текущей вершины нет дуг к непосещённым вершинам, то переходим к началу пути и продолжаем оттуда
Вывод: В любом турнире существует гамильтонов путь
Задача #11 1.5 балла
Илья загадал перестановку чисел от 1 до 12. За какое минимальное число бинарных вопросов Алла наверняка сможет ее отгадать?

💡 Решение

📚 Теория: Информационная сложность

Количество информации, необходимое для различения N равновероятных вариантов: $\log_2 N$ бит

Каждый бинарный вопрос дает максимум 1 бит информации

Минимальное число вопросов: $\lceil \log_2 N \rceil$

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

Количество перестановок чисел от 1 до 12:

$N = 12! = 479{,}001{,}600$

Вычисляем логарифм:

$\log_2(12!) = \log_2(1 \cdot 2 \cdot 3 \cdot ... \cdot 12)$

$= \log_2(1) + \log_2(2) + \log_2(3) + ... + \log_2(12)$

$≈ 0 + 1 + 1.58 + 2 + 2.32 + 2.58 + 2.81 + 3 + 3.17 + 3.32 + 3.46 + 3.58$

$≈ 28.82$

Точное вычисление:

$12! = 479{,}001{,}600$

Найдём степени двойки:

$2^{28} = 268{,}435{,}456 < 12!$

$2^{29} = 536{,}870{,}912 > 12!$

Следовательно:

$28 < \log_2(12!) < 29$

Минимальное число вопросов:

$\lceil \log_2(12!) \rceil = 29$

📚 Стратегия оптимального опроса

Оптимальная стратегия: каждый вопрос должен делить множество оставшихся вариантов примерно пополам

Примеры вопросов: "Число на позиции 1 больше 6?", "Число 7 стоит в первой половине?"

Важно: 29 вопросов достаточно для любой стратегии Ильи, но требуется оптимальная стратегия опроса от Аллы

Доказательство достижимости:

Можно построить дерево решений, где каждый лист соответствует одной перестановке, а каждый внутренний узел - бинарному вопросу. Дерево с $12!$ листьями имеет высоту не менее $\lceil \log_2(12!) \rceil = 29$.

Ответ: 29 бинарных вопросов

Практическая реализация:

Можно использовать метод "двоичного поиска по перестановкам" или кодирование каждой перестановки двоичной строкой длины 29.