Задачки по дискретной математике

[mastedm]

Доброго времени суток.

Ситуация такая, что знакомый попросил помочь решить несколько задач по Дискретке. Сам я проходил её три года назад, поэтому что-то подзабыл, а чего-то и не знал.

В одной из задач нужно вычислить подгруппу, порожденную 8 в мультипликативной группе вычетов по модулю 97. Я мозгами пораскинул так:
группа вычетов по модулю 97 это {0,1,2,...,96}, тогда подгруппа вроде должна быть такая {1,8,64}, но вот только проблема - она вроде группой не является. Короче, я запутался.

[Brukvalub]

А где же, например, элемент 64х8-5х97=27

[Someone]

Мультипликативная группа вычетов по модулю $97$ - это $\{1,2,3,\ldots,96\}$, то есть, без $0$. Искомая подгруппа - циклическая, образованная степенями порождающего элемента. В общем, вычисляйте степени $8^1\pmod{97}$, $8^2\pmod{97}$, $8^3\pmod{97}$, ..., пока не получится $1$.

Добавлено спустя 4 минуты:

Brukvalub писал(а):

А где же, например, элемент 64х8-5х96=32

Тут у Вас опечатка, наверное. Должно быть $64\times 8-5\times 97=27$.

[Brukvalub]

Someone писал(а):

Brukvalub писал(а):
А где же, например, элемент 64х8-5х96=32


Тут у Вас опечатка, наверное. Должно быть $64\times 8-5\times 97=27$.

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

[mastedm]

Получается, что подгруппа у меня такая:
H = \{1, 8, 12, 18, 22, 27, 33, 47, 50, 64, 70, 75, 79, 85, 89, 96\}

Смежный класс gH, где g = 4:
gH = \{4, 6, 9, 11, 25, 32, 35, 48, 49, 62, 65, 72, 86, 88, 91, 93\}

Добавлено спустя 16 минут 54 секунды:

В продолжении задания нужно каждый элемент класса gH представить в виде двоичного числа длины 7. Получилось у меня вот что:
4 0000100 6 0000110 9 0001001 11 0001011 25 0011001 32 0100000 35 0100011 48 0110000 49 0110001 62 0111110 65 1000001 72 1001000 86 1010110 88 1011000 91 1011011 93 1011101
Теперь из этих векторов нужно построить диаграмму Хассе для отношения порядка. Я не совсем пойму, какие узлы должны соединяться.

Ещё нужно выписать три максимальные цепи и антицепи. В этом тоже проблема. Что такое антицепи?

[Brukvalub]

mastedm писал(а):

Что такое антицепи?

У Вас же есть Интернет: http://d1.hse.ru/data/137/315/1234/ltida2_1909.pdf

[Профессор Снэйп]

mastedm писал(а):

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

Вероятно, считается, что последовательность $\varepsilon_1\ldots\varepsilon_7$ длины $7$, составленная из нулей и единиц, меньше либо равна аналогичной последовательности $\delta_1\ldots\delta_7$ если $\varepsilon_i \leqslant \delta_i$ для всех $i \in [1,7]$. Соответственно на диаграмме Хассе последовательность $0000100$ будет минимальным элементом (меньше может быть только последовательность $0000000$, а её в нашем списке нет), прямо над ней будет последовательность $0000110$ и так далее...

P. S. Антицепь --- это подмножество, состоящее из попарно не сравнимых элементов. Нарисуете диаграмму, на ней цепи и антицепи видны будут.

P. P. S. Ну и муторные же задания задают Вашему другу! Зачем так много считать? Понимание идей можно продемонстрировать и на более простых примерах. Им потом самим не лень всё это проверять будет

[mastedm]

Вот что получилось:

Соответсвенно, цепь это путь по стрелочкам, а антицепь - путь против стрелочек?

[Someone]

mastedm писал(а):

антицепь - путь против стрелочек?

Антицепь - это подмножество, в котором никакие два элемента не соединены стрелочкой. Например, $\{35,48,6,65,25,88,11\}$.

[mastedm]

Нужно было найти три максимальных цепи и три максимальных антицепи. Вот что у меня получилось.
Цепи:$\{32, 48, 49\}, \{9, 25, 93\}, \{72, 88, 91\}$
Антицепи:

$$\{35, 49, 62, 86, 65, 25, 88, 11\}, \{35, 48, 6, 65, 25, 88, 11\}, \{35, 49, 62, 86, 93, 91\}$$

[Профессор Снэйп]

Надо ещё отметить, что диаграмма Хассе немного неверно нарисована. На этих диаграммах стрелки не дублируют. В частности, если есть стрелка из 32 в 48, а также стрелка из 48 в 49, то не нужно рисовать стрелку из 32 в 49, поскольку из 32 в 49 уже можно пройти по стрелкам. На правильной диаграмме стрелок должно быть меньше.

[mastedm]

Исправленная версия: