Помощь - Поиск - Пользователи - Календарь
Полная версия: Дискретная математика
Форум «Всё о Паскале» > Образование и наука > Математика
setare
Вот задачи, которые нам задали решить, но как решить не сказали и бросили на произвол судьбы. В книгах в библиотеках вообще ничего найти нельзя. Не могли бы вы помочь хотя бы какую то часть решить. Буду вам очень благодарна. Только пожалуйста, умоляю обьясняйте чуть чуть понятнее, потому что я в этом вообще ничго не смыслю. Спасибо огромное!!!
Вот задачи:
1.Какова мощность множества всех корней уравнения x5-2x3+x=0.
2.Доказать, что множество всех счетных последовательностей натуральных чисел имеет мощность континуума.
3.Доказать, что если отношения R1 и R2 рефлексивны, то рефлексивны и отношения R1R2, R1R2, R1-1, R1R2.
4.Найти порядок перестановки
(1 2 3 4 5 6 7 8 9)
(3 5 7 9 6 8 1 2 4).
5.Найти смежные классы аддитивной группы целых чисел по подгруппе чисел, кратных данному натуральному числу n ( Z + / nZ ).
6.Построить группу симметрий куба. Каков наивысший порядок циклических подгрупп, содержащихся в ней?
7.Найти натуральное число, меньшее 1000, имеющее наибольшее количество делителей.
8. Пусть p-простое число, p>3. Доказать, что если сравнение
x2 + x + 1 = 0 (mod p)
разрешимо, то p имеет вид 6n +1. Вывести отсюда, что множество
простых чисел вида 6n +1 бесконечно.
10. Будет ли множество Z целых чисел подгруппой аддитивной группы,
a + bi с целыми a и b ?
подкольцом или идеалом в кольце А целых гауссовых чисел, т.е. чисел вида
Atos
1. Решить уравнение и посчитать число корней. (Если имеются в виду рациональные). Действительных корней же у уравнения пятого порядка всегда 5.


4. Циклы
(1 3 7)
(3 7 1)

(2 5 6 8)
(5 6 8 2)

(4 9)
(9 4)
Порядок равен НОК длин цикла, т. е. НОК(3, 4, 2) = 12.


2. Легко можно доказать, что мощность не меньше мощности континуума.
Сопоставим каждой бесконечной десятичной дроби из интервала (0,1) счётную последовательность цифр её десятичной записи после запятой. Мощность интервала равна мощности континуума, откуда и следует то, что нам надо.

Сложнее будет доказать в обратную сторону. В принципе, идея есть, но сформулировать надо...


В общем, вечером посмотрю задания.
setare
Большое Вам спасибо! Если вы мне поможете с этими задачами я вам буду очень очень благодарна!!!!! :flowers: smile.gif
setare
Извините, а в 4 задании порядок перестановки равен 12 или мне надо найти еще перестановки? И почему вы взяли именно НОК(3,4,2)?
Atos
Цитата
Большое Вам спасибо! Если вы мне поможете с этими задачами я вам буду очень очень благодарна!!!!!
да не за что :p2: лишняя тренировка в преддверии госэкзаменов только на пользу ;) И можно на "ты" smile.gif .Постараюсь помочь. Кстати,а когда эти задачи надо сдавать?

Цитата
Извините, а в 4 задании порядок перестановки равен 12 или мне надо найти еще перестановки? И почему вы взяли именно НОК(3,4,2)?

Порядок равен 12. Насчёт НОК... как бы объяснить... циклы мы можем рассматривать независимо, и их порядок равен их длинам. Порядок подставноки должен делиться на порядки её циклов, так как это та степень, при возведении в которую перестановка равна тождественной, а значит, и каждый из циклов должен "прокрутиться" целое цисло раз... А так как порядок - наименьшая такая степень, то и берём НОК.

