Класс_11

Задача 00007

от

Дан отрезок OA. Из конца отрезка A выходит 5 отрезков AB1, AB2, AB3, AB4, AB5. Из каждой точки Bi могут выходить ещё пять новых отрезков или ни одного нового отрезка и т.д. Может ли число свободных концов построенных отрезков равняться 1001? Под свободным концом отрезка понимаем точку, принадлежащую только одному отрезку (кроме точки O).

Решение

При проведении пяти отрезков из конца отрезка появляются 5 новых свободных концов и пропадает один старый. В результате число свободных концов увеличивается на 4. Поэтому если пятёрки отрезков проведены k раз, то число свободных концов равно  4k + 1.  При  k = 250  получаем нужное число свободных концов.

Задача 00004

от

Какое наименьшее число соединений требуется для организации проводной сети связи из 10 узлов, чтобы при выходе из строя любых двух узлов связи сохранялась возможность передачи информации между любыми двумя оставшимися (хотя бы по цепочке через другие узлы)?

Решение

  Оценка. Для того, чтобы сохранилась связь при выходе из строя любых двух узлов, необходимо, чтобы в каждый узел входило не менее трёх линий связи (если узел А соединён с двумя узлами В и С, то при выходе из строя узлов В и С узел А становится недоступным). Таким образом, всего линий связи должно быть не менее  10·3 : 2 = 15.
  Пример: каркас пятиугольной призмы (10 вершин – узлы, а рёбра – линии связи). Если вышли из строя два узла на одном пятиугольнике – основании призмы, то связь сохранится через другой пятиугольник. Если вышли из строя по одному узлу на разных пятиугольниках, то связь тоже сохранится.