Изменения

Перейти к: навигация, поиск

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

5213 байт добавлено, 23:26, 16 декабря 2022
Нет описания правки
# Сопряжением перестановки $\alpha$ относительно перестановки $\tau$ называется перестановка $\tau^{-1}\alpha\tau$. Две перестановки $\alpha$ и $\beta$ называются сопряженными, если существует такая перестановка $\tau$, что $\beta = \tau^{-1}\alpha\tau$. Докажите, что сопряжение является отношением эквивалентности.
# Докажите, что две перестановки являются сопряженными тогда и только тогда, когда их циклические классы совпадают.
# В вершинах правильного $n$-угольника записаны числа от $1$ до $n$. Рассмотрим две операции: поворот на угол $2\pi i/n$ и отражение относительно прямой, проходящей через центр многоугольника, после которого вершины оказываются в тех же точках. Докажите, что композиция отражения и поворота является отражением.
# В вершинах правильного $n$-угольника записаны числа от $1$ до $n$. Рассмотрим две операции: поворот на угол $2\pi i/n$ и отражение относительно прямой, проходящей через центр многоугольника, после которого вершины оказываются в тех же точках. Докажите, что композиция двух отражений является поворотом.
# В вершинах правильного $n$-угольника записаны числа от $1$ до $n$. Рассмотрим две операции: поворот на угол $2\pi i/n$ и отражение относительно прямой, проходящей через центр многоугольника, после которого вершины оказываются в тех же точках. Зафиксируем конкретную прямую, относительно которой можно делать отражение. Докажите, что композиция любой последовательности отражений и поворотов является либо поворотом, либо композицией поворота и отражения относительно зафиксированной прямой.
# Выведите формулу для числа ожерелий из $n$ бусинок $k$ цветов с точностью до циклического сдвига и отражения.
# Выведите формулу для числа ожерелий из $n$ бусинок 2 цветов с точностью до циклического сдвига, в которых ровно две белые бусины.
# Выведите формулу для числа ожерелий из $n$ бусинок 2 цветов с точностью до циклического сдвига, в которых ровно $k$ белых бусин.
# Пусть $p$ простое. Найдите число ожерелий из $p^2$ бусинок 2 цветов с точностью до циклического сдвига.
# Пусть $p$ и $q$ простые. Найдите число ожерелий из $pq$ бусинок 2 цветов с точностью до циклического сдвига.
# Найдите число таких различных булевых функций от 2 переменных, что ни одна из них не может быть получена ни из какой другой навешиванием отрицаний над некоторыми переменными
# Найдите число таких различных булевых функций от $n$ переменных, что ни одна из них не может быть получена ни из какой другой навешиванием отрицаний над некоторыми переменными
# Выведите формулу для числа раскрасок $n$ шаров в $k$ цветов, порядок не важен.
# Выведите формулу для числа раскрасок прямоугольника $n \times m$ в $k$ цветов с точностью до отражения относительно горизонтальной и вертикальной оси.
# Выведите формулу для числа раскрасок граней тетраэдра в $k$ цветов с точностью до любого поворота в 3D.
# Выведите формулу для числа раскрасок ребер тетраэдра в $k$ цветов с точностью до любого поворота в 3D.
# Выведите формулу для числа раскрасок граней куба в $k$ цветов с точностью до любого поворота в 3D.
# Выведите формулу для числа раскрасок ребер куба в $k$ цветов с точностью до любого поворота в 3D.
# Выведите формулу для числа раскрасок граней октаэдра в $k$ цветов с точностью до любого поворота в 3D.
# Почему мы не сделали задачу про вершины тетраэдра, вершины куба, вершины и ребра октаэдра? Неужели оставили на контрольную?

Навигация