Список заданий по ДМ 2018 осень

Дискретная математика, 1 семестр

Задания, помеченные 🤔 - задания повышенной сложности. Задания, помеченные 😱 - задания очень высокой сложности. ✋ помечены задания, где мы передаем привет курсу "Алгоритмы и структуры данных".

1. Пусть $R$ и $S$ - рефлексивные отношения на $A$. Будет ли рефлексивным их а) объединение? б) пересечение? В этом и следующих заданиях, если ответ отрицательный, при демонстрации контрпримера удобно использовать представление отношения в виде ориентированного графа.
2. Пусть $R$ и $S$ - симметричные отношения на $A$. Будет ли симметричным их а) объединение? б) пересечение?
3. Пусть $R$ и $S$ - транзитивные отношения на $A$. Будет ли транзитивным их а) объединение? б) пересечение?
4. Пусть $R$ и $S$ - антисимметричные отношения на $A$. Будет ли антисимметричным их а) объединение? б) пересечение?
5. Определим $R^{-1}$ следующим образом: если $xRy$, то $yR^{-1}x$. Выполнено ли соотношение $RR^{-1} = I$, где $I$ - отношение равенства? Выполнен ли закон сложения степенией $R^iR^j=R^{i+j}$, если $i$ и $j$ разного знака?
6. Пусть $R$ обладает свойством $X$. Будет ли обладать свойством $X$ отношение $R^{-1}$? Следует проанализировать $X$ - рефлексивность, антирефлексивность, симметричность, антисимметричность, транзитивность
7. Пусть $R$ и $S$ - транзитивные отношения на $A$. Будет ли транзитивным их композиция?
8. Пусть $R$ и $S$ - антисимметричные отношения на A. Будет ли антисимметричным их композиция?
9. Постройте пример рефлексивного, симметричного, но не транзитивного отношения
10. Постройте пример рефлексивного, антисимметричного, но не транзитивного отношения
11. Является ли отношение $R$, такое что $(a, b) R (c, d)$, если $ad = bc$ на ${\mathbb Z}^+ \times {\mathbb N}$ отношением эквивалентности?
12. Может ли отношение частичного порядка быть отношением эквивалентности? Если да, то в каких случаях?
13. Можно ли в определении отношения эквивалентности убрать требование рефлексивности отношения, потому что оно следует из симметричности и транзитивности?
14. 🤔✋ Транзитивный остов. Задано антисимметричное транзитивное отношение $R$ на $X$. Предолжите полиномиальный алгоритм построения отношения $S$, такого что $S^+=R$, причем в $S$ содержится минимальное число пар элементов.
15. 🤔 В предыдущем задании требование транзитивности опустить нельзя. Задано антисимметричное отношение $R$ на $X$. Докажите, что если существует полиномиальный алгоритм построения отношения $S$, такого что $S \subset R$ и $S^+=R^+$, причем в $S$ содержится минимальное число пар элементов, то можно проверить, есть ли в графе гамильтонов цикл (цикл, проходящий по каждой вершине графа ровно один раз) за полиномиальное время.
16. СКНФ. Будем называть формулу для функции совершенной конъюнктивной нормальной формой, если ее эта формула является конъюнкцией клозов, каждый из которых представляет дизъюнкцию переменных и их отрицаний, причем каждая переменная встречается в каждом клозе ровно один раз. Докажите, что любую функцию, кроме тождественной 1, можно представить в виде СКНФ.
17. Выразите в явном виде "и", "или" и "не" через стрелку Пирса
18. Выразите в явном виде "и", "или" и "не" через штрих Шеффера
19. Булева функция называется пороговой, если $f(x_1, x_2, \ldots, x_n) = 1$ тогда и только тогда, когда $a_1x_1+a_2x_2+\ldots+a_nx_n \ge b$, где $a_i$ и $b$ - вещественные числа. Докажите, что "и", "или", "не" - пороговые функции.
20. Приведите пример непороговой функции
21. Можно ли "и", "или" и "не" выразить через функции из множества $\{x\oplus y, x = y\}$?
22. Можно ли "и", "или" и "не" выразить через функции из множества $\{x\to y, {\mathbf 0}\}$?
23. Можно ли "и", "или" и "не" выразить через функции из множества $\{\langle xyz\rangle, \neg x\}$?
24. Можно ли "и", "или" и "не" выразить через функции из множества $\{{\mathbf 0}, \langle xyz\rangle, \neg x\}$?
25. Можно ли выразить "и" через "или"?
26. Выразите медиану 5 через медиану 3
27. 🤔 Выразите медиану $2n+1$ через медиану 3
28. 🤔 Рассмотрим булеву функцию $f$. Обозначим как $N(f)$ число наборов аргументов, на которых $f$ равна 1. Например, $N(\vee) = 3$. Обозначим как $\Sigma(f)$ сумму всех наборов аргументов, на которых $f$ равна 1 как векторов. Например, $\Sigma(\vee) = (2, 2)$. Докажите, что если для пороговой функции $f$ и функции $g$ выполнено $N(f) = N(g)$ и $\Sigma(f) = \Sigma(g)$, то $f = g$
29. 🤔✋ Говорят, что формула имеет вид 2-КНФ, если она имеет вид $(t_{11}\vee t_{12})\wedge(t_{21}\vee t_{22})\wedge\ldots$, где $t_{ij}$ представляет собой либо переменную, либо ее отрицание (в каждом дизъюнкте ровно два терма). Предложите полиномиальный алгоритм проверки, что формула, заданная в 2-КНФ имеет набор значений переменных, на которых она имеет значение 1.
30. 🤔✋ КНФ называется КНФ Хорна, если в каждом дизъюнкте не более одной переменной находится без отрицания. Пример: $x\wedge(x \vee \neg y \vee \neg z) \wedge (\neg x \vee \neg t)$. Предложите полиномиальный алгоритм проверки, что формула, заданная в форме КНФ Хорна имеет набор аргументов, на котором она равна 1.
31. 👻 Сколько существует самодвойственных функций от $n$ аргуметов?
32. Будем говорить, что функция существенно зависит от переменной $x_i$, если существует два набора аргументов, различающихся только значением $x_i$, на которых функция принимает различные значения. Сколько существует булевых функций от $n$ аргументов, существенно зависящих от всех аргументов? Достаточно привести рекуррентную формулу.
33. Приведите пример функции, существенно зависящей хотя бы от 3 аргументов, которая лежит во всех 5 классах Поста.
34. Приведите пример функции, существенно зависящей хотя бы от 3 аргументов, которая не лежит ни в одном классе Поста.
35. Булева функция $f(x_1, x_2, \ldots, x_n)$ называется форсируемой, если существует такое назначение $x_i=const$ , что для любых значений других переменных значение функции является константой. Например, $x_1 \wedge x_2$ является форсируемой, поскольку при $x_1 = 0$ значение функции равно 0 для любого значения $x_2$. Для каждой функции от двух переменных определите, является ли она форсируемой.
36. Булева функция называется симметричной, если ее значение не меняется при любой перестановке ее переменных. Сколько существует симметричных функций от $n$ переменных?
37. 🤔 Докажите, что любую функцию от $n$ переменных можно представить с использованием стрелки Пирса формулой, длиной не больше чем $2^n\cdot poly(n)$, где $poly(n)$ - полином, общий для всех функций
38. Докажите, что любую монотонную функцию можно выразить через "и", "или", 0 и 1.
39. 🤔 Докажите, что любую монотонную самодвойственую функцию можно выразить через медиану
40. Докажите, что если булеву функцию $f$ можно задать в форме Крома (в виде 2-КНФ), то выполнено следствие: $f(x_1, ..., x_n) = f(y_1, ..., y_n) = f(z_1, ..., z_n) = 1$ $\Rightarrow f(\langle x_1, y_1, z_1\rangle, ..., \langle x_n, y_n, z_n \rangle) = 1$
41. 😱 Докажите, что если выполнено следствие: $f(x_1, ..., x_n) = f(y_1, ..., y_n) = f(z_1, ..., z_n) = 1$ $\Rightarrow f(\langle x_1, y_1, z_1\rangle, ..., \langle x_n, y_n, z_n \rangle) = 1$, то булеву функцию $f$ можно задать в форме Крома.
42. Докажите, что если булеву функцию $f$ можно задать в форме Хорна, то выполнено следствие: $f(x_1, ..., x_n) = f(y_1, ..., y_n) = 1 \Rightarrow f(x_1\wedge y_1, ..., x_n \wedge y_n) = 1$
43. 😱 Докажите, что если выполнено следствие: $f(x_1, ..., x_n) = f(y_1, ..., y_n) = 1 \Rightarrow f(x_1\wedge y_1, ..., x_n \wedge y_n) = 1$, то булеву функцию $f$ можно задать в форме Хорна
44. Докажите, что $x_0\oplus x_1\oplus\ldots\oplus x_{2m} = \langle \neg x_0,s_1,s_2,\ldots,s_{2m}\rangle$, где $s_j=\langle x_0,x_j,x_{j+1},\ldots,x_{j+m-1},\neg x_{j+m},\neg x_{j+m+1},\ldots,\neg x_{j+2m-1}\rangle$, для удобства $x_{2m+k}$ обозначет то же, что и $x_k$ для $k \ge 1$.
45. Докажите, что биномиальный коэффициент $C_n^k$ нечетен тогда и только тогда, когда в двоичной записи $k$ единицы стоят только на тех позициях, где в двоичной записи $n$ также находятся единицы (иначе говоря, двоичная запись $k$ доминируется двоичной записью $n$ как двоичным вектором).
46. Докажите "метод треугольника" построения полинома Жегалкина по таблице истинности.
47. Постройте схему из функциональных элементов для операции медиана трех над базисом $\{ \vee, \wedge, \neg\}$. Постарайтесь использовать минимальное число элементов.
48. Постройте схему из функциональных элементов для операции $x \oplus y \oplus z$ над базисом $\{ \vee, \wedge, \neg\}$. Постарайтесь использовать минимальное число элементов.
49. Предложите способ построить схему для функции $x_1 \oplus ... \oplus x_n$ над базисом $\{ \vee, \wedge, \neg\}$ с линейным числом элементов и глубиной $O(\log n)$.
50. Докажите, что для функции "большинство из $2n+1$" существует схема из функциональных элементов глубины $O(\log n)$
51. Докажите, что любую булеву функцию от $n$ аргументов можно представить схемой из функциональных элементов, содержащей $O(2^n)$ элементов.
52. Докажите, что не существует схем константной глубины для функций $x_1 \vee ... \vee x_n$, $x_1 \wedge ... \wedge x_n$, $x_1 \oplus ... \oplus x_n$.
53. Мультиплексором называется схема, которая имеет $2^n+n$ входов и один выход. Обозначим входы как $x_0, x_1, \ldots, x_{2^n-1}, y_0, y_1, \ldots, y_{n-1}$. На выход подается то же, что подается на вход $x_i$, где $i$ - двоичное число, которое кодируется входами $y_0, \ldots, y_{n-1}$. Постройте схему линейного (от суммарного количества входов и выходов) размера для мультиплексора.
54. Дешифратором называется схема, которая имеет $n+1$ входов и $2^n$ выходов. Обозначим входы как $y_0, y_1, \ldots, y_{n-1}, x$, а выходы как $z_0, z_1, \ldots, z_{2^n-1}$. На все выходы подается 0, а на выход $z_i$ то же, что подается на вход $x$, где $i$ - двоичное число, которое кодируется входами $y_0, \ldots, y_{n-1}$. Постройте схему линейного (от суммарного количества входов и выходов) размера для дешифратора.
55. Игра "два шага вперед, один назад". Задана булева функция от $n$ аргументов $f(x_1, \ldots, x_n)$. Играют два игрока: 0 и 1. Игроки делают ходы по очереди. Для хода используется вспомогательное значение $m$, исходно равное 0, кроме того исходно все значения переменных не определены. Ход заключается в следующем. Игрок либо увеличивает $m$ на 2, либо уменьшает на 1. После этого действия значение $m$ должно удовлетворять неравенству $1 \le m \le n$. Затем, если значение $x_m$ не определено, то игрок присваивает переменной $x_m$ значение на свое усмотрение. Если же значение $x_m$ определено, то оно меняется на противоположное. Игра заканчивается, когда все значения определены. Если значение функции $f$ на получившемся наборе переменных равно 1, то выигрывает 1, иначе выигрывает 0. Проанализируйте описанную игру для значений $n$ от 2 до 9 на функции $f(x_1, \ldots, x_n)$, равной 1, если строка $x_1x_2\ldots x_n$ лексикографически строго меньше строки $x_nx_{n-1}\ldots x_1$.
56. Проанализируйте игру "два шага вперед, один назад" для значений $n$ от 2 до 9 на функции $f(x_1, \ldots, x_n)=x_1\oplus x_2\oplus \ldots\oplus x_n$.
57. Проанализируйте игру "два шага вперед, один назад" для значений $n$ от 2 до 9 на функции $f(x_1, \ldots, x_n)$, равной 1, если строка $x_1x_2\ldots x_n$ не содержит двух единиц подряд.
58. Проанализируйте игру "два шага вперед, один назад" для значений $n$ от 2 до 9 на функции $f(x_1, \ldots, x_n)$, равной 1, если строка $x_1x_2\ldots x_n$ представляет собой (возможно дополненную ведущими нулями) двоичную запись простого числа.дешифратора.
59. Контактной схемой называется ориентированный ациклический граф, на каждом ребре которого написана переменная или ее отрицание (ребра в контактных схемах называют контактами, а вершины - полюсами). Зафиксируем некоторые значения переменным. Тогда замкнутыми называются ребра, на которых записана 1, ребра, на которых записан 0, называются разомкнутыми. Зафиксируем две вершины $u$ и $v$. Тогда контактная схема вычисляет некоторую функцию $f$ между вершинами $u$ и $v$, равную 1 на тех наборах переменных, на которых между $u$ и $v$ есть путь по замкнутым ребрам. Постройте контактные схемы для функций "и", "или" и "не".
60. Постройте контактную схему для функции "xor".
61. Постройте контактную схему для функции медиана трех.
62. Докажите, что любую булеву функцию можно представить контактной схемой.
63. Постройте контактную схему "xor от $n$ переменных", содержащую $O(n)$ ребер.
64. Постройте контактную схему "большинство из $2n+1$ переменных", содержащую $O(n)$ ребер.
65. Постройте контактную схему, в которой для каждого из $2^n$ наборов дизъюнкций переменных и их отрицаний есть пара вершин, между которыми реализуется эта дизъюнкция, используя $O(2^n)$ ребер.
66. Докажите, что любую булеву функцию можно представить контактной схемой, содержащей $O(2^n)$ ребер.
67. Будем интерпретировать битовые строки длины $n$ как целые числа с соответствующей двоичной записью. Заданы $n$-битные числа $v_0 < v_1 < \ldots < v_{m-1}$. Предложите алгоритм за $O(m)$, который по заданным числам и числу $j$ находит все такие пары индексов $i, k$, что $v_i \oplus 2^j = v_k$. Считайте, что операции с числами выполняются за $O(1)$.
68. Приведите пример формулы, которая одновременно (а) равна тождественному нулю (б) находится в форме Хорна (в) находится в форме Крома (г) содержит хотя бы 3 переменные
69. Предложите алгоритм проверки, что можно выбрать удовлетворяющее назначение для формулы, которая является конъюнкцией клозов, каждый из которых является либо клозом Хорна, либо клозом Крома
70. Формулы с кванторами. Рассмотрим формулу с кванторами $Qx_1Qx_2\ldots Qx_n f(x_1, \ldots, x_n)$, где $Q$ может быть квантором "существует" или "для любого". Докажите, что если если $f(x_1,\ldots,x_n)$ имеет ровно $k$ удовлетворяющих её назначений переменных, то существует ровно $k$ (из $2^n$ возможных) формул с кванторами в указанной форме, которые являются истиными.
71. Для каких бинарных коммутативных операций $\circ$ выполнен распределительный закон для медианы $w\circ\langle xyz \rangle = \langle x\circ w, y \circ w, z \circ w\rangle$?
72. Можно ли выразить медиану трех через медиану пяти?
73. Как выглядит дерево Хаффмана для частот символов $1, 2, ..., 2^{n-1}$ (степени двойки) ?
74. Как выглядит дерево Хаффмана для частот символов $1, 1, 2, 3, ..., F_{n-1}$ (числа Фибоначчи)?
75. Докажите, что если размер алфавита - степень двойки и частоты никаких двух символов не отличаются в 2 или более раз, то код Хаффмана не лучше кода постоянной длины
76. Модифицируйте алгоритм Хаффмана, чтобы строить $k$-ичные префиксные коды
77. Обобщите неравенство Крафта-Макмиллана на $k$-ичные коды
78. Укажите, как построить дерево Хаффмана за линейное время, если символы уже отсортированы по частоте
79. Предложите алгоритм построения оптимального кода среди префиксных кодов с длиной кодового слова не более L бит
80. Предложите способ хранения информации об оптимальном префиксном коде для n-символьного алфавита, использующий не более $2n - 1 + n \lceil\log_2(n)\rceil$ бит ($\lceil x\rceil$ - округление $x$ вверх)
81. Можно ли разработать алгоритм, который сжимает любой файл не короче заданной величины $N$ хотя бы на 1 бит?
82. Приведите пример однозначно декодируемого кода оптимальной длины, который не является ни префиксным, ни развернутым префиксным
83. Для каких префиксных кодов существует строка, для которой он является кодом Хаффмана? Предложите алгоритм построения такой строки.
84. Пусть заданы пары $(u_i, v_i)$. Предложите полиномиальный алгоритм проверки, что существует код Хаффмана для некоторой строки, в котором $i$-е кодовое слово содержит $u_i$ нулей и $v_i$ единиц.
85. Докажите, что если в коде Хаффмана для некоторой строки $i$-е кодовое слово содержит $u_i$ нулей и $v_i$ единиц, то для многочлена от двух переменных $f(x, y) = \sum_{i=1}^n x^{u_i}y^{v_i}$ выполнено $f(x, y) - 1 = (x + y - 1) g(x, y)$ для некоторого многочлена $g(x, y)$.
86. Изучите коды Шеннона-Фано https://ru.wikipedia.org/wiki/%D0%90%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC_%D0%A8%D0%B5%D0%BD%D0%BD%D0%BE%D0%BD%D0%B0_%E2%80%94_%D0%A4%D0%B0%D0%BD%D0%BE. Приведите пример текста, для которого код Шеннона-Фано хуже кода Хаффмана.
87. Обобщите коды Шеннона-Фано на $k$-ичные коды.
88. При арифметическом кодировании может повезти и у достаточно длинной строки код получится коротким, хотя длина строки большая, и оценка на длину кода тоже большая. Приведите пример такой строки.
89. Для предыдущего задания приведите пример бесконечной последовательности строк возрастающей длины, для которых проявляется описанный эффект.
90. При арифметическом кодировании можно учитывать, что с учетом уже потраченных символов соотношения символов становятся другими и отрезок надо делить в другой пропорции. Всегда ли кодирование с таким уточнением лучше классического арифметического кодирования?
91. При арифметическом кодировании трудным моментом является деление отрезка в пропорциях, не являющихся степенями двойки. Рассмотрим модификацию арифметического кодирования, когда соотношения между символами приближаются дробями со знаменателями - степенями двойки. Что можно сказать про получившийся алгоритм?
92. Проанализируйте время работы алгоритма арифиметического кодирования
93. Троичное арифметическое кодирование. Пусть при арифметичском кодировании мы используем в качестве знаменателя не $2^q$, а $3^q$, а числитель записываем как трочное число. Затем это число записывается в двоичной записи. Приведите пример строки, когда такой метод будет лучше классического арифметического кодирования.
94. Приведите пример строки, когда такой метод будет хуже классического арифметического кодирования.
95. Докажите, что для любого $c > 1$ существует распределение частот $p_1, p_2, .., p_n$, что арифметическое кодирование в $c$ раз лучше Хаффмана
96. Докажите, что при оптимальном кодирование с помощью LZ не выгодно делать повтор блока, который можно увеличить вправо
97. Разработайте алгоритм оптимального кодирования текста с помощью LZ, если на символ уходит $c$ бит, а на блок повтора $d$ бит
98. Предложите семейство строк $S_1, S_2, \ldots, S_n, \ldots$, где $S_i$ имеет длину $i$, таких, что при их кодировании с помощью LZW длина строки увеличивается. Начальный алфавит $\{0, 1\}$.
99. Предложите алгоритм декодирования кода Барроуза-Уиллера.
100. Предложите алгоритм декодирования кода Барроуза-Уиллера за $O(n)$.
101. Предложите реализацию преобразования Move to Front за $O(n \log n)$.
102. Предложите реализацию преобразования Move to Front за $O(n)$.
103. Кодирование с ошибками. Пусть разрешается при декодировании неверно раскодировать не более одного бита. Можно ли каждую двоичную строку длиной не больше $n$ сжать, чтобы её размер уменьшился хотя бы на один символ?
104. Кодирование с ошибками. Пусть разрешается при декодировании неверно раскодировать не более одного бита. Можно ли каждую двоичную строку длиной от 2 до $n$ сжать, чтобы её размер уменьшился хотя бы на два символа?
105. Разработайте оптимальный код исправляющий одну ошибку при пересылке 2 битов
106. Разработайте оптимальный код исправляющий одну ошибку при пересылке 3 битов
107. Разработайте оптимальный код исправляющий одну ошибку при пересылке 4 битов
108. Разработайте код, исправляющий две ошибки, использующий асимптотически не более $2n$ бит для кодирования $2^n$ символьного алфавита (для $n > n_0$)
109. Докажите, что в зеркальном коде Грея $g_i = i \oplus \lfloor i / 2\rfloor$
110. Докажите, что в зеркальном коде Грея при переходе от $g_i$ к $g_{i+1}$ меняется тот же бит, который меняется с 0 на 1 при переходе от $i$ к $i+1$
111. Разработайте код Грея для k-ичных векторов
112. При каких $a_1, a_2, ..., a_n$ существует обход гиперпараллелепипеда $a_1 \times a_2 \times ... \times a_n$, который переходит каждый раз в соседнюю ячейку и бывает в каждой ячейке ровно один раз?
113. При каких $a_1, a_2, ..., a_n$ существует обход гиперпараллелепипеда $a_1 \times a_2 \times ... \times a_n$, который переходит каждый раз в соседнюю ячейку и бывает в каждой ячейке ровно один раз, а в конце возвращается в исходную ячейку?
114. Код "антигрея" - постройте двоичный код, в котором соседние слова отличаются хотя бы в половине бит
115. Троичный код "антигрея" - постройте троичный код, в котором соседние слова отличаются во всех позициях
116. При каких $n$ и $k$ существует двоичный $n$-битный код, в котором соседние кодовые слова отличаются ровно в $k$ позициях?
117. Докажите, что для достаточно больших $n$ существует код Грея, который отличается от любого, полученного из зеркального перестановкой столбцов, отражением и циклическим сдвигом строк
118. 🤔 Код Грея назвается монотонным, если нет таких слов $g_i$ и $g_j$, что $i < j$, а $g_i$ содержит на 2 или больше единиц больше, чем $g_j$. Докажите, что существует монотонный код Грея
119. Выведите рекуррентную формулу для числа комбинаторных объектов: вектор длины $2n$, в котором каждое число от $1$ до $n$ встречается ровно два раза.
120. Коды Грея для перестановок. Предложите способ перечисления перестановок, в котором соседние перестановки отличаются обменом двух соседних элементов (элементарной транспозицией).
121. Коды Грея для сочетаний. Предложите способ перечисления сочетаний, в котором соседние сочетания отличаются заменой одного элемента.
122. Коды Грея для размещений. Предложите способ перечисления размещений, в котором соседние размещения отличаются заменой одного элемента в одной позиции.
123. Докажите, что $C_r^mC_m^k=C_r^kC_{r-k}^{m-k}$.
124. Докажите, что $\sum_{k=0}^n C_{m+k}^k=C_{m+n+1}^n$.
125. Докажите, что $\sum_{k=0}^n C_r^kC_s^{n-k}=C_{r+s}^n$.
126. Докажите, что число Каталана $C_n = \frac{1}{n+1}C_{2n}^n$.
127. Докажите, что число различных триангуляций правильного $n$-угольника равно числу Каталана. В этом и нескольких следующих заданиях номер соответствующего числа Каталана может отличаться от $n$, требуется также установить соответствие между размером задачи и номерами чисел Каталана.
128. Докажите, что число двоичных деревьев с $n$ вершинами равно числу Каталана.
129. Докажите, что число подвешенных деревьев с порядком на детях с $n$ вершинами равно числу Каталана.
130. Будем называть последоватедовательность сортируемой стеком, если ее можно отсортировать, используя в произвольном порядке следующие операции: (а) взять первый элемент входной последовательности и положить в стек (б) взять верхний элемент стека и отправить в конец выходной последовательности. Докажите, что число перестановок $n$ элементов, сортируемых стеком, равно число Каталана.
131. Докажите, что число перестановок $n$ элементов, в которых нет возрастающей последовательности длины 3, равно числу Каталана.
132. Докажите, что число способов расставить числа от 1 до $2n$ в прямоугольник $2 \times n$, чтобы числа в каждой строке и каждом столбце возрастали, равно числу Каталана.
133. Матрица Ханкеля - матрица $n \times n$, такая что $a[i][j] = C_{i+j-2}$. Докажите, что определитель матрицы Ханкеля равен 1.
134. Факториальная система счисления. Рассмотрим систему счисления, где бесконечно много цифр, в $i$-м разряде (нумерация разрядов с 1 от младшего к старшему) разрешается использовать цифры от 0 до $i$, вес $i$-го разряда $i!$. Докажите, что у каждого положительного числа ровно одно представление в факториальной системе счисления (с точностью до ведущих нулей). Предложите алгоритм перевода числа в факториальную систему счисления.
135. Как связана факториальная система счисления и нумерация перестановок?
136. Фибоначчиева система счисления. Рассмотрим систему счисления, где есть две цифры, 0 и 1. Пусть нумерация разрядов ведется с 1 от младшего к старшему, вес $i$-го разряда $F_i$, где $F_i$ - $i$-е число Фибоначчи ($F_0 = 1$, $F_1 = 1$, нулевой разряд не используется). При этом запрещается исползовать две единицы в соседних разрядах. Сколько представлений в Фибоначчиевой системе счисления у положительного числа $x$? Предложите алгоритм перевода числа в фибоначчиеву систему счисления.
137. Свяжите фибоначчиеву систему счисления с нумерацией каких-либо комбинаторных объектов.
138. Укажите способ подсчитать число разбиений заданного $n$-элементного множества на $k$ упорядоченных непустых подмножеств (например, для $n = 3$, $k = 2$ есть следующие разбения: $\{[1], [2, 3]\}$, $\{[1], [3, 2]\}$, $\{[1, 2], [3]\}$, $\{[1, 3], [2]\}$, $\{[2, 1], [3]\}$, $\{[2], [3, 1]\}$.
139. Подъемом в перестановке называется пара соседних элементов, таких что $a_{i-1} < a_i$. Выведите рекуррентную формулу для числа перестановок $n$ элементов с $k$ подъемами
140. Неподвижной точкой в перестановке называется элемент $a_i = i$. Выведите рекуррентную формулу для числа перестановок $n$ элементов с $k$ неподвижными точками
141. Выведите рекуррентную формулу для числа разбиений числа $n$ на нечетные слагаемые
142. Выведите рекуррентную формулу для числа разбиений числа $n$ на нечетное число слагаемых
143. Выведите рекуррентную формулу для числа разбиений числа $n$ на различные слагаемые
144. Предложите алгоритм подсчета количества разбиений числа $n$ на слагаемые за $O(n\sqrt{n})$.
145. Выведите рекуррентную формулу для числа разбиений числа $a+ib$, где $a$ и $b$ целые неотрицательные числа, на комплексные слагаемые вида $c + id$, где $c$ и $d$ целые неотрицательные числа, хотя бы одно из которых положительно.
146. Раскрашенные слагаемые. Будем называть разбиение числа $n$ на положительные слагаемые раскрашенным, если каждому слагаемому сопоставлен один из $k$ заданных цветов. Два разбиения считаются одинаковыми, если слагаемые в одном из них можно переставить так, чтобы получилось другое разбиение (цвета после перестановки тоже должны совпасть). Выведите рекуррентную формулу для числа раскрашенных разбиений числа $n$ на слагаемые
147. Разноцветные слагаемые. Будем называть разбиение числа $n$ на положительные слагаемые разноцветным, если каждому слагаемому сопоставлен один из $k$ заданных цветов, причем одинаковым числам в разбиении не сопоставляются одинаковые цвета. Два разбиения считаются одинаковыми, если слагаемые в одном из них можно переставить так, чтобы получилось другое разбиение (цвета после перестановки тоже должны совпасть). Выведите рекуррентную формулу для числа разноцветных разбиений числа $n$ на слагаемые
148. Группа называется абелевой, если для любых двух элементов выполнено $ab = ba$. Какое минимальное число элементов может быть в неабелевой группе?
149. Найдите число таких различных булевых функций от 2 переменных, что ни одна из них не может быть получена ни из какой другой навешиванием отрицаний над переменными
150. Найдите число таких различных булевых функций от $n$ переменных, что ни одна из них не может быть получена ни из какой другой навешиванием отрицаний над переменными
151. Выведите формулу для числа ожерелий из $n$ бусинок $k$ цветов с точностью до циклического сдвига и отражения.
152. Выведите формулу для числа ожерелий из $n$ бусинок 2 цветов с точностью до циклического сдвига, в которых ровно две белые бусины.
153. Выведите формулу для числа ожерелий из $n$ бусинок 2 цветов с точностью до циклического сдвига, в которых ровно $k$ белых бусин.
154. Пусть $p$ простое. Найдите число ожерелий из $p^2$ бусинок 2 цветов с точностью до циклического сдвига.
155. Пусть $p$ и $q$ простые. Найдите число ожерелий из $pq$ бусинок 2 цветов с точностью до циклического сдвига.
156. Выведите формулу для числа раскрасок $n$ шаров в $k$ цветов, порядок не важен.
157. Выведите формулу для числа раскрасок прямоугольника $n \times m$ в $k$ цветов с точностью до отражения относительно горизонтальной и вертикальной оси.
158. Выведите формулу для числа раскрасок граней тетраэдра в $k$ цветов с точностью до любого поворота в 3D.
159. Выведите формулу для числа раскрасок ребер тетраэдра в $k$ цветов с точностью до любого поворота в 3D.
160. Выведите формулу для числа раскрасок граней куба в $k$ цветов с точностью до любого поворота в 3D.
161. Выведите формулу для числа раскрасок ребер куба в $k$ цветов с точностью до любого поворота в 3D.
162. Выведите формулу для числа раскрасок граней октаэдра в $k$ цветов с точностью до любого поворота в 3D.
163. Почему мы не сделали задачу про вершины тетраэдра, вершины куба, вершины и ребра октаэдра? Неужели оставили на контрольную?
164. Пусть 2 - множество из двух различных элементов, каждый из которых имеет вес 1. Можно условно называть их черный и белый. Что представляет собой $Seq(2)$? Посчитайте число элементов для него, в зависимости от веса.
165. Что представляет собой $Set(2)$? Посчитайте число элементов для него, в зависимости от веса.
166. Что представляет собой $MSet(2)$? Посчитайте число элементов для него, в зависимости от веса.
167. Что представляет собой $Cycle(2)$? Посчитайте число элементов для него, в зависимости от веса.
168. Пусть $F$ - множество из двух различных элементов, один из которых имеет вес 1, а другой - 2. Можно условно называть их маленький и большой. Что представляет собой $Seq(F)$? Посчитайте число элементов для него, в зависимости от веса.
169. Что представляет собой $Set(F)$? Посчитайте число элементов для него, в зависимости от веса.
170. Что представляет собой $MSet(F)$? Посчитайте число элементов для него, в зависимости от веса.
171. Что представляет собой $Cycle(F)$? Посчитайте число элементов для него, в зависимости от веса.
172. Пусть $A$ - комбинаторные объекты. Выведите формулу для числа элементов в зависимости от веса для $Pair(Seq(A), Seq(A))$.
173. Пусть $A$ - комбинаторные объекты. Обозначим как $Seq^+(A)$ множество непустых последовательностей из элементов $A$. Выведите рекуррентную формулу для числа элементов в зависимости от веса для $Seq^+(Seq^+(A))$.
174. Пусть $A$ - комбинаторные объекты. Обозначим как $Seq^1(A) = Seq^+(A)$, $Seq^k(A) = Seq^+(Seq^{k-1}(A))$. Выведите рекуррентную формулу для числа элементов в зависимости от веса для $Seq^k(A)$.
175. Разбиения на множества. Проинтерпретируйте разбиения $n$-элементного множества на $k$ множеств как конструируемый помеченный комбинаторный объект. Получите альтернативную рекуррентную формулу для чисел Стирлинга 2 рода.
176. Разбиения на циклы. Проинтерпретируйте разбиения $n$-элементного множества на $k$ циклов как конструируемый помеченный комбинаторный объект. Получите альтернативную рекуррентную формулу для чисел Стирлинга 1 рода.
177. Раскрашенные деревья. Выведите формулу для числа подвешенных деревьев с $n$ вершинами без порядка на детях, раскрашенных в $k$ цветов.
178. Раскрашенные деревья. Выведите формулу для числа подвешенных деревьев с $n$ вершинами с порядком на детях, раскрашенных в $k$ цветов.
179. Будем называть граф циклическим мультибамбуком, если он устроен следующим образом: есть цикл, из каждой вершины которого выходит путь. Предложите способ посчитать непомеченные циклические мультибамбуки.
180. Предложите способ посчитать помеченные циклические мультибамбуки.
181. Подсчет помеченных унициклических графов. Граф называется унициклическим, если он содержит ровно один цикл. Предложите способ подсчета помеченных унициклических графов.
182. Подсчет помеченных двудольных графов. Граф называется двудольным, если его вершины можно разбить на два множества, таких что ребра соединяют только вершины различных множеств. Сколько существует помеченных двудольных графов?
183. Подсчет помеченных связных двудольных графов. Сколько существует помеченных связных двудольных графов?
184. Докажите, что в любой перестановке $n$ элементов найдется возрастающая последовательность из $\sqrt{n}$ элементов или убывающая последовательнтсть из $\sqrt{n}$ элементов.
185. Докажите, что среди любых 5 точек общего положения на плоскости (никакие три не лежат на одной прямой) можно выбрать 4, которые являются вершинами выпуклого многоугольника.
186. Какое число точек необходимо для того, чтобы среди них можно было выбрать 5, являющихся вершинами выпуклого пятиугольник?
187. Докажите, что для любого $r$ существует $K(r)$, такое что среди любых $K(r)$ точек общего положения на плоскости (никакие три не лежат на одной прямой) можно выбрать $r$, которые являются вершинами выпуклого многоугольника.
188. 🔎 Теорема Ван дер Вардена. Докажите, что для любых $n$ и $k$ найдется такое $W(n, k)$, что если числа от $1$ до $W(n, k)$ покрасить в $k$ цветов, то найдется арифметическая прогрессия длины $n$, покрашенная в один цвет.
189. Все клетки бесконечного листа клетчатой бумаги раскрасили в $n$ цветов. Докажите, что найдутся четыре вершины прямоугольника со сторонами, параллельными осям координат, которые покрашены в один цвет.
190. Все клетки бесконечного листа клетчатой бумаги раскрасили в $n$ цветов. Докажите, что для любых $k$ и $l$ найдутся $k$ строк и $l$ столбцов, что все $kl$ их клеток пересечения покрашены в один и тот же цвет.