5. Смежными классами будут nZ, nZ+1, nZ+2, ... nZ+n-1. Например, для n=3:
nZ = {... , -3, 0 , 3, 6, ...}
nZ+1 = {... , -5, -2, 1, 4, ...}
nZ+2 = {... , -4, -1, 2, 5, ...}

А что это за квадратики в третьем задании? И десятое, вроде не до конца дописано?
Atos
2. Дошло, как доказать в обратную сторону: сопоставим последовательностям различные числа из (0,1) следующим извращенческим способом: переведём элементы последоательности в девятиричную систему счисления :D и запишем их подряд, вставляя в промежутки между ними девятки. Допишем слева ноль и запятую и получим бесконечную десятичную дробь из (0, 1), для каждой последовательности свою.
setare
Привет! Задачи надо сдавать 17 октября. Кстати 10 номера не надо. Мы его отвоевали у препода. Я не знаю как заменить квадратики. Но в 3 задании второе соотношение после первой запятой там знак пересечения, парабола ветвями вниз в первом случае наоборот. В последнем квадратик обозначает какой-то кружочек маленький наверху между R1 and R2.
setare
Остались самые сложные задачи 3,6,7,8! Их никто не знае как решить даже препод тормозил и сказал сами решайте.
Atos
7. Странная задача. Интересно, это всё руками надо проверять или какой-нибудь специальный алгоритм построения чисел с максимальным количеством делителей есть? В общем, ответ - число 840, имеет 32 делителя. Посчитано этой прогой, которая тупым перебором выдаёт число с наибольшим количеством делителей, которое меньше введённого.


{$n+} program test;
uses crt;
var i,j,k,n,tmpmax, maxN,max:word;
begin
readln(n);
max:=0;
maxN:=1;
for i:=1 to n-1 do
begin
tmpmax:=0;
for j:=1 to i do
if i mod j = 0 then inc(tmpmax);
if tmpmax> max then begin max:=tmpmax; maxN:=i; {write(maxN,' ',max,' ');} end;
end;
writeln(maxN);
readln;
end.



8. Заковыристая, однако, задача... Можно доказать, что x^2+x+1 делится на (6n+1) для некоторого n, но после этого надо ещё доказать, что это самое (6n+1)- простое и не раскладывается на (6p-1)(6s-1) для некоторых p и s. Будем думать...

6. Если группа симметрий- синоним группы поворотов куба, то эта группа изоморфна группе всех перестановок из 4 элементов и наивысший порядок циклических подгрупп равен 4.
См. подробноНажмите для просмотра прикрепленного файлаНажмите для просмотра прикрепленного файлаНажмите для просмотра прикрепленного файла
setare
А вообще-то там не алгоритм Евклида случайно используется?Ведь надо же написать как я это посчитала, не перебором же :D ?
Atos
А почему бы и нет? :D В принципе, препод должен сам объяснить алгоритм или хотя бы сказать, где его прочесть, else его проблемы angry.gif вешать таких преподов... а вообще я действительно не знаю, каким боком тут можно применить алгоритм Евклида sad.gif общей закономерности в числах, которые у меня получались, вроде не видно...

3. Посмотрел теорию отношений. В приципе, там довольно всё просто, только расписывать решение лень, ещё и тегов символов математических нет... Могу или всё-таки написать, или, если у тебя есть просмотрщик .djvu - файлов, сбросить на мыло книжку Новикова "Дискретная математика для программистов" - просто суперская вещь!!! Там очень многие разделы математики понятно излагаются, да ещё и с алгоритмами на псевдоПаскале. Весит 2.32 mb.
Кстати, заодно тогда уже могу и djvu - плагин к InternetExplorer кинуть. Размер точно не помню, по-моему в районе от 1 до нескольких метров.

