Математика Сириус.курсы за 9 класс

Чтобы доказать, что из 100 городов можно закрыть несколько дорог так, чтобы из каждого города выходило не менее одной дороги и хотя бы из 67 городов выходило ровно по одной дороге, воспользуемся методом, известным как «метод индукции» или утверждением о графах.

Определим ситуацию:

У нас есть граф

𝐺

, представляющий 100 городов и дороги между ними. Каждая вершина (город) имеет степень

𝑑

𝑖

≥

1

для всех

𝑖

=

1

,

2

,

…

,

100

(то есть, из каждого города выходит хотя бы одна дорога).

Общее количество дорог:

Обозначим количество дорог в графе как

𝑚

. Поскольку каждая вершина имеет хотя бы одну дорогу, общее количество «выходящих» дорог будет как минимум 100 (по одной из каждого города). То есть,

𝑚

≥

100

.

Обозначим города с различным количеством выходящих дорог:

Пусть

𝑘

— это количество городов, из которых выходит ровно одна дорога. Исходя из условия задачи, нам нужно показать, что мы можем выбрать максимум 67 таких городов.

Остальные города:

Пусть осталось

100

−

𝑘

городов, из которых выходит больше одной дороги. Если у города степень больше 1, то он должен «снабжать» дороги на другие города. Если

𝑑

𝑖

— это степень города

𝑖

, то для каждого из

100

−

𝑘

городов

𝑑

𝑖

≥

2

.

Считаем количество дорог:

Поскольку мы имеем

𝑘

городов со степенью 1 и

100

−

𝑘

городов со степенью хотя бы 2, общее число дорог

𝑚

можно представить следующим образом:

гдедлягородов

𝑚

=

𝑘

⋅

1

+

(

100

−

𝑘

)

⋅

𝑑

𝑖

(где

𝑑

𝑖

≥

2

для

100

−

𝑘

городов)

Это означает, что:

𝑚

≥

𝑘

+

2

(

100

−

𝑘

)

=

𝑘

+

200

−

2

𝑘

=

200

−

𝑘

Сравниваем количество дорог:

Мы знаем, что

𝑚

≥

100

и

𝑚

≥

200

−

𝑘

. Таким образом, у нас есть два неравенства:

100

≤

200

−

𝑘

⇒

𝑘

≤

100

Это означает, что

𝑘

(количество городов с одной дорогой) не может превышать 100. Но мы также знаем, что

𝑘

не может быть 67. Работая с этим ограничением:

Этовсегдавыполняется

𝑘

+

(

100

−

𝑘

)

≥

100

⇒

Это всегда выполняется.

Однако, для наибольшей целеустремленности мы можем установить:

100

−

𝑘

≤

𝑚

⇒

100

−

𝑘

≤

100

⇒

𝑘

≥

33.

Заключение:

Из вышеприведенной логики и установки можно заключить, что мы действительно можем выбрать 67 городов, так, что из каждого из них будет только одна дорога, оставаясь при этом с дороги из каждого города. Таким образом, мы обеспечим, что из 33 оставшихся городов будет по меньшей мере 2 дороги.

Это и доказывает, что можно закрыть несколько дорог так, чтобы из 67 городов выходило ровно по одной дороге.