Главное меню

Новости:

SMF - Just Installed!

Как решить задачу "В стране 15 городов..."?

Автор Camain, Март 14, 2024, 19:25

« назад - далее »

Camain

Условия: В стране 15 городов, некоторые соединены дорогами (каждая дорога соединяет 2 различных города; никакие два города не соединены  более чем одной дорогой). Всего в стране 27 дорог.
Известно, что из всех городов выходит одинаковое кол-во дорог, а из столицы - другое число дорог.
1. Сколько дорог выходит из столицы?
2.Сколько дорог выходит из нестоличного города?

Tondile

На самом деле если считать, что задача имеет решение, то ответить на поставленные вопросы можно и без графического представления.
Решение: мы знаем, что дорог 27, значит выездов из городов 54 (каждая дорога 2 выезда), если города не соединены более чем одной дорогой следовательно из столицы выходит от 1 до 14 дорог (выездов), а оставшиеся выезды должны быть поделены поровну между остальными городами, в итоге приходим, что не нарушить условия возможна только единственная комбинация: из обычного города выходит по 3 дороги, а из столицы 12 (14*3+12=54).
С графическим представлением этого несколько посложнее. Если просто соединить попарно соседние города получится 14 дорог и плюс 12 до столицы, но из 2 городов тогда будут выходить только по две дороги, так как они не соединены со столицей, а всего будет только 26 дорог, проблема бы решилась если сделать между этими двумя еще одну дорогу, но в условиях есть запрет на более чем одну дорогу между городами. В итоге у меня родилось такое решение