Euler Projesi 285. Soru

Pisagor Olasılığı

Albert pozitif bir tam sayı k seçer, ardından tekdüze dağılımlı [0,1] aralığında rastgele iki reel sayı a, b seçilir. Daha sonra (k·a + 1)² + (k·b + 1)² toplamının karekökü hesaplanır ve en yakın tam sayıya yuvarlanır. Sonuç k'ye eşitse, Albert k puan alır; aksi takdirde hiçbir puan almaz.

Örneğin, k = 6, a = 0,2 ve b = 0,85 ise, (k·a + 1)² + (k·b + 1)² = 42,05.

42,05'in karekökü 6,484'tür ... ve en yakın tam sayıya yuvarlandığında 6 olur.

Bu k'ye eşittir, bu yüzden 6 puan alır.

k = 1, k = 2, ..., k = 10 ile 10 tur oynarsa, beş ondalık basamağa yuvarlanmış toplam puanının beklenen değerinin 10,20914 olduğu gösterilebilir.

k = 1, k = 2, k = 3, ..., k = 105 ile 105 tur oynarsa, beş ondalık basamağa yuvarlanan toplam puanının beklenen değeri kaçtır?

Euler Projesi 255. Soru

Yuvarlanmış Kare Kökler

Bir n pozitif tam sayının yuvarlanmış kare kökünü, n'nin kare kökünün en yakın tam sayıya yuvarlanmış değeri olarak tanımlarız.

Aşağıdaki işlemle (özellikle tam sayı aritmetiğine uyarlanmış Heron yöntemi) n'nin yuvarlanmış kare kökü bulunur:

n sayısının basamak sayısı d olsun.
d tek ise $x_0=2\times 10^{\frac{(d-1)}{2}}$ olsun.
d çift ise $x_0=7\times 10^{\frac{(d-2)}{2}}$ olsun.

$x_{k+1}=x_k$ olana kadar $$x_{k+1}=\lfloor \frac{x_k+\lceil \frac{n}{x_k}\rceil}{2}\rfloor$$tekrarlayalım.

Örneğin n=4321 sayısının yuvarlanmış kare kökünü bulalım.

n sayısının 4 basamağı var, yani $x_0=7\times 10^{\frac{(4-2)}{2}}=70$ olur. $$x_{1}=\lfloor \frac{70+\lceil \frac{4321}{70}\rceil}{2}\rfloor=66$$ $$x_{2}=\lfloor \frac{66+\lceil \frac{4321}{66}\rceil}{2}\rfloor =66$$

$x_2=x_1$ olduğundan burada dururuz.

Böylece sadece iki iterasyon ile 4321 sayısının yuvarlanmış karekökünün 66 olduğunu bulduk (gerçek kare kökü ise 65,7343137...).

Bu yöntemde gereken iterasyon sayısı şaşırtıcı derecede azdır.

Örneğin 5 basamaklı bir tam sayının ($10.000\le n\le 99.999$) yuvarlanmış kare kökünü yaklaşık 3,2102888889 (10 ondalık basamağa yuvarlanmış yaklaşık değer) iterasyonda bulabiliriz.

Yukarıda tanımlanan işlemle 14 basamaklı bir sayının ($10^{13}\le n< 10^{14}$) yuvarlanmış kare kökünü bulmak için gereken yaklaşık iterasyon sayısı kaçtır?

Cevabınızı 10 ondalık basamağa yuvarlayarak verin.

Not: $\lfloor x\rfloor$ ve $\lceil x\rceil$ sembolleri sırasıyla taban ve tavan fonksiyonlarını ifade eder.