№ 6. На аллее в ряд растут деревья шести видов. Для любых двух различных видов нашлась пара соседних деревьев этих видов. Какое наименьшее количество деревьев может расти на аллее?

Рассмотрим каждый вид как вершину графа, а соседство двух разных видов — как ребро. Нужно, чтобы среди последовательных пар деревьев встретились все 15 пар видов: \(\binom{6}{2}=15\). В ряду из \(n\) деревьев имеется \(n-1\) соседних пар, поэтому сначала получаем нижнюю оценку \(n\ge16\).

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

Достаточно 18 деревьев: можно пройти все рёбра полного графа на шести вершинах, повторив два ребра с непересекающимися концами. Тогда нечётных вершин останется две, и получится маршрут, в котором встречаются все 15 пар видов.

Ответ: 18 деревьев.