Записи с темой: дискретная математика (список заголовков)
20:30 

Раскраска домов

wpoms.
Step by step ...


На улице Антонио сто домов, пронумерованных числами от единицы до ста. Любой дом, чей номер равен разности номеров домов, покрашенных в один цвет, покрашен в цвет отличный от цвета этих двух домов. Докажите, что на улице Антонио есть дома по крайне мере пяти разных цветов.



@темы: Дискретная математика

19:25 

Доказательство лемм

Добрый день,

В работе над курсовой работой у меня возникла потребность в доказательстве вспомогательных лемм. К сожалению, доказательство собственных теорем/лемм - самый слабый мой математический навык и я был бы благодарен за помощь в данной проблеме. Прочитал книжку Успенского про примеры математических доказательств, но ни на какие мысли это меня не натолкнуло.
Суть лемм состоит в следующем. У нас имеется модель процесса в виде сети Петри, а точнее ее развертки, которое можно рассматривать как параллельное исполнение, а также все возможные последовательные исполнения процесса. Я исследую отношения между событиями процесса: `>`: `e > e'` - если случилось событие `e'`, то `e` случилось до этого; `#`: `e # e'` - события `e` и `e'` никогда не встречаются в одном последовательном исполнении; `e || e'` - `neg (e > e') wedge neg (e' > e) wedge neg (e # e')`. Так, например, для процесса на картинке, имеем следующие последовательные исполнения: `adc`, `acd`. `cad`, `b`. Т.е. события находятся в следующих отношениях: `a || c`, `d || c`, `a > d`, `a # b`, `c # b`, `d # b`.


Необходимо доказать, что если два события находятся в каком-либо отношении в параллельном исполнении, то они будут находится в этом отношении и во всех его последовательных исполнениях и наоборот (если два события находятся в каком-либо отношении во всех последовательных исполнениях, то они будут находится в этом отношении и в параллельном исполнении). Нужно ли вообще это формально доказывать? Не вытекает ли это с очевидностью из определений отношений?

@темы: Дискретная математика, Бинарные отношения

10:03 

помогите если можно то с описанием решения

Отношение Т: «иметь один и тот же остаток при делении на 4» задано на множестве Х={6, 7, 8, 9, 10, 11, 12, 13}. Является ли оно отношением эквивалентности.

@темы: Дискретная математика

10:59 

помогите решить

задайте всеми известными способами соответствия между множествами Х={3,4,5,9} и Y={135,0,264,122} "число х является делителем числа y"

@темы: Дискретная математика

14:41 

Шарики

wpoms.
Step by step ...


В одной сумке лежит `m` шариков, в другой их `n` (`m, n > 0`). Можно выполнять две разные операции:
a) Удалить равное количество шариков из обеих сумок;
b) Удвоить количество шариков в одной из сумок.
Всегда ли возможно опустошить обе сумки с помощью конечной последовательности операций a) и b)?
Операцию b) заменяют на
b') Утроить количество шаров в одной из сумок.
Всегда ли возможно опустошить обе сумки с помощью конечной последовательности операций a) и b')?



@темы: Дискретная математика

12:19 

помогите решить

соответствия между множествами C = {1,2,3,4,5} и D={5,6,7} таково что его график состоит из пар в которых первая компонента взята из множества С а вторая из D и больше первой компаненты. Постройте граф этого соответствия , график этого соответствия в прямоугольной системе координат. Постройте граф противоположного соответствия , график противоположного соответствия в прямоугольной системе координат.

@темы: Дискретная математика, Теория графов

21:41 

Trotil
На stepic.org открылся курс "дискретные структуры", посвящённый комбинаторике и теории графам. На курс можно записаться прямо сейчас. Первый модуль будет доступен еще неделю.

Курс интересен практической направленностью, постоянно возникают задачи со сложными структурами, свойства которых приходится анализировать самостоятельно. Рекомендую его всем, кто хочет о комбинаторике узнать чуть больше, чем это даётся в стандартном курсе теории вероятностей. Я два модуля прошёл.

