В стране 2000 городов. Каждый город связан беспосадочными двусторонними авиалиниями с некоторыми другими городами, причём для каждого города число исходящих из него авиалиний есть степень двойки (то есть 1, 2, 4, 8, ...). Для каждого города A статистик подсчитал количество маршрутов, имеющих не более одной пересадки, связывающих A с другими городами, а затем просуммировал полученные результаты по всем 2000 городам. У него получилось 100000. Докажите, что статистик ошибся.

   Решение

На плоскости дана незамкнутая несамопересекающаяся ломаная, в которой 31 звено (соседние звенья не лежат на одной прямой). Через каждое звено провели прямую, содержащую это звено. Получили 31 прямую, некоторые, возможно, совпали. Какое наименьшее число различных прямых могло получиться?

   Решение

Темы:    [ Сочетания и размещения ] [ Доказательство от противного ] [ Системы точек и отрезков. Примеры и контрпримеры ]

Сложность: 4 Классы: 8,9

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

Условие

На плоскости дана незамкнутая несамопересекающаяся ломаная, в которой 31 звено (соседние звенья не лежат на одной прямой). Через каждое звено провели прямую, содержащую это звено. Получили 31 прямую, некоторые, возможно, совпали. Какое наименьшее число различных прямых могло получиться?

Решение

  Оценка. Кроме концов, на ломаной 30 вершин, и каждая является пересечением двух прямых. Если прямых не более восьми, то точек пересечения не более  7·8 : 2 = 28  – противоречие.

Ответ

9 прямых.

Замечания

1. Ср. с задачей 115502.

2. 8 баллов.

Источники и прецеденты использования