İki küre için kullanılan mantıkla yola devam edelim. Yani ilk olarak $n_{1}$ numaralı kattan küreyi bırakalım. Kırılırsa kalan iki küre ile $1$'den $n_{1} - 1$'e kadar olan katları daha önceki yazıda bulduğumuz gibi $\frac {n \cdot (n+1)}{2} \ge n_{1} - 1$ eşitsizliğini çözerek $n$ adımda deneyebiliriz. Eğer ilk küre ilk denemede kırılmazsa ikinci deneme için ilk deneme katını öyle artırmalıyız ki kırılırsa kalan iki küreyle bu artış miktarını $n-1$ adımda çözebilelim. Bu yöntemi diğer adımlar için de genelleyerek bir tablo halinde gösterelim:
| Adım | Artış miktarı |
| 1 | $\frac{n \cdot (n+1)}{2} + 1$ |
| 2 | $\frac{(n-1) \cdot (n+2)}{2} + 1$ |
| 3 | $\frac{(n-2) \cdot (n+3)}{2} + 1$ |
| ... | ... |
Her adımda son iki küre artışı tam deneyebildiğinden artış miktarına ilk küre için ekstra bir deneme katı daha ekleyebildik. Bu şekilde ilk küre herhangi bir adımda kırıldığında maksimum deneme sayısı adım sayısı artı iki küre durumunda artış için çözüm adım sayısı, o da eşittir $n+1$ olacaktır ($n + 1 = (n-1)+2 = (n-2) + 3 = ...$).
Yukarıdaki tabloyu kullanarak birinci küre için deneme yüksekliklerini yazalım.
Artış miktarlarını topladığımız zaman $n+1$ adım sonunda eksiksiz taranabilecek yükseklik bulunur. Basit bir değişken dönüşümüyle bu tabloyu üç küre için $n$ adımda çözümü verecek şekilde yazabiliriz.
Toplam yükseklik = $\sum\limits_{i=1}^n {\frac{i \cdot (i-1)}{2} + 1} = \frac{1}{2} \sum\limits_{i=1}^n {i^2} - \frac{1}{2} \sum\limits_{i=1}^n {i} + \sum\limits_{i=1}^n {1} = \frac {1}{12} n \cdot (n+1) \cdot (2\cdot n + 1) - \frac {1}{4} n \cdot (n+1) + n$
$\sum\limits_{i=1}^n {i^2}$ toplamı için bir formül bulmaya çalışalım. Bunun için önce formülün üçüncü derece bir polinom şeklinde yazılabileceğini var sayalım. Yani
$\sum\limits_{i=1}^n {i^2} = a \cdot n^3 + b \cdot n^2 + c \cdot n + d$
$a, b, c, d$ değerlerini bulmak için kare toplamların ilk dört değeri için denklemler yazalım ve bu dört bilinmeyenli dört denklemi çözelim.
$a + b + c + d = 1$ (1)
$8 \cdot a + 4 \cdot b + 2 \cdot c + d = 1 + 4 = 5$ (2)
$27 \cdot a + 9 \cdot b + 3 \cdot c + d = 1 + 4 + 9= 14$ (3)
$64 \cdot a + 16 \cdot b + 4 \cdot c + d = 1 + 4 + 9 + 16 = 30$ (4)
İlk önce $d$ değişkenlerinden kurtulmak için (2) - (1), (3) - (2) ve (4) - (3) denklemlerini hesaplayalım.
$7 \cdot a + 3 \cdot b + c = 4$ (5)
$19 \cdot a + 5 \cdot b + c = 9$ (6)
$37 \cdot a + 7 \cdot b + c = 16$ (7)
(9) - (8) ile $b$ katsayısını ortadan kaldırırsak
$6a = 2 \implies a = \frac{1}{3}$ buluruz.
Bu değeri (8)'de yerine koyup $b$ katsayısını bulalım.
$12 \cdot \frac{1}{3} + 2 \cdot b = 5 \implies b = \frac {1}{2} \cdot (5 - 4) = \frac {1}{2}$
$a$ ve $b$ değerlerini şimdi (5) denklemine koyalım.
$7 \cdot \frac{1}{3} + 3 \cdot \frac{1}{2} + c = 4 \implies c = 4 - \frac{7}{3} - \frac{3}{2} = \frac{1}{6}$
Son olarak hepsini (1) denklemine koyalım ve $d$'yi bulalım.
$\frac{1}{3} + \frac{1}{2} + \frac{1}{6} + d = 1 \implies d = 1 - \frac{1}{3} - \frac{1}{2} - \frac{1}{6} = 0$
Var sayımımıza göre $\sum\limits_{i=1}^n {i^2} = \frac{1}{3} \cdot n^3 + \frac{1}{2} \cdot n^2 + \frac{1}{6} \cdot n = \frac{1}{6} \cdot n \cdot (n+1) \cdot (2n + 1)$
Şimdi formülümüzün doğruluğunu tümevarımla test edelim.
önce formülü $n=1$ için test edelim.
$\frac{1}{6} \cdot 1 \cdot (1+1) \cdot (2 \cdot 1 + 1) = \frac{1}{6} \cdot 1 \cdot (2) \cdot (3) = 1$
Şimdi formülü $n$ için doğru kabul edip $n+1$ için doğru olup olmadığına bakalım.
$\frac{1}{6} \cdot n \cdot (n+1) \cdot (2n + 1) + (n+1)^2 = \frac{1}{6} \cdot n \cdot (n+1) \cdot (2n + 1) + n^2 + 2 \cdot n +1 = \frac{1}{6} (2 \cdot n^3 + 3 \cdot n^2 + n) + n^2 + 2 \cdot n +1 = \frac{1}{6} (2 \cdot n^3 + 3 \cdot n^2 + n) + \frac{1}{6}(6 \cdot n^2 + 12 \cdot n +6) = \frac{1}{6}(2 \cdot n^3 + 9 \cdot n^2 + 13 \cdot n + 6) = \frac{1}{6} \cdot (n+1) \cdot (n+2) \cdot (2 \cdot n + 3)$
Demek ki formül $n+1$ için de doğruymuş. Böylece formülümüzün bütün $n \ge 1$ doğal sayıları için doğru olduğunu ispatladık.
Şimdi toplam yükseklik için formülü tekrar yazalım.
Toplam yükseklik = $\sum\limits_{i=1}^n {\frac{i \cdot (i-1)}{2} + 1} = \frac{1}{2} \sum\limits_{i=1}^n {i^2} - \frac{1}{2} \sum\limits_{i=1}^n {i} + \sum\limits_{i=1}^n {1} = \frac {1}{12} n \cdot (n+1) \cdot (2\cdot n + 1) - \frac {1}{4} n \cdot (n+1) + n = \frac {1}{6} n \cdot (n^2 + 5)$
$N$ katlı bir bina için $\frac {1}{6} n \cdot (n^2 + 5) \ge N$ eşitsizliğini n için çözersek gereken maksimum deneme sayısının en küçük değerini buluruz.
Çözümlerde eşitsizliğin derecesi küre sayısına eşit olduğunu görüyoruz, yani iki küre için ikinci derece bir eşitsizlik, üç küre için de üçüncü derece bir eşitsizlik. Küre sayısı arttıkça eşitsizliğin derecesi de artacaktır. Daha yüksek sayılı küreler için eşitsizlikler aynı mantıkla bulunabilir.
Bu soruyla ilgili bahsetmek istediğim bir şey de verilen bir $N$ için en düşük maksimum deneme sayısının alt limiti iki tabanına göre $\log N$ ile verilir. Yani bu sayıda ya da daha fazla küremiz var ise yapılması gereken tek şey ikili arama algoritmasını kullanmaktır. Yani kısaca her adımda kalan aralığı eşit iki parçaya ayıracak şekilde deneme katını seçmek gerek. Bu şekilde yukarıda verilen adım sayısında her kata ulaşmak mümkün.
Yukarıdaki tabloyu kullanarak birinci küre için deneme yüksekliklerini yazalım.
| Adım | Deneme yüksekliği |
| 1 | $\frac{n \cdot (n+1)}{2} + 1$ |
| 2 | $\frac{n \cdot (n+1)}{2} + \frac{(n-1) \cdot (n)}{2} + 2$ |
| 3 | $\frac{n \cdot (n+1)}{2} + \frac{(n-1) \cdot (n)}{2} + \frac{(n-2) \cdot (n-1)}{2} +3$ |
| ... | ... |
Artış miktarlarını topladığımız zaman $n+1$ adım sonunda eksiksiz taranabilecek yükseklik bulunur. Basit bir değişken dönüşümüyle bu tabloyu üç küre için $n$ adımda çözümü verecek şekilde yazabiliriz.
| Adım | Deneme yüksekliği |
| 1 | $\frac{n \cdot (n-1)}{2} + 1$ |
| 2 | $\frac{n \cdot (n-1)}{2} + \frac{(n-1) \cdot (n-2)}{2} + 2$ |
| 3 | $\frac{n \cdot (n-1)}{2} + \frac{(n-1) \cdot (n-2)}{2} + \frac{(n-2) \cdot (n-3)}{2} +3$ |
| ... | ... |
Toplam yükseklik = $\sum\limits_{i=1}^n {\frac{i \cdot (i-1)}{2} + 1} = \frac{1}{2} \sum\limits_{i=1}^n {i^2} - \frac{1}{2} \sum\limits_{i=1}^n {i} + \sum\limits_{i=1}^n {1} = \frac {1}{12} n \cdot (n+1) \cdot (2\cdot n + 1) - \frac {1}{4} n \cdot (n+1) + n$
$\sum\limits_{i=1}^n {i^2}$ toplamı için bir formül bulmaya çalışalım. Bunun için önce formülün üçüncü derece bir polinom şeklinde yazılabileceğini var sayalım. Yani
$\sum\limits_{i=1}^n {i^2} = a \cdot n^3 + b \cdot n^2 + c \cdot n + d$
$a, b, c, d$ değerlerini bulmak için kare toplamların ilk dört değeri için denklemler yazalım ve bu dört bilinmeyenli dört denklemi çözelim.
$a + b + c + d = 1$ (1)
$8 \cdot a + 4 \cdot b + 2 \cdot c + d = 1 + 4 = 5$ (2)
$27 \cdot a + 9 \cdot b + 3 \cdot c + d = 1 + 4 + 9= 14$ (3)
$64 \cdot a + 16 \cdot b + 4 \cdot c + d = 1 + 4 + 9 + 16 = 30$ (4)
İlk önce $d$ değişkenlerinden kurtulmak için (2) - (1), (3) - (2) ve (4) - (3) denklemlerini hesaplayalım.
$7 \cdot a + 3 \cdot b + c = 4$ (5)
$19 \cdot a + 5 \cdot b + c = 9$ (6)
$37 \cdot a + 7 \cdot b + c = 16$ (7)
Şimdi $c$ değişkenlerinden kurtulalım. Bunun için tabii ki (6) - (5) ve (7) - (6) farklarını hesaplayacağız.
$12 \cdot a + 2 \cdot b = 5$ (8)
$18 \cdot a + 2 \cdot b = 7$ (9)
$18 \cdot a + 2 \cdot b = 7$ (9)
$6a = 2 \implies a = \frac{1}{3}$ buluruz.
Bu değeri (8)'de yerine koyup $b$ katsayısını bulalım.
$12 \cdot \frac{1}{3} + 2 \cdot b = 5 \implies b = \frac {1}{2} \cdot (5 - 4) = \frac {1}{2}$
$a$ ve $b$ değerlerini şimdi (5) denklemine koyalım.
$7 \cdot \frac{1}{3} + 3 \cdot \frac{1}{2} + c = 4 \implies c = 4 - \frac{7}{3} - \frac{3}{2} = \frac{1}{6}$
Son olarak hepsini (1) denklemine koyalım ve $d$'yi bulalım.
$\frac{1}{3} + \frac{1}{2} + \frac{1}{6} + d = 1 \implies d = 1 - \frac{1}{3} - \frac{1}{2} - \frac{1}{6} = 0$
Var sayımımıza göre $\sum\limits_{i=1}^n {i^2} = \frac{1}{3} \cdot n^3 + \frac{1}{2} \cdot n^2 + \frac{1}{6} \cdot n = \frac{1}{6} \cdot n \cdot (n+1) \cdot (2n + 1)$
Şimdi formülümüzün doğruluğunu tümevarımla test edelim.
önce formülü $n=1$ için test edelim.
$\frac{1}{6} \cdot 1 \cdot (1+1) \cdot (2 \cdot 1 + 1) = \frac{1}{6} \cdot 1 \cdot (2) \cdot (3) = 1$
Şimdi formülü $n$ için doğru kabul edip $n+1$ için doğru olup olmadığına bakalım.
$\frac{1}{6} \cdot n \cdot (n+1) \cdot (2n + 1) + (n+1)^2 = \frac{1}{6} \cdot n \cdot (n+1) \cdot (2n + 1) + n^2 + 2 \cdot n +1 = \frac{1}{6} (2 \cdot n^3 + 3 \cdot n^2 + n) + n^2 + 2 \cdot n +1 = \frac{1}{6} (2 \cdot n^3 + 3 \cdot n^2 + n) + \frac{1}{6}(6 \cdot n^2 + 12 \cdot n +6) = \frac{1}{6}(2 \cdot n^3 + 9 \cdot n^2 + 13 \cdot n + 6) = \frac{1}{6} \cdot (n+1) \cdot (n+2) \cdot (2 \cdot n + 3)$
Demek ki formül $n+1$ için de doğruymuş. Böylece formülümüzün bütün $n \ge 1$ doğal sayıları için doğru olduğunu ispatladık.
Şimdi toplam yükseklik için formülü tekrar yazalım.
Toplam yükseklik = $\sum\limits_{i=1}^n {\frac{i \cdot (i-1)}{2} + 1} = \frac{1}{2} \sum\limits_{i=1}^n {i^2} - \frac{1}{2} \sum\limits_{i=1}^n {i} + \sum\limits_{i=1}^n {1} = \frac {1}{12} n \cdot (n+1) \cdot (2\cdot n + 1) - \frac {1}{4} n \cdot (n+1) + n = \frac {1}{6} n \cdot (n^2 + 5)$
$N$ katlı bir bina için $\frac {1}{6} n \cdot (n^2 + 5) \ge N$ eşitsizliğini n için çözersek gereken maksimum deneme sayısının en küçük değerini buluruz.
Çözümlerde eşitsizliğin derecesi küre sayısına eşit olduğunu görüyoruz, yani iki küre için ikinci derece bir eşitsizlik, üç küre için de üçüncü derece bir eşitsizlik. Küre sayısı arttıkça eşitsizliğin derecesi de artacaktır. Daha yüksek sayılı küreler için eşitsizlikler aynı mantıkla bulunabilir.
Bu soruyla ilgili bahsetmek istediğim bir şey de verilen bir $N$ için en düşük maksimum deneme sayısının alt limiti iki tabanına göre $\log N$ ile verilir. Yani bu sayıda ya da daha fazla küremiz var ise yapılması gereken tek şey ikili arama algoritmasını kullanmaktır. Yani kısaca her adımda kalan aralığı eşit iki parçaya ayıracak şekilde deneme katını seçmek gerek. Bu şekilde yukarıda verilen adım sayısında her kata ulaşmak mümkün.
Hiç yorum yok:
Yorum Gönder