Soru
\(5\) köyün bulunduğu bir ilçede bu köyler arasında gidiş gelişi sağlayacak yollar yapılacaktır. Buna göre, herhangi bir köyün izole olmadığı, yani diğer köylerden en az biriyle arasında bir yol bulunduğu, kaç farklı sistem tasarlanabilir?Çözüm
Çözümü daha iyi anlamak için öncelikle "İçerme Dışarma Prensibi" ni inceleyebilirsiniz.Şekildeki gibi köyler arasında çizilebilecek tüm yolların sayısının
\(\left( {\begin{array}{*{20}{c}}
5\\
2
\end{array}} \right) = 10\) olduğunu görebiliriz.
Köyler arasında kurulacak bir yol sistemini için bu yollardan herhangi biri ya seçilir ya da seçilmez. Yani her yol için 2 seçenek mevcuttur. O halde bu yollar ile toplamda \[{2^{10}}\] farklı sistem kurulabilir. Bu değere \({S_0}\) diyelim. Böylece \[{S_0} = {2^{10}} = 1024\] bulunur. Fakat tabii ki bu sistemler içinde istenilen şarta uygun olmayan durumlarda mevcuttur. Herhangi bir köyün izole olmadığı durumları saymak için aksini düşünüp köylerin izole olduğu durumları sayacak ve tüm durumdan çıkaracağız.
Öncelikle şekildeki gibi köylerden sadece birinin izole olduğu durumların sayısını bulalım.
4 köy arasında
\(\left( {\begin{array}{*{20}{c}}
4\\
2
\end{array}} \right)=6\) yol var. Bu nedenle seçilen bir köyün izole olduğu sistem sayısı \[{2^6}\] olur. Şekildeki gibi
\(\left( {\begin{array}{*{20}{c}}
5\\
1
\end{array}} \right) = 5\) farklı biçimde izole olacak köy seçebileceğimizden, herhangi bir köyün izole olduğu sistem sayısı
\[\left( {\begin{array}{*{20}{c}}
5\\
1
\end{array}} \right) \cdot {2^6}\] olur. Bu değere \({S_1}\) diyelim. Böylece \[{S_1} = 5 \cdot 64 = 320\] bulunur.
Şimdi aşağıdaki şekildeki gibi iki köyün izole olduğu sistem sayısını bulalım.
3 köy arasında şekilden de görüleceği üzere
\(\left( {\begin{array}{*{20}{c}}
3\\
2
\end{array}} \right) = 3\) adet yol vardır. O nedenle bu yollar ile \[{2^3}\] farklı sistem yapılabilir. Şekildeki gibi 2 köyün izole olduğu
\(\left( {\begin{array}{*{20}{c}}
5\\
2
\end{array}} \right)\) farklı seçim mümkün olduğundan, herhangi 2 köyün izole olduğu
\[\left( {\begin{array}{*{20}{c}}
5\\
2
\end{array}} \right) \cdot {2^3}\] sistem vardır. Bu değere \({S_2}\) dersek, \[{S_2} = 10 \cdot 8 = 80\] bulunur.
Şimdi de 3 köyün izole olduğu durumların sayısını düşünelim. Kalan 2 köy arasında bir yol olacağından \[{2^1}\] farklı sistem kurulabilir. Ayrıca 5 köy arasından 3 izole köy
\(\left( {\begin{array}{*{20}{c}}
5\\
3
\end{array}} \right)\) farklı biçimde seçilebileceğinden, herhangi 3 köyün izole olduğu sistem sayısı
\[\left( {\begin{array}{*{20}{c}}
5\\
3
\end{array}} \right) \cdot 2\] olur. Bu değere \({S_3}\) dersek, \[{S_3} = 10 \cdot 2 = 20\] olur.
Şimdi, 4 köyün izole olduğu durum sayısını düşünelim. Geriye kalan köy için herhangi bir yol çizilemeyeceğinden böyle bir seçimde 1 sistem oluşur. Herhangi 4 köyün izole olduğu
\(\left( {\begin{array}{*{20}{c}}
5\\
4
\end{array}} \right) = 5\) seçim olacağından, bu durum kendini 5 kez tekrar eder. Bu değere de \({S_4}\) dersek, \[{S_4} = 5\] olur.
Son olarak tüm köylerin izole olduğu 1 durum vardır. Bu değere de \({S_5}\) dersek, \[{S_5} = 1\] olur.
O halde içerme dışarma prensibi gereği, herhangi bir köyün izole olmadığı sistem sayısı
\[\begin{align*}
S &={S_0} - {S_1} + {S_2} - {S_3} + {S_4}-{S_5}\\
&=1024 - 320 + 80 - 20 + 5-1\\
&=768
\end{align*}\] bulunur.
Soru
\(20!\) sayısı kaç farklı biçimde iki veya daha fazla ardışık pozitif tam sayının toplamı biçiminde yazılabilir?Çözüm
\(n\) bir pozitif tam sayı olsun. Öncelikle \(n\) sayısının kendisi dahil ister pozitif, ister negatif veya \(0\) olsun kaç farklı biçimde iki veya daha fazla ardışık tam sayının toplamı biçiminde yazılabileceğini hesaplayalım.
- \(n\) sayısının tek adette terim içeren ardışık tüm yazılımlarını, tamamı bir \(a\) tam sayısı ve negatif olmayan bir \(b\) tam sayısı ile \(n = \left( {a - b} \right) + ... + a + ... + \left( {a + b} \right)\) yani \(n = a\left( {2b + 1} \right)\) biçiminde gösterebiliriz. \(b\) negatif olmadığından \(2b+1>0\) tek çarpanı, bu eşitliğin \(n\) nin pozitif tek bölenleri kadar çözümü olacağını göstermektedir.
- \(n\) sayının çift adette terim içeren ardışık tüm yazılımlarını da bir \(a\) tam sayısı ve bir \(b\) pozitif tam sayısı ile \(n = \left( {a - b + 1} \right) + ... + a + \left( {a + 1} \right) + ... + (a + b)\) yani \(n = \left( {a + 1/2} \right).2b = \left( {2a + 1} \right)b\) biçiminde gösterebiliriz. \(b\) ve \(n\) pozitif olduğundan \(2a+1>0\) olmalıdır. Bu nedenle bu eşitliğin de \(n\) nin pozitif tek bölenleri kadar çözümü olacağı görülmektedir.
Şimdi en büyük terimi \(d\) olan \(n = c+...+d\) gösterimini düşünelim. Eğer \(c>0\) ise, bu gösterimin önüne \((1-c)+...+(c-1) = 0\) ekleyerek ilk terimi pozitif olmayan \(n = (1-c)+...+d\) gösterimini elde ederiz. Eklenen \((1-c)+...+(c-1)\) terimlerin gösterim biçiminin tek olduğu açık olduğundan, elde edilen bu yeni gösterimin de tek olduğu açıktır. Benzer biçimde eğer \(1-c<=0\) ise, \(n = (1-c)+...+d\) gösteriminde başta yer alan \((1-c)+...+(c-1)\) terimleri silinerek \(n = c+...+d\) gösterimi tek bir biçimde elde edilecektir. Demek ki terimleri pozitif olan her gösterim için, her terimi pozitif olmayan bir başka gösterim daha vardır.
O halde tüm gösterimlerin yarısı pozitif terimlilerden, diğer yarısı da her terimi pozitif olmayan terimlilerden oluşmaktadır. Yani \(n\) pozitif tam sayısının kendisi dahil iki veya daha fazla ardışık pozitif tam sayının toplamı biçiminde gösterim sayısı, \(n\) nin pozitif tek bolen sayısı kadardır.
Dikkat edilirse \(2\) sayısının tek gösterimi kendisidir. Benzer biçimde \(2^k\) (\(k\) pozitif bir tamsayı) formatındaki tam sayıların iki veya daha fazla ardışık gösterimleri yoktur.
Sorumuzun cevabına gelirsek, \[20! = {2^{18}} \cdot {3^8} \cdot {5^4} \cdot {7^2} \cdot 11 \cdot 13 \cdot 17 \cdot 19\] olduğundan pozitif tek bölen sayısı \[(8+1)(4+1)(2+1)(1+1)(1+1)(1+1)(1+1) = 2160\] olduğundan kendisi hariç \(2159\) farklı biçimde iki veya daha fazla ardışık pozitif tam sayının toplamı biçiminde yazılabilir.
Kaynak: http://www.qbyte.org/puzzles/puzzle10.html (soru 92)
Çalışmalarım
Zaman buldukça kendimce ilginç bulduğum çalışmaları burada paylaşıyorum. Sağdaki menüden şimdiye kadar yapılan çalışmalara ulaşabilirsiniz. Şu an için en popüleri "Üçgen Olasılık" tır.