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

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

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



Задача 30794

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

В стране 100 городов, некоторые из которых соединены авиалиниями. Известно, что от каждого города можно долететь до любого другого (возможно, с пересадками). Докажите, что можно побывать во всех городах, совершив не более  а) 198 перёлетов;  б) 196 перелётов.

Решение

  б) Рассмотрим соответствующий граф и выделим из него максимальное дерево (см. задачу 30789 а).
  Докажем по индукции, что в дереве с n вершинами  (n > 2)  существует обходящий все вершины маршрут длины не более  2n – 4.  База  (n = 3)  очевидна.
  Шаг индукции. Рассмотрим висячую вершину А (см. задачу 30786) и удалим её и выходящее из неё ребро АВ. По предположению индукции в оставшемся дереве есть обходящий его маршрут длины  2n – 6.  Вставив в него кусок ВАВ получим маршрут длины  2n – 4,  обходящий исходное дерево.

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

Задача 98365

Темы:   [ Деревья ]
[ Раскраски ]
[ Куб ]
[ Доказательство от противного ]
[ Перебор случаев ]
Сложность: 4+
Классы: 9,10

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

Решение

  Допустим, что существуют такая раскраска и такой способ перекатывания, о которых идёт речь в условии. Рассмотрим все общие стороны соседних клеток шахматной доски. Те из них, через которые кубик не перекатывался, закрасим красным цветом. Поскольку кубик побывал на всех клетках доски, красная фигура не разделяет доску на части. Значит, она не содержит циклов, то есть является объединением нескольких деревьев. Рассмотрим одно из этих деревьев. Оно, как известно, имеет хотя бы два листа (лист – это вершина, из которой выходит только один отрезок). Если бы эти два листа принадлежали границе доски, то красные отрезки делили бы доску на части. Значит, существует лист A, не лежащий на границе доски. Кубик обязан перекатиться через все три не красных отрезка, которые выходят из точки A. Это значит, что кубик должен "обойти" точку A, как показано на рисунке (красный отрезок изображён жирной линией). При этом обходе с клетками, граничащими по выходящему из точки A красному отрезку, соприкасается одна и та же грань кубика. Значит, эти клетки должны быть одного цвета, что противоречит шахматной раскраске.

Ответ

Нельзя.

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

Задача 109782

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

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

Решение

  Рассмотрим ребро l, соединяющее вершины с числами xi и xj. Обозначим через ki(l) число вершин, из которых нельзя пройти в вершину xi при удалении ребра l.
  Ясно, что   1 ≤ ki(l), kj(l) ≤ n – 1,  ki(l) + kj(l) = n.  Кроме того, для каждого i сумма     равна  n – 1  (сумма берётся по всем рёбрам l, выходящим из xi), так как из вершины xi можно пройти по рёбрам дерева в каждую из оставшихся  n – 1  вершин единственным несамопересекающимся путем.
  Согласно неравенству Коши для данного ребра l получим  
  Последнее неравенство верно, так как  ki(l)kj(l) = ¼ ((ki(l) + kj(l))² – (ki(l) – kj(l))² ≥ ¼ (n² – ((n – 1) – 1)²) = n – 1.
  Сложив неравенства (*) по всем рёбрам, получим требуемое неравенство.

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

Задача 109740

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

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

Решение

  Рассмотрим граф, вершины которого соответствуют городам, а рёбра – дорогам. В этом графе между каждыми двумя вершинами есть единственный путь, следовательно, в нем нет циклов (дерево). По условию, в этом графе есть 100 вершин, из которых выходит ровно одно ребро (висячие вершины) – пусть это вершины A1, A2, ..., A100.
  Для каждой пары висячих вершин Ai и Aj существует единственный путь между ними, назовём количество рёбер на этом пути расстоянием между этими вершинами и будем обозначать через  d(Ai, Aj).
  Из конечности числа способов разбить эти 100 вершин на 50 пар следует, что при одном из способов достигается максимум суммы расстояний между вершинами в парах. Соединим пары вершин при этом разбиении 50 новыми рёбрами (остальные рёбра будем называть старыми). Мы докажем, что после этого даже при удалении любого ребра сохраняется связность графа.
  Предположим противное, пусть при удалении ребра между вершинами B и C граф распался на две компоненты. Ясно, что удалённое ребро было старым, а вершины B и C принадлежат разным компонентам. В каждой части должна быть вершина, из которой выходит ровно одно старое ребро, а каждое новое ребро соединяет две вершины из одной части. Но тогда в одной из частей должно быть новое ребро, соединяющее вершины Ai и Aj, а в другой – соединяющее вершины Ak и Am. Пути l и L, соединяющие соотвественно Ai с Ak и Aj с Am, должны содержать ребро BC. Следовательно, путь из Ai в Aj состоит из участка пути l, соединяющего Ai с B, и участка пути L, соединяющего B с Aj. Аналогично путь из Ak в Am проходит через точку C. Таким образом,  d(Ai, Aj) + d(Ak, Am) = d(Ai, Ak) + d(Aj, Am) – 2,  что противоречит максимальности суммы расстояний в выбранных парах.

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

Задача 31098

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

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

Решение

  а) Если граф – не дерево, то в нём есть простой цикл. Любое ребро из этого цикла можно выкинуть без нарушения связности. Этот процесс остановится, когда граф станет деревом.

  б) У дерева есть висячая вершина (см. задачу 30786). Удалим её вместе с ребром, которое из нее выходит. Оставшийся граф также является деревом. Поэтому у него есть висячая вершина, которую мы также удалим вместе с выходящим из нее ребром. Проделав эту операцию  n – 1  раз, мы получим граф, состоящий из одной вершины (в котором, конечно, нет рёбер). Поскольку каждый раз удалялось ровно одно ребро, то сначала их было  n – 1.

  в) Выйдем из висячей вершины и пойдём по графу как в задаче 30786. Так же как и там этот путь закончится в другой висячей вершине.

  г) Удалим из графа несколько вершин, превратив его в дерево. В полученном дереве  n – 1  вершина, а в иcходном – не меньше.

  д) Если это не так, то, превратив его в дерево, мы получим противоречие с п. б).

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

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



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

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