6. Думаем потихоньку... :ypr:
(В следущий раз на форум только в понедельник зайду. )
setare
Давай скинь, у меня все есть. Я имею ввиду djvu. Все, что нужно скинь. Если хочешь на имейл, то вот он:marjan99@mail.ru
Atos
Так, файлы скинул, теперь насчёт оставшейся восьмой задачи:
В общем, можно рассуждать следующим образом: проверить, что x^2+x+1 может быть сравнимо только с единицей или с тройкой по модулю 6, и , таким образом, представимо либо в виде (6n+1), либо в виде (3^m) * (6n+1). Однако проблема состоит в том, что в таблице умножения вычетов по модулю 6 единица может получаться двумя способами - как единица в квадрате либо как пятёрка в квадрате. И если (6n+1) раскладывается некоторым образом в (6k+5)(6l+5), то получаем простые числа, такие, что x^2+x+1 сравнимо с нулём по их модулям, но сами они не представимы в виде (6n+1) sad.gif . То есть данную задачу можно свести к следующему утверждению: доказать, что x^2+x+1 не делится на (6k+5) для любых натуральных x и k. Только вот как это сделать... sad.gif

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

p- простое --> p-нечётное --> p= 2k+1. Докажем, что k=3n. От противного: пусть k не делится на 3 --> так каk x(x+1) = 2k, то ни x, ни (x+1) не делятся на 3 --> (x-1) и (x+2) делятся на 3 --> p=x(x+1)+1 = (x-1)(x+2)+3+1 = 3*((x-1)(x+2)/3 +1) +1 = 3t+1. Таким образом, p=2k+1=2(3n)+1=6n+1.
Guest
Большое спасибо за книгу и за обьяснение, я думаю я воспользуюсь неправильным доказательством, авось прокатит! smile.gif Спасибо за все!У меня уже появилась комбинаторика! :D Буду пробовать сама все сделать, но если будут вопросы может обращусь, если ничего!
Atos
Интересно, купился ли препод на утку? rolleyes.gif
setare
Привет! Представляешь на твой ответ ответ положительный! Он купился! даже ошибки не нашел! Спасибо Большое за помощь!!! теперь у нас комбинаторика! Там уже лучше, но все равно кое-какие задачи непонятны! У тебя случайно нет в цифровом виде уч по комбин?
Altair
лекции по комбинаторики
http://www.mccme.ru/ium/f00/comb.html
кое-точ из теории
http://combinatorics.by.ru/russian.htm

Если будешь спрашивать по комбинаторике, создавай тему новую пожалуйста smile.gif
setare
Хорошо! Обязательно!
Guest
помогите решить
(x-1)(x-2)(x-3)(x-4)=840


М
Не надо лезть в чужую тему! Создавай собственную!

HeX
Почитай вот ето
Atos
Всё-таки покопался и нашёл эту тему. Не люблю оставшихся нерешёнными задач, а эта (которая номер 8) очень долго меня мучала. Правильное решение её я всё-таки узнал от нашего препода, ведущего кодирование (а кодирование это на 90% алгебра, теория групп и теория чисел):

Цитата

Можно рассуждать, используя факт: если порядок элемента поля GF(p) равен k, то p-1 делится на k (это следует из теоремы Лагранжа). Теперь, домножив обе части уравнения на (x-1), получим x^3-1 = 0 (mod p), откуда x^3=1. Т.к. p>3, то x не может быть равен 1. Кроме того, x^2 = -x-1 не равно 1, т.к. иначе x=-2 и x^2+x+1 = 3 =/=0, потому что опять p>3. Значит, порядок x равен 3, откуда p-1 делится на 3. Осталось найти элемент порядка 2. Это, очевидно, будет -1.
Теперь p-1 делится на 2 и на 3, а значит p=6n+1.

В общем, неплохая очень задача: вроде выглядит и просто, но для решения нужно догадаться применить разность кубов и вспомнить факты из теории. В хит-параде задач заняла бы заслуженное место smile.gif
how does plaquenil work for auto
Propecia Achat
Это текстовая версия — только основной контент. Для просмотра полной версии этой страницы, пожалуйста, нажмите сюда.