Решение. Заметим, что никакой город не соединён железной дорогой более чем с двумя другими городами. Действительно, пусть какие-то три города соединены железной дорогой с одним. Тогда все они между собой соединены авиалиниями, что невозможно по условию задачи. Значит, каждый город связан железной дорогой не более чем с двумя другими. Тогда связанные друг с другом железнодорожным сообщением города представляют собой цепочку (возможно, замкнутую). Докажем, что каждая такая цепочка содержит не более 5 вершин.
Пусть города A, B, C, D и E стоят последовательно в цепочке. Поскольку A и C соединены с B железными дорогами, между A и C существует авиалиния. Аналогично между C и E существует авиалиния. Тогда между A и E существует железная дорога, и, значит, города соединены по кругу и больше ни с каким другим городом не связаны. Таким образом, в каждой цепочке не более 5 городов. Чтобы из каждого города можно было добраться до гуманитарного центра, его необходимо открыть в каждой такой цепочке. А значит, и центров необходимо построить хотя бы 100 : 5 = 20, что и требовалось доказать.