Всего: 65 1–20 | 21–40 | 41–60 | 61–65
Добавить в вариант
Четыре кротовые норы A, B, C, D последовательно соединены тремя тоннелями. Каждую минуту крот по тоннелю перебегает в одну из соседних нор. Сколькими способами крот может добраться из норы A в C за 26 минут?
и 
Отсюда 
Четыре кротовые норы A, B, C, D последовательно соединены тремя тоннелями.Каждую минуту крот по тоннелю перебегает в одну из соседних нор. Сколькими способами крот может добраться из норы A в C за 24 минут?
Четыре кротовые норы A, B, C, D последовательно соединены тремя тоннелями. Каждую минуту крот по тоннелю перебегает в одну из соседних нор. Сколькими способами крот может добраться из норы A в C за 22 минут?
Четыре кротовые норы A, B, C, D последовательно соединены тремя тоннелями. Каждую минуту крот по тоннелю перебегает в одну из соседних нор. Сколькими способами крот может добраться из норы A в C за 20 минут?
Четыре кротовые норы A, B, C, D последовательно соединены тремя тоннелями. Каждую минуту крот по тоннелю перебегает в одну из соседних нор. Сколькими способами крот может добраться из норы A в C за 18 минут?
Четыре кротовые норы A, B, C, D последовательно соединены тремя тоннелями. Каждую минуту крот по тоннелю перебегает в одну из соседних нор. Сколькими способами крот может добраться из норы A в C за 16 минут?
В альфацентаврианском алфавите S звонких букв, H глухих и N нейтральных. Словом называется последовательность различных букв такая, что в ней
а) первая и последняя буквы имеют разную звонкость (т. е. не являются обе звонкими, обе глухими или обе нейтральными);
б) есть хотя бы одна звонкая буква.
Стихотворением называется последовательность различных слов такая, что каждое последующее слово начинается с той буквы, на которую закончилось предыдущее слово. Сколько слов в самом длинном стихотворении, состоящем только из двухбуквенных слов, если S = 6, H = 3, N = 5?
где H — любая из глухих букв, S — любая из звонких букв. Всего слов указанных видов: 18, 18, 30, 30, соответственно. То есть в двухбуквенном стихотворении не может быть более 96 слов. Теперь покажем, что эта оценка достигается.
вершины второй — звонким 
вершины третьей — нейтральным 
таким образом, ориентированные ребра графа — двухбуквенные слова. 
слов (осталось неиспользованным только слово S6H1, но оно нам потребуется для «замыкания цикла»). Теперь, аналогично, начиная с буквы 
на которой мы сейчас остановились, перечислим слова третьего и четвертого типов: 
Перечислить все различные (неизоморфные) деревья (связные графы без циклов) на 5 вершинах. Изоморфными называются графы, которые перемещением (без совмещения) вершин можно привести к одному виду. Связным называется граф, у которого любые две вершины можно соединить путем из ребер графа. Цикл — замкнутый путь без повторного прохода по ребрам.
Если суммировать число рёбер, входящих в каждую вершину (степени вершин), то получится число вдвое больше числа рёбер, так как каждое ребро соединяет две вершины: 
Постройте плоский граф (рёбра плоского графа не пересекаются во внутренних точках рёбер), в двух вершинах которого сходится по 5 рёбер, а в остальных вершинах по 4 рёбра. Постарайтесь, чтобы вершин было как можно меньше. (Вершины графа можно перемещать).
—
вершинах. В предыдущем примере формула выглядит так: 
В нашей задаче из корня выходит три ветви, каждая из которых уже является бинарным деревом, поэтому нужно рассмотреть распределение листьев между тремя ветками и далее уже применить формулу для чисел Каталана: 
Посмотрите на картинку. Вершины графа слева изображают школьников одного класса. Вершины справа — предметы, в которых эти школьники показали хорошую осведомленность. Для отправки на олимпиаду нужно выбрать команду из как можно меньшего числа участников, чтобы в ней был специалист по каждому предмету.
Для выбора участников кликните на соответствующие вершины.
Шесть школьников разбились на две команды, после чего каждый участник одной команды сыграл с каждым участником другой команды партию в настольный теннис. Вершины графа на рисунке изображают школьников, рёбра — сыгранные партии.
На рисунке вы можете видеть часть схемы турнира: всех участников и некоторые сыгранные партии. Восстановите остальные партии.
Некоторое количество (n) школьников разбились на две команды, после чего каждый участник одной команды сыграл с каждым участником другой команды партию в настольный теннис. Вершины графа на рисунке изображают школьников, рёбра — сыгранные партии.
На рисунке вы можете видеть часть схемы турнира для n = 6: всех участников и некоторые сыгранные партии. В общем случае данная часть схемы выглядит так же: цепочка из n человек, где каждый, кроме последнего, сыграл со следующим и каждый кроме первого сыграл с предыдущим.
Какое количество рёбер (в зависимости от n) нужно добавить в граф, чтобы восстановить схему турнира полностью? Не забудьте обосновать свой ответ.
человек, в случае нечётного 
человек, другую из 
рёбер, значит, добавить необходимо 
ребро, что можно также представить как 
В случае нечётного n итоговое количество рёбер это 
добавить необходимо 
ребро, что также можно представить как 
при нечетном n: 
В некоторой компании у каждого человека по 3 друга. Каждый из них является сторонником одной из двух политических партий: красной или синей. Каждый день каждый человек общается со всеми своими друзьями. За ночь он обдумывает полученную от них информацию, и если оказывается, что большинство его друзей являются сторонниками противоположной политической партии, к утру человек меняет свои взгляды.
Докажите, что для любой компании существует исходное распределение политических взглядов при котором в дальнейшем стабилизации политических взглядов не происходит.
Постройте граф, удовлетворяющий следующим условиям:
1) Из каждой вершины выходит ровно 4 ребра
2) В графе нет четырёх вершин, каждые две из которых были бы соединены между собой
3) Граф нельзя покрасить в три цвета "правильно", то есть так, чтобы любые две вершины одного цвета были не соединены.
Графом называется рисунок, состоящий из точек (вершин), соединённых отрезками (рёбрами). При этом нам не важно, как именно нарисован граф, важно только, какие вершины с какими соединены.
а) Учитель нарисовал на доске граф. Три ученика перерисовали его в тетрадки (возможно, не сохранив расположение вершин), при этом каждый из них потерял по одной вершине (каждый — свою) и все выходящие из неё рёбра.
Оказалось, что по рисункам ребят нельзя восстановить нарисованный учителем граф. Как такое могло быть? Постройте пример трёх рисунков учеников и двух возможных рисунков учителя.
б) Верно ли, что для любого n можно придумать набор из n таких рисунков, по которым исходный граф восстанавливается неоднозначно (то есть существует два и более варианта)?
копии левого и второй граф, состоящий, наоборот, из k копий левого графа и 
Графом называется рисунок, состоящий из точек (вершин), соединённых отрезками (рёбрами). При этом нам не важно, как именно нарисован граф, важно только, какие вершины как соединены.
Подграф, который получается из графа удалением одной вершины, назовём картой, а набор всех карт графа — колодой.
В задаче отборочного тура мы уже доказывали, что по колоде можно восстановить общее количество рёбер графа. Также легко доказать, что можно установить степени всех вершин (количество выходящих из неё рёбер): степень вершины, которой не хватает на карте — это в точности количество отсутствующих на ней рёбер.
Докажите, что граф, степени всех вершин которого чётны, однозначно восстанавливается по своей колоде.
Семь кротовых нор A, B, C, D, E, F, G последовательно соединены шестью тоннелями. Каждую минуту крот по тоннелю перебегает в одну из соседних нор. Сколькими способами крот может добраться из норы D в B за 10 минут?
из соображений симметрии. Заметим, что выполняются равенства 
