Дискретная математика, задачи Опции

[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) счётную последовательность цифр её десятичной записи после запятой. Мощность интервала равна мощности континуума, откуда и следует то, что нам надо.

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


В общем, вечером посмотрю задания.

Сообщение отредактировано: Atos - 3.10.2005 13:42

[setare]

Большое Вам спасибо! Если вы мне поможете с этими задачами я вам буду очень очень благодарна!!!!! :flowers:

[setare]

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

[Atos]

Большое Вам спасибо! Если вы мне поможете с этими задачами я вам буду очень очень благодарна!!!!!

да не за что :p2: лишняя тренировка в преддверии госэкзаменов только на пользу ;) И можно на "ты" .Постараюсь помочь. Кстати,а когда эти задачи надо сдавать?

Извините, а в 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.
См. подробно

Сообщение отредактировано: Atos - 5.10.2005 6:13

[setare]

А вообще-то там не алгоритм Евклида случайно используется?Ведь надо же написать как я это посчитала, не перебором же :D ?

Сообщение отредактировано: setare - 5.10.2005 16:57

[Atos]

А почему бы и нет? :D В принципе, препод должен сам объяснить алгоритм или хотя бы сказать, где его прочесть, else его проблемы вешать таких преподов... а вообще я действительно не знаю, каким боком тут можно применить алгоритм Евклида общей закономерности в числах, которые у меня получались, вроде не видно...

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) . То есть данную задачу можно свести к следующему утверждению: доказать, что x^2+x+1 не делится на (6k+5) для любых натуральных x и k. Только вот как это сделать...

Правда, могу предложить неправильное доказательство :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.

Сообщение отредактировано: Atos - 12.10.2005 11:53

[Guest]

Большое спасибо за книгу и за обьяснение, я думаю я воспользуюсь неправильным доказательством, авось прокатит! Спасибо за все!У меня уже появилась комбинаторика! :D Буду пробовать сама все сделать, но если будут вопросы может обращусь, если ничего!

[Atos]

Интересно, купился ли препод на утку?

[setare]

Привет! Представляешь на твой ответ ответ положительный! Он купился! даже ошибки не нашел! Спасибо Большое за помощь!!! теперь у нас комбинаторика! Там уже лучше, но все равно кое-какие задачи непонятны! У тебя случайно нет в цифровом виде уч по комбин?

[Altair]

лекции по комбинаторики
http://www.mccme.ru/ium/f00/comb.html
кое-точ из теории
http://combinatorics.by.ru/russian.htm

Если будешь спрашивать по комбинаторике, создавай тему новую пожалуйста

[setare]

Хорошо! Обязательно!

[Guest]

помогите решить
(x-1)(x-2)(x-3)(x-4)=840

М

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

[HeX]

Почитай вот ето