• ↓
  • ↑
  • ⇑
 
Записи с темой: дискретная математика (список заголовков)
12:05 

Выборы

wpoms.
Step by step ...


В Нечётненской начальной школе нечетное число классов. Каждый класс содержит нечетное число учеников. Один ученик из каждого класса будет выбран для формирования школьного совета. Докажите, что следующие два утверждения логически эквивалентны.
а) Способов сформировать школьный совет, который включает в себя нечетное число мальчиков больше, чем способов формирования школьного совета, который включает в себя нечетное число девочек.
б) Имеется нечетное число классов, в которых мальчиков больше, чем девочек.



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

18:32 

Новогодняя гирлянда

wpoms.
Step by step ...


Имеются n выключенных лампочек, пронумерованных числами от `1` до `n`. С ними можно выполнять одну из следующих операций:
• изменить состояние лампочки `1`;
• изменить состояние лампочки `2`, если первая лампочка горит;
• изменить состояние лампочки с номером `k` (`k > 2`), если лампочка с номером `k-1` горит и все лампочки с номерами `1, ... , k-2` выключены.
Покажите, что возможно, после определенного количества операций, добиться того, чтобы горела только лампочка с номером `n`.



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

00:42 

Комбинаторная задача.

Прошу помощи в решении задачи. Буду очень рад, если поделитесь материалом, по которому можно было бы разобрать решение подобных задач (ибо грядёт зачёт, потому понимание крайне важно).

Определить число троек слов (a,b,c) длины 12 в латинском алфавите, таких что:
a. два слова имеют 4 общих буквы и 2 слова имеют 3 позиции, символы в которых совпадают;
b. два слова имеют 3 общих буквы и 2 слова имеют 4 позиции, символы в которых совпадают;

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

18:45 

Граф состояний

привет, я у тебя самый лучший
Можно удалить, уже сама разобралась.

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

13:12 

Давай пожмем друг другу руки - И в дальний путь, на долгие года.

wpoms.
Step by step ...


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

(b) Если, дополнительно, в группе есть три человека, каждый из которых знаком с двумя другими, то чему равно наибольшее количество людей, которые могли принять участие в вечеринке?



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

20:56 

Прямые на шахматной доске

wpoms.
Step by step ...


Докажите, что если p - простое число, то на шахматной доске размером pxp можно выбрать p клеток так, что никакие три из них не лежат на одной прямой. На рисунке показан один из возможных выборов клеток для p=3.




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

01:13 

Десерт

wpoms.
Step by step ...


Ежедневно более чем половина жителей города Эвора ест на десерт sericaia. Покажите, что есть группа из 10 эворийцев, таких что за последние 2010 дней каждый день по крайней мере один из них ел на десерт sericaia.

Sericá (или Sericaia) является традиционным португальским десертом из яиц, сахара, молока и корицы. Обычно подается с сахарными сливами.




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

21:03 

Правило Кондорсе

Добрый день. Вопрос про правило Кондорсе. Считаем следующим образом: попарно сравниваем кандидатов, то есть сколько голосующих предпочитает одного кандидата другому. После строится мажоритарный граф.
Такой вопрос: если мы не можем сказать кто лучше, то в графе это ребро отсутствует вовсе?
Отсюда следует вывод, что это правило не строит отношение полного порядка (так как некоторые несравнимы получаются), верно?

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

19:47 

Сокровище

wpoms.
Step by step ...


Два игрока играют в следующую игру на круглой доске с 2009 домами. Игроки поочередно помещают в пустой дом одну из трех фишек, они называются исследователь (E), ловушка (A) и камень (P). Назовем сокровищем последовательность из трех домов, такую что в первом (в любом направлении) находится исследователь и в среднем не находится ловушка. Например, последовательность PAE не является сокровищем, но последовательность AEE сокровищем является.

Первый игрок, который образует сокровище выигрывает. Могут ли игроки обеспечить себе победу? И если да, то кто из них?





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

20:08 

Рекуррентная последовательность

