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

Нули и единицы

wpoms.
Step by step ...


Каждой последовательности, состоящей из $n$ нулей и $n$ единиц, ставится в соответствие число сегментов максимальной длины, состоящих из идущих подряд одинаковых цифр. (Например, в последовательности 00111001 есть 4 таких сегмента 00, 111, 00, 1.) Для данного $n$ мы суммируем числа, поставленные в соответствие всем таким последовательностям. Докажите, что полученное значение равно $(n+1)С_{2n}^{n}.$



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

22:13 

Алмазы

wpoms.
Step by step ...


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



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

23:38 

Язык и математики

wpoms.
Step by step ...


Девять математиков встретились на международной конференции и оказалось, что среди любых трёх из них по крайней мере двое говорят на одном языке. Пусть каждый математик может говорить не более чем на трёх языках. Докажите, что по крайней мере три математика могут говорить на одном языке.



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

08:53 

Один с сошкой, а семеро с ложкой

wpoms.
Step by step ...


В компании, управляемой несколькими директорами, есть сейф, закрываемый на шесть замков. У каждого директора есть три ключа, которыми он может открыть три разные замка. Каждый ключ может открыть ровно один замок. Нет двух директоров, ключи которых могут открыть одни и те же три замка, и никакие два директора не могут вместе открыть сейф. Сколько директоров работают в компании?



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

20:18 

Да будет свет

wpoms.
Step by step ...


В ряд стоят $n$ ламп, $n \geq 3,$ пронумерованные числами от 1 до $n.$ В начале все лампы, стоящие на нечетных местах, включены, а остальные выключены. За одну операцию можно одновременно изменить состояние трех стоящих рядом ламп (включенные выключить, выключенные включить).
(a) Докажите, что порядок выполнения операций, необходимых для достижения конечного состояния, не важен.
(b) Для каких $n$ можно добиться того, чтобы лампы на нечетных местах были выключены, а на четных --- включены?



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

00:46 

LABOR EST ETIAM IPSE VOLUPTAS

wpoms.
Step by step ...


Дана треугольная сетка размером $9 \times 9$. В верхнем узле находится колонна муравьев, а их муравейник --- в нижнем правом узле. Во всех остальных узлах сетки лежит по одному зерну. По пути в муравейник муравей собирает все встреченные зерна, а добравшись до муравейника, остается в нем. Какое наименьшее количество муравьев должно быть в колонне, если они хотят собрать все зерна, а двигаться могут только по сетке вправо или вниз или по диагонали вправо-вниз?





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

16:57 

Раскраска

wpoms.
Step by step ...


(a) Каждый квадрат шахматной доски размером `4 xx 7,` окрашен либо в черный цвет, либо в белый цвет. Докажите, что при любой такой раскраске доска должна содержать прямоугольник (образованный горизонтальными и вертикальными линиями доски, пример изображён на рисунке), чьи четыре угловых клетки имеют одинаковый цвет.



(b) Приведите пример черно-белой раскраски доски `4 xx 6,` в которой угловые клетки каждого прямоугольника (описанного выше) не имеют одинаковый цвет.



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

19:41 

Ожерелье

wpoms.
Step by step ...


Ожерелье содержит 2016 жемчужин, каждая из которых окрашена в один из цветов --- чёрный, зёленый или синий.
На каждом шаге мы заменяем одновременно каждую жемчужину новой, цвет которой определяется так: если у жемчужины оригинальные соседи были одного цвета, то новая жемчужина получает их цвет, если соседи были двух разных цветов, новая жемчужина выбирается третьего цвета.
(a) Есть ли такое ожерелье, которое может быть с помощью таких шагов преобразовано в ожерелье с синими жемчужинами, если вначале одна половина жемчужин была чёрной, а вторая половина --- зелёной?
(b) Есть ли такое ожерелье, которое может быть с помощью таких шагов преобразовано в ожерелье с синими жемчужинами, если вначале 1000 жемчужин были чёрными, а остальные --- зелёными?
(c) Возможно ли преобразовать ожерелье, в котором ровно две чёрные, соседние, жемчужины, а остальные 2014 --- синие, в ожерелье, в котором одна зелёная жемчужина и 2015 синих жемчужин?



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

00:01 

Вредные множества

wpoms.
Step by step ...


