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

"А какого он был цвета?" - "Зелёного" - "Мой любимый цвет"(с)

wpoms.
Step by step ...


Бизнесмен подарил детям в детском саду 2000 воздушных шариков. Шарики были 20 разных цветов, по 100 каждого цвета. Директор детского сада раздала каждому из 100 детей, посещающих сад, по 20 шариков, при этом она не обращала внимание на их цвет. Дети захотели поменяться шариками так, чтобы у каждого из них были шарики всех 20 цветов. Директор разрешила любой паре детей меняться парой шариков (когда каждый из них получает шарик другого), но только при условии, что каждый из пары при обмене получает шарик того цвета, которого у него не было до обмена.
Определите, всегда ли, вне зависимости от начального распределения шариков, дети смогут, после конечного количества обменов, добиться желаемого?



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

23:37 

Игра

wpoms.
Step by step ...


Августин и Лукас по очереди помечают квадраты на доске размером `101xx101` квадратов. Августин начинает игру. Нельзя помечать квадрат, если в том же ряду или столбце уже помечены два квадрата. Тот, кто не может пометить квадрат, проигрывает. Кто имеет выигрышную стратегию?



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

10:47 

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

Здравствуйте, уважаемые члены математического сообщества. Я сейчас изучаю дискретную математику по учебному пособию для вузов. Авторы: И. Л. Ерош, М. Б. Сергеев, Н. В. Соловьев. Там есть задача по теории множеств, условие которой я не могу сказать, что понимаю. Условие следующее:
"Сколько разных слов длины, не превышающей 5, может быть подано на вход цифрового устройства, если входной алфавит состоит из двух букв {0, 1}? Слово длины 0 – одно, длины 1 – два (0 и 1), длины 2 – четыре, длины 3 – восемь, длины 4 – шестнадцать, длины 5 – тридцать два. Если к этой сумме прибавить 1, получим 64. Всего на вход устройства может быть подано (2 в степени 6 )–1 разных слов. Найдите количество разных слов длины, не превышающей 7, 8, 9, 10, n."

Как понял я, то под словом подразумевается множество букв. И поскольку по одной из теорем количество подмножеств равно 2 в степени мощности множества, ответы на задачу будут 2 в степени 7,8, 9, 10, n. Прав ли я?

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

22:36 

Доска

wpoms.
Step by step ...


Есть доска с $n$ рядами и 12 колонками. В каждой клетке написаны 1 или 0. Доска обладает такими свойствами:
A) Любые два ряда различны.
B) В каждом ряду есть ровно 4 клетки с 1.
C) Для любых 3 рядов есть колонка, на пересечении которой с этими рядами стоят три 0.
Найдите наибольшее $n,$ для которого существует доска с указанными выше свойствами.



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

13:36 

Про коробки

wpoms.
Step by step ...


Имеются 100 бесконечно вместительных коробок, в каждой из которых лежит по одной фишке. Бруно может добавить в каждую коробку так много фишек, сколько пожелает. После этого начинает выполняться последовательность шагов.
На шаге 1 в каждую коробку добавляется по одной фишке.
На шаге 2 фишка добавляется в те коробки, в которых содержится чётное количество фишек.
На шаге 3 фишка добавляется в те коробки, количество фишек в которых делится на 3.
На шаге 4 фишка добавляется в те коробки, количество фишек в которых делится на 4.
И так далее.
Целью Бруно было добиться того, чтобы на каждом шаге можно было найти две коробки с разным количеством фишек.
Определите, может ли Бруно достичь своей цели при каком-либо добавлении фишек до начала выполнения описанной последовательности шагов.




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

18:00 

Игра

wpoms.
Step by step ...


Анна и Берта играют в игру, в которой нужно снимать камешки со стола.
Анна ходит первой. Пусть перед очередным ходом на столе лежат `n \geq 1` камешков, тогда делающий ход игрок снимает со стола `k` камешков, где `k \geq 1` либо четное и `k \leq \frac{n}{2}`, либо нечетное и `\frac{n}{2} \leq k \leq n`. Игрок выигрывает, если своим ходом она снимает со стола последний камень.
Найдите наименьшее `N \geq 100000` такое, что Берта может одержать победу, если на столе лежат ровно `N` камешков в начале игры.



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

20:01 

Доказать, что четверка Штейнера порядка 10 единственна

yoggik_wow
And I'm feeling good.
Также спрашивала тут: www.cyberforum.ru/discrete-mathematics/thread19...
Здравствуйте. Никак не могу уцепиться и понять, с чего начать.
Нужно доказать, что четверка Штейнера порядка 10 единственна с точностью до изоморфизма.
мысли

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

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) Показать, что самодополнительный граф связен

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

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

главная