Найти тему
Плохой Программист

Сириус. Комбинаторика. 7 класс. Двудольные графы

В стране есть города и посёлки. Между некоторыми населёнными пунктами построены дороги. Известно, что есть 8 дорог, соединяющих города, и 20 дорог, соединяющих посёлки. При этом из каждого населённого пункта в посёлки выходит на одну дорогу больше, чем в города. Сколько всего населённых пунктов в стране?

Есть города(Г) и поселки(П), т.е. дороги могут быть следующие:

Г-Г(8), Г-П, П-Г, П-П(20)

Помним, что из каждого населенного пункта выходит в поселок на 1 дорогу больше, чем в город.

Дорог из города в поселок (Г-П) для каждого города больше на одну, чем в другие города.

Дорог из поселка в город (П-Г) для каждого поселка меньше на одну, чем в другие поселки.

При этом Г-П=П-Г

Рассмотрим город из него выходит г1 городских дорог и г1+1 поселковых.

Так как каждая дорога между городами выходя из одного города, входит в другой, то когда мы просуммируем все дороги всех городов, то городских получится 16 (мы знаем что Г-Г=8 и одна дорога соединяет 2 города, поэтому считается для каждого из них).

Значит, сельских дорог (Г-П) будет 16+количество городов (их столько же сколько и городских + для каждого из городов на 1 больше).

Теперь рассмотрим поселок. Из него выходит п1 дорог в села и п1-1 в города. Опять же при сложении всех дорог выясниться, что поселковых дорог будет 40, значит городских (П-Г) 40-количество поселков.

Вспоминаем, что Г-П=П-Г

16+количество городов=40-количество поселков

Остальные задачи раздела

Наука
7 млн интересуются