Тема 19. Задачи на теорию чисел

19.23 Графы: вершины, ребра

Вспоминай формулы по каждой теме
Решай новые задачи каждый день
Вдумчиво разбирай решения
ШКОЛКОВО.
Готовиться с нами - ЛЕГКО!
Подтемы раздела задачи на теорию чисел
Решаем задачи

Ошибка.
Попробуйте повторить позже

Задача 1#60156

В стране 100 городов, занумерованных от 1 до 100. Дума приняла закон, по которому из каждого города с номером n  должно выходить количество дорог, равное n  -ному простому числу. Можно ли выполнить такой закон?

Показать ответ и решение

Есть только одно четное простое число, а именно 2. Все остальные простые числа нечетны, поэтому при таком условии только из одного города выходит четное количество дорог, а из остальных 99 — нечетное. Итого получается нечетное количество городов, из которых выходит нечетное количество дорог, чего быть не может.

Ответ: Нет, нельзя

Ошибка.
Попробуйте повторить позже

Задача 2#60157

В стране 96 городов, из которых 24 — «областные». Некоторые пары городов соединены между собой дорогами (но не более чем одной), причём любой путь по дорогам между двумя обычными городами, если он есть, проходит хотя бы через один «областной» город. Какое наибольшее количество дорог могло быть в этой стране?

Показать ответ и решение

Очевидно, что обычные города не соединены дорогами, иначе бы существовал путь не проходящий через областной город. Значит, максимальное число дорог в том случае, когда каждый обычный город соединен с каждым областным, и все областные соединены между собой. Нетрудно убедиться, что ответ в таком случае будет равен

24⋅ 23 +(96− 24)⋅24= 276+ 1728 =2004.
    2
Ответ: 2004

Ошибка.
Попробуйте повторить позже

Задача 3#60158

На спартакиаде проводились соревнования по пяти видам спорта. Каждый из 30 семиклассников принял участие в соревнованиях либо по одному, либо по трём видам спорта, а в каждом из видов число принимавших участие было 15 или 25. Докажите, что такого быть не могло.

Показать ответ и решение

Рассмотрим граф, в котором вершинами будут семиклассники и виды спорта, а ребра проведены от семиклассников к тем видам спорта, в которых они участвовали. Так как от каждого из 30 семиклассников выходит нечетное количество ребер, то всего ребер в графе четное количество. С другой стороны, если в каждом виде спорта также участвовало нечетное количество спортсменов, но видов спорта было 5. Поэтому количество ребер, выходящих от вершин-видов спорта нечетное количество. Итак, ребер в графе одновременно и четно, и нечетно, а такого быть не могло.

Ответ: Задача на доказательство

Ошибка.
Попробуйте повторить позже

Задача 4#60159

Из полного графа на 100 вершинах выкинули 98 ребер. Мог ли получиться несвязный граф?

Показать ответ и решение

Предположим, что полученный граф оказался несвязным. Тогда его можно мысленно разделить на два подграфа, между которыми нет ребер (ни одна вершина первого подграфа не связана ни с какой вершиной второго подграфа). Обозначим количество вершин в первом подграфе за n.  Тогда было выкинуто по крайней мере n(100 − n)  рёбер, соединявших вершины этого подграфа с вершинами другого подграфа. Но

n(100− n)= 502− (n− 50)2 ≥ 502− 492 = 1⋅99 >98.

Противоречие. Значит, свзяный граф получиться не мог.

Ответ: Нет

Ошибка.
Попробуйте повторить позже

Задача 5#60160

Можно ли придумать пять таких слов, чтобы каждое имело хотя бы одну общую букву ровно с тремя другими?

Показать ответ и решение

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

Ответ: Нет, нельзя
Рулетка
Вы можете получить скидку в рулетке!