Физтех 2024, 9 класс, задача 6

Сложная
Комбинаторика
Источник:
Олимпиаде школьников «Физтех», Заключительный этап, 2024, 9 класс

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

Войдите, чтобы проверять ответы

Ответ. .

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

Пусть - количество висячих вершин. Найдем количество рёбер. С одной стороны, оно равно половине от суммы степеней вершин, то есть . С другой стороны, количество рёбер в дереве на меньше количества вершин. Так как вершин , то рёбер .

Получаем уравнение , откуда находим, что . Значит, в дереве вершин.

Похожие задачи

Физтех 2022, 10 класс, задача 7

(5 баллов) Функция f определена на множестве положительных рациональных чисел. Известно, что для любых чисел a и b из этого множества выполнено равенство f(ab)=f(a)+f(b), и при этом f(p)=[p/2] для любого простого числа p ([x] обозначает наибольшее целое число, не превосходящее x). Найдите количество
Сложная
Теория чисел
Комбинаторика

Физтех 2022, 10 класс, задача 2

(4 баллов) Найдите количество треугольников периметра 1200 с целочисленными сторонами, у которых одна из биссектрис перпендикулярна одной из медиан.
Сложная
Теория чисел
Планиметрия
Комбинаторика

Физтех 2024, 9 класс, задача 4

(5 баллов) В классе для занятий иностранным языком стоят три ряда парт, в каждом из которых по три парты, расположенных друг за другом. Парта рассчитана на одного человека. Школьник хорошо видит доску в любом из следующих случаев (и только в них): он сидит на первой парте в ряду, ближайшая парта пер
Сложная
Комбинаторика

Физтех 2022, 9 класс, задача 2

(4 баллов) Найдите количество треугольников периметра 600 с целочисленными сторонами, у которых одна из биссектрис перпендикулярна одной из медиан.
Сложная
Теория чисел
Планиметрия
Комбинаторика