Question

В королевстве 20 городов. Некоторые из них соединены прямыми авиарейсами. Известно, что если между городами A и B есть прямой авиарейс, и между городами B и C есть прямой авиарейс, то между городами A и C нет прямого авиарейса. Какое наибольшее количество прямых авиарейсов может быть в королевстве?

Answer 1

Пусть города имеют номера от 1 до 20

1) 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