Пример среднего по сложности задания:

читать дальше

@темы: Дискретная математика, Комбинаторика, Образование, Теория графов

00:47 

Раскраска

wpoms.
Step by step ...


Стороны выпуклого `(L + M + N)`-угольника раскрашены в три цвета: `L` сторон красным, `M` сторон желтым и `N` сторон синим. Выразите в виде неравенств необходимые и достаточные условия такой раскраски, при которой две смежные стороны не окрашены одним и тем же цветом.



@темы: Дискретная математика

22:22 

Помогите док-ть ассоциативность умножения по модулю 5!Срочно!Пожалуйста!

Помогите док-ть ассоциативность умножения по модулю 5!

Введем на полученном множестве N5(0,1,2,3,4,5) операцию умножения по модулю 5. Так как 5 – простое число, то выполняются все аксиомы группы, что легко проверяется. Так, замкнутость следует из того, что произведение чисел, меньших простого модуля, не кратна ему.

Ассоциативность легко доказывается при переходе от сравнения к равенствам. ??? как это расписать,помогите,пожалуйста! с чего начать, как обозначить,записать на математическом языке не понимаю.

+ к какой математической модели (моноид, полугруппа, группа, кольцо, область целостности, поле, тело) относятся следующие множества (U) с заданными операциями.

@темы: Дискретная математика

19:23 

Композиция бинарных отношений - помогите понять

Задали найти композицию бинарных отношений,а я никак не пойму что откуда брать.
R1(x, y) = {(x, y) | x^2 = y}
R2(x, y) = {(x, y) | x = y^2}

Нужно найти R1 * R2 и R2 * R1?
Думал будет так : R1*R2 = sqrt(x)=y^2
R2*R1 = x=y
но оказалось не верно

@темы: Бинарные отношения, Дискретная математика

21:06 

Найти коэффициент при x^6 в разложении многочлена

Найти коэффициент при x^6 в разложении многочлена
(1+2x^2-3x^4)^8

@темы: Высшая алгебра, Дискретная математика

01:46 

Представить отношение R другими возможными способами

На множестве М бинарное отношение R c МхМ задано характеристическим свойством. Представить отношение R другими возможными способами. Выяснить какими свойствами оно обладает.
M = {-1,0,1,2,3,4}, R = { (х;у)|х+у<4; х,у є М }

@темы: Дискретная математика, Высшая алгебра

18:58 

RLE-кодирование

Задача с дистанционной олимпиады olymp.ifmo.ru (тур уже завершен)
Условие

Решение.
Мне не очень понятно, что от меня хотели в ответе задачи.
Если бы в условии задачи было сказано: "Определите максимально возможное количество деталей одного типа в составе комплекта в изделии", то ответ 8192.
Если бы в условии задачи было сказано: "Определите максимально возможное количество деталей одного типа в составе изделия", то ответ 8192*6=49152.
А как понимать "Определите максимально возможное количество деталей одного типа в составе комплектов изделия"? Комбинация A8192 B1 A8192 B1 A8192 B1 A8192 B1 A8192 B1 A8192 B1 удовлетворяет условию задачи? Правильный ответ -8192 или 49152?

@темы: Дискретная математика

11:34 

Дискретка

Кайре Аш
ключник
Монотонность булевой функции. Какие наборы значений сравнимы, а какие нет? Гугл вообще не спасает.

@темы: Дискретная математика

14:20 

Дискретная математика, хелп! :C

Бинарные отношения.

Задание: найдите отношение, являющееся симметричным, антисимметричным и не рефлексивным одновременно или докажите, что такого отношения не существует.

По определению: если отношение симметрично, то для любого х из множества справедливо: xRy => yRx. Если отношение антисимметрично, то для любого x из множества выполняется: xRy & yRx => x=y. Тогда если существуют (a;b), принадлежащие множеству, то (b;a) также принадлежит множеству, и b=a. Т.е. пара (a;a) принадлежит множеству. Если же множество пустое, то оно удовлетворяет условиям симметричности и антисимметричности, но не удовлетворяет рефлексивности.

