Question

Король приказал построить в городе метро, в котором: • любые две линии пересекаются ровно в одной общей станции;ровно в одной станции сходятся (пересекаются) ровно три линии, а вовсех остальных станциях сходятся (пересекаются) ровно две линии.Количество линий в этом метро должно быть 102.Сколько станций придётся построить?​

Answer 1

Ответ: 5048, 5045, 5041, 5036, 5030, 5023, 5015, 5006, 4996, 4985, 4973, 4960, 4946, 4931, 4915, 4898, 4880, 4861, 4841, 4820, 4798, 4775, 4751, 4726, 4700, 4673, 4645, 4616, 4586, 4555, 4523, 4490, 4456, 4421, 4385, 4348, 4310, 4271, 4231, 4190, 4148, 4105, 4061, 4016, 3970, 3923, 3875, 3826, 3776, 3725, 3673, 3620, 3566, 3511, 3455, 3398, 3340, 3281, 3221, 3160, 3098, 3035, 2971, 2906, 2840, 2773, 2705, 2636, 2566, 2495, 2423, 2350, 2276, 2201, 2125, 2048, 1970, 1891, 1811, 1730, 1648, 1565, 1481, 1396, 1310, 1223, 1135, 1046, 956, 865, 773, 680, 586, 491, 395, 298, 200, 101, 1

Объяснение: Если бы не было станций, через которые проходили бы более двух линий, то в го-

роде должно было бы быть 101 · 100 = 5050 станций (каждая из линий пересекается 2

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

Если через ровно одну пересадочную станцию проходят ровно три линии, то эта пересадочная станция объединяет три двойных, и тогда ответ 5050 − 2 = 5048.

Если через ровно одну пересадочную станцию проходят ровно k > 3 линий, то эта

пересадочная станция объединяет k(k − 1) двойных, и тогда ответ 5050− k(k − 1) +1. 22

Засчитывались все ответы, получающиеся по этой формуле при k ∈ {3, 4, 5, ..., 101}. Не засчитывались ответы, при которых станций, через которые проходит три или более линий, более одной, т.к. если через станцию проходит k > 3 линий, то и 3 линии через неё проходят.

Ответ: Если бы не было станций, через которые проходили бы более двух линий, то в го-

роде должно было бы быть 101 · 100 = 5050 станций (каждая из линий пересекается 2

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

Если через ровно одну пересадочную станцию проходят ровно три линии, то эта пересадочная станция объединяет три двойных, и тогда ответ 5050 − 2 = 5048.

Если через ровно одну пересадочную станцию проходят ровно k > 3 линий, то эта

пересадочная станция объединяет k(k − 1) двойных, и тогда ответ 5050− k(k − 1) +1. 22

Засчитывались все ответы, получающиеся по этой формуле при k ∈ {3, 4, 5, ..., 101}. Не засчитывались ответы, при которых станций, через которые проходит три или более линий, более одной, т.к. если через станцию проходит k > 3 линий, то и 3 линии через неё проходят.

Ответ: 5048, 5045, 5041, 5036, 5030, 5023, 5015, 5006, 4996, 4985, 4973, 4960, 4946, 4931, 4915, 4898, 4880, 4861, 4841, 4820, 4798, 4775, 4751, 4726, 4700, 4673, 4645, 4616, 4586, 4555, 4523, 4490, 4456, 4421, 4385, 4348, 4310, 4271, 4231, 4190, 4148, 4105, 4061, 4016, 3970, 3923, 3875, 3826, 3776, 3725, 3673, 3620, 3566, 3511, 3455, 3398, 3340, 3281, 3221, 3160, 3098, 3035, 2971, 2906, 2840, 2773, 2705, 2636, 2566, 2495, 2423, 2350, 2276, 2201, 2125, 2048, 1970, 1891, 1811, 1730, 1648, 1565, 1481, 1396, 1310, 1223, 1135, 1046, 956, 865, 773, 680, 586, 491, 395, 298, 200, 101, 1

Answer 2

Для решения данной задачи можно использовать принцип алгебраической топологии. Заведем переменные n - количество станций, k - количество пересечений линий в каждой станции, m - количество линий в метро.

1. В каждой станции сходятся ровно 3 линии, а во всех остальных станциях сходятся ровно 2 линии. Поэтому количество станций с тремя линиями будет на 1 меньше общего количества линий в метро. То есть (m - 1). 2. Мы знаем, что количество пересечений линий в каждой станции должно быть равно 1. Это означает, что каждая линия должна пересекаться ровно с (m - 1) другими линиями. 3. Всего пересечений линий в метро будет равно половине произведения количества линий на количество пересечений линий в каждой станции (по принципу Гансаендаля). Его можно выразить следующим образом: (m * (m - 1)) / 2. 4. Исходя из условия задачи, общее количество пересечений линий должно быть равно количеству линий в метро. То есть (m * (m - 1)) / 2 = m. 5. Решим данное уравнение относительно m: (m^2 - m) / 2 = m. Умножим обе части уравнения на 2: m^2 - m = 2m. Перенесем все слагаемые в одну часть уравнения: m^2 - 3m = 0. Раскроем скобки: m * (m - 3) = 0. Получаем два возможных значения: m = 0 и m = 3. Ноль нам не интересен, так как у нас не может быть метро без линий. 6. Итак, получили, что количество линий в метро должно быть равно 3. 7. Теперь найдем количество станций. Заметим, что на каждую станцию приходится ровно три линии и одно пересечение. Поэтому количество станций будет равно количеству линий в метро. То есть n = m = 3. Количество станций, которые придется построить, равно 3.