ЗАДАЧИ
problems.ru
О проекте | Об авторах | Справочник
Каталог по темам | по источникам |
К задаче N

Проект МЦНМО
при участии
школы 57
Фильтр
Сложность с по   Класс с по  
Задачи

Страница: << 2 3 4 5 6 7 8 >> [Всего задач: 36]      



Задача 109782

Темы:   [ Деревья ]
[ Полуинварианты ]
[ Перестройки ]
[ Неравенство Коши ]
[ Алгебраические неравенства (прочее) ]
Сложность: 5-
Классы: 9,10,11

Дано дерево с n вершинами,  n ≥ 2.  В его вершинах расставлены числа x1, x2, xn, а на каждом ребре записано произведение чисел, стоящих в концах этого ребра. Обозначим через S сумму чисел на всех рёбрах. Докажите, что  

Прислать комментарий     Решение

Задача 109740

Темы:   [ Деревья ]
[ Наименьшее или наибольшее расстояние (длина) ]
[ Связность и разложение на связные компоненты ]
Сложность: 5
Классы: 9,10,11

В стране несколько городов, некоторые пары городов соединены дорогами, причём между каждыми двумя городами существует единственный несамопересекающийся путь по дорогам. Известно, что в стране ровно 100 городов, из которых выходит по одной дороге. Докажите, что можно построить 50 новых дорог так, что после этого даже при закрытии любой дороги можно будет из каждого города попасть в любой другой.

Прислать комментарий     Решение

Задача 66727

Темы:   [ Деревья ]
[ Ориентированные графы ]
[ Индукция (прочее) ]
[ Теория игр (прочее) ]
Сложность: 6
Классы: 8,9,10,11

Автор: Дидин М.

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

а) в простом государстве Петя может играть так, чтобы не проиграть, как бы ни играл Вася;

б) в сложном государстве Вася может гарантировать себе победу, как бы ни играл Петя.
Прислать комментарий     Решение


Задача 31098

Темы:   [ Связность и разложение на связные компоненты ]
[ Деревья ]
Сложность: 3
Классы: 6,7,8

Доказать, что
  а) из связного графа можно выкинуть несколько рёбер так, чтобы осталось дерево;
  б) в дереве с n вершинами ровно  n – 1  ребро;
  в) в дереве не меньше двух висячих вершин;
  г) в связном графа из n вершин не меньше  n – 1  ребра;
  д) если в связном графе n вершин и  n – 1  ребро, то он – дерево.

Прислать комментарий     Решение

Задача 98105

Темы:   [ Отношение порядка ]
[ Деревья ]
[ Принцип крайнего (прочее) ]
Сложность: 3
Классы: 7,8

В некотором королевстве было 32 рыцаря. Некоторые из них были вассалами других (вассал может иметь только одного сюзерена, причём сюзерен всегда богаче своего вассала). Рыцарь, имевший не менее четырёх вассалов, носил титул барона. Какое наибольшее число баронов могло быть при этих условиях?
(В королевстве действовал закон: "вассал моего вассала – не мой вассал".)

Прислать комментарий     Решение

Страница: << 2 3 4 5 6 7 8 >> [Всего задач: 36]      



© 2004-... МЦНМО (о копирайте)
Пишите нам

Проект осуществляется при поддержке Департамента образования г.Москвы и ФЦП "Кадры" .