Geomania.Org Forumları
Yarışma Soruları => Tübitak Lise Takım Seçme => 2007 => Konuyu başlatan: Lokman Gökçe - Ağustos 09, 2013, 12:43:18 ös
-
Bir havayolu şirketi $A,B,C,D,E$ ve $F$ kentlerinden bazıları arasında karşılıklı uçak seferleri başlatacaktır. Bu altı kentten herhangi ikisi arasında yalnızca bu şirketin seferlerini kullanarak ulaşımı mümkün kılacak biçimde, bu seferlerin kaç farklı biçimde düzenlenebileceğini belirleyiniz.
(Okan Tekman)
-
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)