Последовательность `$(a_1, a_2, ldots , a_k)`, состоящая из попарно различных клеток шахматной доски `n times n`, называется циклом, если `k \geq 4` и клетки `a_i` и `a_{i+1}` имеют общую сторону для всех `i=1, 2, ldots, k`, где `a_{k+1} = a_1`. Подмножество `X`, состоящее из клеток доски, назовем вредным, если каждый цикл содержит по крайней мере одну клетку из `X`.
Найдите все действительные числа `C` такие, что для каждого целого числа `n \geq 2` на доске размером` n \times n` существует вредное подмножество, содержащее не более `C*n^2` клеток.



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

12:39 

Рататуй

wpoms.
Step by step ...


Гурман Жан сравнивал $n$ ресторанов, где $n$ --- положительное целое число. Каждая пара ресторанов сравнивалась по двум показателям: качеству еды и уровню обслуживания. В некоторых случаях Жан не мог определиться, какой из двух ресторанов лучше по какому-то одному показателю, но тогда он всегда выбирал лучший по другому показателю. Понятно, что если Жан узнал, что ресторан $A$ лучше ресторана $B$ по какому-то показателю, и ресторан $B$ лучше ресторана $C$ по этому же показателю, то он считает, что $A$ лучше $C$ по этому показателю. Докажите, что есть ресторан $R$ такой, что любой другой ресторан хуже чем $R$ хотя бы по одному показателю.



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

01:23 

Папа, мама, я - спортивная семья

wpoms.
Step by step ...


Папа, мама и сын проводят семейный турнир, играя в игру без ничьих, в каждой партии которой участвуют два игрока. Правила турнира:
(i) Самый слабый игрок выбирает первую пару игроков.
(ii) Победитель очередной партии проводит следующую партию против человека, не игравшего в предыдущей партии.
(iii) Первый человек, выигравший две партии, выигрывает турнир.
Папа - самый слабый игрок, сын - сильнейший. Предполагается, что вероятность любого игрока выиграть партию у другого игрока не меняется во время турнира. Докажите, что оптимальная стратегия папы для победы в турнире - сыграть первую партию с мамой.




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

18:51 

Простенький автомат

Здравствуйте,у меня снова вопрос,думаю совсем уж простой,но я не очень понимаю.
Есть автомат,заданный в виде диаграммы и задание к нему. И если возможно,поясните пожалуйста после запятой у нас идёт значение,выходящее из автомата,верно? какой в этом смысл,если следом у нас идёт следующий символ в цепочке,если таковой имеется.

Работа с автоматом задана с помощью диаграммы и выдает на выходе символ "*",всякий раз,когда во входном алфавите встречается цепочка символов.Определить,какие символы распознает автомат и записать принцип работы автомата с помощью совокупности четверок.

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

21:04 

Булевые функции

пожалуйста,помогите разобраться с приложенным вырезкой из указаний к работе,не пойму,каким образом мы получаем g1 и g2,возможно,что-то напутано в материалах? такое уже бывало с этим сборником.

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

21:23 

Поиграем

wpoms.
Step by step ...


На окружности отмечены $N$ точек, которые являются вершинами правильного $N$-угольника. Игроки $A$ и $B$ играют в следующую игру: Они по очереди проводят хорды, соединяющие пару отмеченных точек, так чтобы хорды не пересекались (за исключением их концов). Выигрывает тот игрок, который первым получает треугольник. Какой игрок может выиграть, если $A$ начинает игру и a) $N = 14;$ b) $N = 15?$



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

21:27 

Поехали в Ростов-на-Дону, а оказались в Ростове Великом

wpoms.
Step by step ...


Шесть туристов совершили несколько поездок в шесть стран, во время одной поездки каждый турист посещал только одну страну. Оказалось, что если выбрать любые три из этих стран, а также любых трех туристов, то, по крайней мере, один из них был в одной из этих стран. Чему равно наименьшее возможное общее количество поездок?



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

21:53 

Шарики

wpoms.
Step by step ...


Каждый из шаров, лежащих в коробке, окрашен в один из $N$ цветов и на каждом шаре написано натуральное число не превосходящее $N.$ Известно, что каждый из $N$ цветов использован не менее одного раза и каждое натуральное число, не превосходящее $N,$ написано не менее одного раза. При каких значениях $N$ в коробке можно будет найти $N$ окрашенных в разные цвета шаров, на которых будут $N$ разных чисел?



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

19:49 

Тестирование

wpoms.
Step by step ...


Провели 92 теста. В каждом тесте высшую оценку получили ровно 10 проверяемых, и в любых двух тестах ровно один проверяемый получил две высшие оценки. Можно ли утверждать, что есть проверяемый, который получил высшую оценку в 92 тестах?



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

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. Прав ли я?

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

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

главная