МАЛЫЙ МЕХМАТ МГУ

Кружок 6 класса

Занятие 16. Деревья(11.03.2006)

1.

Обязательно ли является ли деревом граф из задачи 15.2, 15.7, 15.8, графы из задачи 15.4?

2.

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

Ответ Решение

Ответ. Улитка доползет до цели в воскресенье вечером.

Решение. Заметим, что утром во вторник улитка окажется на высоте 1 метр, утром в среду — на высоте 2 метра, и так далее; утром в воскресенье улитка окажется на высоте 6 метров. До вершины дерева в этот момент останется 4 метра, а значит, в воскресенье вечером улитка достигнет своей цели.

3.

Докажите, что в любом дереве существует хотя бы одна висячая вершина.

4.

Существует ли дерево, в котором все вершины имеют одинаковую степень? Сколько вершин может быть в таком дереве? Приведите все варианты.

5.

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

6.

Пусть в дереве В вершин. Сколько в этом дереве рёбер?

7.

В старой усадьбе дом обсажен по кругу высокими деревьями — елями, соснами и березами. Всего деревьев 96. Эти деревья обладают странным свойством: из двух деревьев, растущих через одно от любого хвойного — одно хвойное, а другое лиственное, и из двух деревьев, растущих через три от любого хвойного — тоже одно хвойное, а другое лиственное. Сколько берез посажено вокруг дома?

Ответ

Ответ. 32 берёзы.

8.

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