Страница: << 1 2 3 4 5 6 [Всего задач: 27]      

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

Прислать комментарий

Решение

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

Прислать комментарий

Решение

Страница: << 1 2 3 4 5 6 [Всего задач: 27]