В королевстве 20 городов. Некоторые из них соединены прямыми авиарейсами. Известно, что если между городами A и B есть прямой авиарейс, и между городами B и C есть прямой авиарейс, то между городами A и C нет прямого авиарейса. Какое наибольшее количество прямых авиарейсов может быть в королевстве?
More Questions From This User See All
Answers & Comments
Verified answer
Пусть города имеют номера от 1 до 201) 20 рейсов свяжут города по кругу: 1-2; 2-3;...19-20; 20-1
Связывать города через один нельзя: рейса 1-3 быть не может, так как есть рейсы 1-2 и 2-3
2) 20 рейсов свяжут города через два: 1-4; 2-5; 3-6; 4-7; ... 19-2; 20-3
Связывать города через 3 нельзя: рейса 1-5 быть не может, так как есть рейсы 1-2 и 2-5
3) 20 рейсов свяжут города через четыре: 1-6; 2-7; ... 19-4; 20-5
Связывать города через 5 нельзя: рейса 1-7 быть не может, так как есть рейсы 1-4 и 4-7
4) 20 рейсов свяжут города через шесть: 1-8; 2-9; 3-10; 4-11;... 19-6; 20-7
Связывать города через 7 нельзя: рейса 1-9 быть не может, так как есть рейсы 1-8 и 8-9
5) 20 рейсов свяжут города через восемь: 1-10; 2-11; 3-12; ... 19-8; 20-9
Связывать города через 9 нельзя; рейса 1-11 быть не может, так как есть рейсы 1-6 и 6-11
Наибольшее количество прямых авиарейсов 100