Bu problem, içerme - dışarma prensibinin güzel bir uygulamasıdır.
Çözüm: $6$ şehri noktalarla gösterelim. Bunlar arasında uçak seferleri olanları da doğru parçalarıyla birleştirelim. $\binom{6}{2}=15$ doğru parçası oluşabilir. Şimdi bu $15$ doğru parçasını kullanıp kullanmama durumuna göre $2^{15}$ yolla seçebiliriz. Bu bize tüm durumların sayısını veriyor. Ancak diğer şehirlerle hiçbir bağlantısı olmayan bir şehir varsa, bu istenmeyen bir durumdur. Böyle bir şehri $\binom{6}{1}$ yolla seçeriz. Geriye kalan $5$ şehir için kendi aralarında $\binom{5}{2}=10$ doğru parçası çizilebilir. Bu $10$ doğru parçasını kullanıp kullanmama durumuna göre $2^{10}$ yolla seçim yapabiliriz. Çarparsak $\binom{6}{1}2^{10}$ olur.
Hem $A$, hem de $B$ gibi iki şehrin de, diğer şehirlerle ve birbirleriyle hiçbir bağlantısı olmaması durumlarını eklemeliyiz. Bunların sayısı $\binom{6}{2}2^6$ dır. Bu şekilde devam edilirse içerme - dışarma prensibinden istenen:
$2^{15} - \binom{6}{1}2^{10} + \binom{6}{2}2^6 - \binom{6}{3}2^3 + \binom{6}{4}2^1 - \binom{6}{5}2^0 + \binom{6}{6}2^0 = 32768 - 6144 + 960 - 160 + 30 - 6 + 1 = 27449$ elde edilir.
(L. Gökçe)