Муссон
[Солнце не беспокоится ни о чем. И цветы просто распускаются]
Здравствуйте.
Нужно найти общую формулу для рекуррентной последовательности: 1, 2, 3, 4, 1, 2, 3, 4, ...
Решение в общем виде нашла, но при проверке для нечетных n вылезает i, упорно-долго пересчитывала коэффициенты, не могу найти ошибку: (

a(n+4) = a(n)

a(n) = C1 + C2*(-1)^n + C3*i^n + C4*(-i)^n

a(n) = (5 + 2*i)/2 + ((-1 - 2*i)*(-1)^n)/2 + ((i - 1)*i^n)/2 + ((-i - 1)*(-i)^n)/2

Решение прикрепляю картинкой:



Надеюсь на тык в ошибку, упорно ее не вижу х.х

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

13:48 

Теория алгоритмов

1.Доказать, что если множества А и В рекурсивно перечислимы, то множества А пересечение В и А объединение В рекурсивно перечислимы. Вот с рекурсивными множествами понятно, нужно построить характеристическую функцию являющуюся рекурсивной. А вот с рекурсивно перечислимым не знаю с чего начать
2. Множества А и В отличаются конечным числом элементов, доказать, что: если А рекурсивно перечислимо, то и В рекурсивно перечислимо

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

18:25 

построить машину Тьюринга

Построить для функции f(x,y)=x, если x>y; y, если x<y; 0, если x=y
какая идея построения?

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

13:30 

Доказательство нескольких утверждений по графам

Никак не получается, понять как грамотно доказать некоторые утверждения, например:

1) Доказать, что если в графе (без петель и кратных ребер) более 4 вершин, то либо в самом графе, либо в его дополнении содержится цикл.
попытки доказать

2) Если v - разделяющая вершина графа, то она не является разделяющей в его дополнении.

домыслы

3) Показать, что самодополнительный граф связен

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

14:11 

Задания по теории графов

Вот не приходят идеи мне к этим 2 задачкам по теории графов:
1) Доказать, что в мультиграфе всякий замкнутый маршрут нечетной длины l>=3 содержит простой цикл. Доказать, что это несправедливо для маршрутов четной длины.
мои мысли
2) Пусть p(G) - наименьшая из степеней вершин графа G, не имеющего петель и кратных ребер и содержащего n вершин (n >= 2)
Доказать, что если p(G) >= (n-1)/2, то граф связен.
очевидное рассуждение

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

10:40 

Задача из теории множеств

Доказать, что если отношения R1 и R2 рефлексивны, то рефлексивны отношения R1 объединение R2, R1 пересечение R2, R1 * R2, (R1)^-1

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

23:56 

Перестановки

Помогите пожалуйста решить задачу
сколькими способами можно переставить буквы слова "баллада", чтобы две буквы "а" не шли рядом?
у меня в решении поучается всего перестановок 7!/3!/2!
берем две буквы а как одну 6!/2!/2!
берем три буквы а как одну 5!/2!
Итого 7!/3!/2!-6!/2!/2!+5!/2!=300

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

14:36 

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

Добрый вечер!
Подскажите, пожалуйста, как проверить свойства?

Каким свойством обладает отношение R, заданное на парах положительных чисел.
`(a;b)R(c;d) <=> a^2-d^2=b^2-c^2`

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

11:43 

Доказать или опровергнуть формулу (A\B)\C=(A\C)\(B\C).

Подскажите, пожалуйста, как доказать или опровергнуть формулу (A\B)\C=(A\C)\(B\C).
Кроме диаграмм эйлера-Венна ничего в голову не приходит(( будут ли диаграммы доказательством?

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

15:09 

Теоремы Силова

Здравствуйте, проблем с теорема Силова, а точнее с их доказательствами
не могла бы вы подсказать доказательства теорем простым язык чтоле или привести свое:)
смотрел в книге Каргаполова, Мерзлякова
ну очень там сложно, в особенности теорема о существовании и сопряженности
спасибо всем)

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

14:37 

Максимальный поток, минимальный разрез в сетевом графе.

adolescence
Есть задача: Найти максимальный поток, минимальный разрез. Должна быть таблица с "достижимыми" вершинами на каждом шаге. В ответе должна быть величина потока и ребра, входящие в разрез.

Помогите с любым простейшим примером, что бы понимать, куда двигаться вообще. В инете подробно разъясняется в основном алгоритм Форда-Фалкерсона, но с его помощью легко найти только максимальный поток, а для минимального разреза нужно расставлять пометки на вершинах...

Заранее спасибо за помощь)

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

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

главная