Есть предположение, что такому отношению удовлетворяет «A победил B в морской бой» над множеством людей на Земле. Из того, что A победил B и B победил A в одной партии, следует то, что A и B — один человек, который играл сам с собой (какой-нибудь странный человек, к примеру). С другой стороны, оно не рефлексивно, поскольку не все люди побеждали сами себя в морской бой (существуют люди, которые не знают об этой игре).

@темы: Бинарные отношения, Дискретная математика

15:46 

wpoms.
Step by step ...


1. В треугольнике ABC, AB > AC, продолжение высоты AD, где точка D лежит на BC, пересекает описанную окружность треугольника ABC `\omega` в точке P. Окружность, проходящая через точку P и касающаяся BC в точке D, пересекает `\omega` в точке Q отличной от P, при этом PQ = DQ. Докажите, что AD = BD - DC.

2. Найдите все пары целых чисел (m,n) таких, что `m^3-n^3=2mn+8`.

3. `b_1, b_2, ...` - последовательность положительных действительных чисел таких, что для всех натуральных `n \ge 1` выполняется условие
`b_{n+1}^2 \ge b_1^2/1^3 + b_2^2/2^3 + ... b_n^2/n^3`.
Покажите, что существует натуральное число M такое, что
`sum_{n=1}^M b_{n+1}/(b_1+b_2+...+b_n) > 2013/1013`.

4. В массиве 6x6,
2 0 1 0 2 0
0 2 0 1 2 0
1 0 2 0 2 0
0 1 0 2 2 0
1 1 1 1 2 0
0 0 0 0 0 0
можно выбрать подмассив размером k x k, 1 < k < 6, и добавить 1 ко всем его элементам. Возможно ли за конечное количество подобных операций добиться того, чтобы все элементы массива стали кратны 3?

5. Даны различные действительные x, у такие, что `(x^n-y^n)/(x-y)` является целым числом для четырех последовательных натуральных n. Докажите, что `(x^n-y^n)/(x-y)` является целым числом для всех натуральных n.



@темы: Планиметрия, Дискретная математика, Теория чисел

19:01 

теория множеств

Здравствуйте!
Помогите пожалуйста разобраться с задачей
K={M| |ML|=|MH|=4}
Не понимаю, что от меня требуется. Т.е. понятно что нужно найти множество М точек на плоскости заданных этим свойством, но свойство понять не могу.

@темы: Дискретная математика, Множества

17:27 

Понятия функциональной замкнутости и полноты

Здравствуйте. Объясните как решить:
Построить множество всех функций, зависящих от переменных `x_1`, `x_2` и принадлежащих замыканию множества `A`:
`A = {bar(x_1) vv x_2}`

@темы: Дискретная математика

23:29 

Машина Тьюринга

Может не совсем сюда, но мне раньше всегда здесь помогали.

Задача:
Даны 2 языка `L_1, L_2` определим `Delta` как `L_1 Delta L_2 =(L_2 \\ L_1) uuu (L_1 \\ L_2)` класс `C` замкнут если `L_1, L_2 in C => L_1 Delta L_2 in C`. Определить если есть замыкание для `P, NP, NP nnn coNP`


читать дальше

заранее спасибо.

@темы: Дискретная математика

21:10 

Принцип двойственности

С использованием принципа двойственности построить формулу, реализующую функцию, двойственную к функции `f`, и убедиться в том, что полученная формула эквивалентна формуле `g`:

`f=(xdownarrowy)oplus((x|y)downarrow(bar(x)~ywedgez))`, `g=xwedgebar(y)vvbar(x)wedgeyvvbar(y)wedgez`

@темы: Дискретная математика

Не решается алгебра/высшая математика?.. ПОМОЖЕМ!

главная