Euler Projesi 280. Soru

Karınca ve tohumlar

Çalışkan bir karınca 5x5 bir ızgarada rastgele yürüyor. Yürüyüş merkezdeki kareden başlıyor. Her adımda karınca ızgara dışına çıkmadan rastgele komşu bir kareye hareket ediyor; dolayısıyla karıncanın konumuna bağlı olarak her adımda 2, 3 veya 4 olasılık mevcuttur.

Yürüyüşe başlarken alttaki satırın her bir karesine bir tohum yerleştirilir. Karınca bir tohum taşımıyorken tohum bulunan alt satırdaki bir kareye ulaştığında, tohumu taşımaya başlar. Sonrasında üst satırda bulunan ulaştığı ilk boş kareye tohumu bırakır.

Tüm tohumların sonuçta üst satırda bırakılmış olmasına kadar geçen adım sayısının beklenen değeri kaçtır? Cevabınızı 6 ondalık basamağa yuvarlayarak veriniz.

Euler Projesi 276. Soru

İlkel Üçgenler

Kenar uzunlukları a, b ve c ($a\le b\le c$) tam sayıları olan üçgenleri düşünün.
Tam sayı kenar uzunluklarına sahip herhangi bir üçgen GCD(a,b,c)=1 ise ilkel olarak adlandırılır.
Çevre uzunluğu 10.000.000'dan fazla olmayan kaç adet tam sayı kenarlı ilkel üçgen bulunur?

Euler Projesi 271. Soru

Modüler Küpler, kısım 1

Bir pozitif n sayısı için $1<x<n$ ve $x^3\equiv 1$ mod n olmak üzere x tam sayılarının toplamı S(n) ile tanımlansın.

n=91 iken x için 8 olası değer mevcut:  9, 16, 22, 29, 53, 74, 79, 81.
Yani, S(91)=9+16+22+29+53+74+79+81=363.

S(13082761331670030) kaçtır?

Euler Projesi 270. Soru

Kare kesme

Tam sayı N × N boyutlu kare bir kağıt parçası, bir köşesi başlangıç noktasında ve iki kenarı da x ve y eksenleri üzerinde olacak şekilde yerleştiriliyor. Ardından aşağıdaki kurallara uyarak bu kareyi kesiyoruz:

• Sadece karenin farklı kenarlarında bulunan ve tam sayı koordinatlarına sahip iki nokta arasında uzanan düz kesimler yapıyoruz.
• İki kesim kesişemez, ancak kesimler aynı kenar noktasında buluşabilir.
• Daha fazla kurallı kesme yapılamayana kadar kesmeye devam edin.

Herhangi bir yansımayı veya dönüşümü farklı sayarsak, N x N karesini kesme yollarının sayısını C(N) ile tanımlayalım. Örneğin C(1) = 2 ve C(2) = 30 (aşağıda gösterilmiştir).

C(30) mod 10⁸ kaçtır?

Euler Projesi 257. Soru

Açıortaylar

Aşağıda kenar uzunlukları a ≤ b ≤ c tam sayıları olan bir ABC üçgeni veriliyor. (AB = c, BC = a ve AC = b).
Üçgenin açıortayları kenarları E, F ve G noktalarında kesiyor (aşağıdaki resme bakınız).

EF, EG ve FG segmentleri ABC üçgenini dört küçük üçgene böler: AEG, BFE, CGF ve EFG.
Bu dört üçgenin her biri için alan(ABC)/alan(alt üçgen) oranının rasyonel olduğu kanıtlanabilir.
Bununla birlikte, bu oranların bir kısmının veya tamamının tam sayı olduğu üçgenler vardır.

Alan(ABC)/alan(AEG) oranı tam sayı olacak şekilde çevre uzunluğu ≤100.000.000 olan kaç ABC üçgeni vardı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.

Euler Projesi 246. Soru

Elipsin Teğetleri

Elipsin bir tanımı: M merkezli r yarıçaplı bir c çemberi ve d(G,M)<r olacak şekilde bir G noktası verilmek üzere, c ve G'den eş uzaklıktaki noktaların geometrik yeri.

Aşağıda tanıma ilişkin bir gösterim verilmektedir:

M(-2000,1500) ve G(8000,1500) noktaları veriliyor. Ayrıca M merkezli ve 15000 yarıçaplı c çemberi veriliyor. c ve G'den eş uzaklıktaki noktaların geometrik yeri e elipsi olsun. Elipsin dışındaki bir P noktasından elipse iki t₁ ve t₂ teğeti çiziliyor. Teğetlerin elipse değme noktaları R ve S olsun.

Kaç farklı P örgü noktası için RPS açısı 45 dereceden büyüktür?

(Project Euler)

Euler Projesi 244. Soru

Kayan Desenler

Muhtemelen On Beş Yapbozunu biliyorsunuzdur. Burada numaralı desenler yerine yedi kırmızı ve sekiz mavi desen var.

Bir hareket, desenin kaydırıldığı yönün (Sol-L, Sağ-R, Yukarı-U, Aşağı-D) baş harfiyle ifade ediliyor, örn. (S) konfigürasyondan başlayarak LULUR dizisi ile (E) konfigürasyona ulaşırız:

(S)

, (E)

Her yol için sağlama toplamı (pseudocode) aşağıdaki gibi hesaplanır:

checksum = 0
checksum = (checksum × 243 + m₁) mod 100 000 007
checksum = (checksum × 243 + m₂) mod 100 000 007
   …
checksum = (checksum × 243 + m_n) mod 100 000 007

Buradaki m_k, hareket dizisindeki k. harfin ASCII değeridir ve hareketler için ASCII değerleri şu şekildedir:

L	76
R	82
U	85
D	68

Yukarıda verilen LULUR dizisi için sağlama toplamı 19761398'dir.

Şimdi, (S) konfigürasyondan başlayarak (T) konfigürasyonuna ulaşmanın en kısa yollarını bulun.

(S)

, (T)

Minimum uzunluğa sahip yollar için tüm sağlama toplamlarının toplamı nedir?

(Project Euler)

Euler Projesi 243. Soru

Direnç

Payı paydasından küçük olan bir pozitif kesre basit kesir denir. Herhangi bir d paydası için d − 1 adet basit kesir olacaktır; örneğin d = 12 için 1/12, 2/12, 3/12, 4/12, 5/12, 6/12, 7/12, 8/12, 9/12, 10/12, 11/12.

Sadeleşmeyen basit bir kesre dirençli kesir adını verelim. Dahası, bir d paydasının R(d) direncini, dirençli kesirlerin basit kesirlere oranı olarak tanımlayalım; örneğin R(12) = 4/11. Aslında d = 12, R(d) < 4/10 direncine sahip en küçük paydadır.

R(d) < 15499/94744 direncine sahip olan en küçük d paydasını bulunuz.

Euler Projesi 242. Soru

Tek Üçlüler

{1,2, ..., n} kümesi verildiğinde f(n, k) değerini, kümenin toplamları tek olan k-elemanlı alt kümelerinin sayısı olarak tanımlarız. Örneğin f(5,3) = 4, çünkü {1,2,3,4,5} kümesinin, tek toplama sahip dört adet 3-elemanlı alt kümesi vardır: {1,2,4}, { 1,3,5}, {2,3,4} ve {2,4,5}.

n, k ve f(n, k) değerlerinin üçü de tek olduğunda, bir [n, k, f(n, k)] tek üçlüsünü oluşturduklarını söyleriz.

n ≤ 10 için tam olarak beş adet tek üçlü vardır: [1,1, f(1,1) = 1], [5,1, f(5,1) = 3], [5,5, f(5,5) = 1], [9,1, f(9,1) = 5] ve [9,9, f(9,9) = 1].

n ≤ 10¹² için kaç tek üçlü vardır?

Euler Projesi 240. Soru

En Yüksek Zar

Beş adet 6-yüzlü zar (1'den 6'ya kadar numaralı) atıldığında  üste gelen en yüksek 3 sayının toplamının 15 olmasının 1111 farklı yolu vardır. Bazıları aşağıdaki gibidir:

D1, D2, D3, D4, D5 = 4,3,6,3,5
D1, D2, D3, D4, D5 = 4,3,3,5,6
D1, D2, D3, D4, D5 = 3,3,3,6,6
D1, D2, D3, D4, D5 = 6,6,3,3,3

Yirmi adet 12-yüzlü zar (1'den 12'ye kadar numaralı) atıldığında en yüksek 10 sayının toplamının 70 olmasının kaç farklı yolu vardır?

Euler Projesi 239. Soru

Yirmi İki Aptalca Asal Sayı

1'den 100'e kadar numaralandırılmış bir dizi disk bir sıra halinde rastgele sıralanıyor.

Tam olarak 22 asal sayılı diskin doğal konumlarından başka yerde bulunacak şekilde kısmi bir bozulmayla sıralanması olasılığı nedir? (Asal sayılı olmayan disklerin herhangi bir kısmı kendi doğal konumlarında veya konumlarının dışında bulunabilir.)

Cevabınızı 0, abcdefghijkl şeklinde 12 ondalık basamağa kadar yuvarlayarak verin.

Euler Projesi 238. Soru

Sonsuz Dizgi Turu

"Blum Blum Shub" sözde rasgele sayı üreteci kullanarak bir sayı dizgisi oluşturun:

s₀=14025256

s_n+1=s_n² mod 20300713

Sonsuz uzunlukta bir w dizgisi oluşturmak için s₀s₁s₂… sayılarını birleştirin. Bu durumda w = 14025256741014958470038053646... olur.

Pozitif bir tamsayı k için, eğer rakamları toplamı k'ya eşit olmayan w'nun bir alt dizgisi yoksa, p(k) sıfır olarak tanımlanır. Eğer rakamları toplamı k'ya eşit olan w'nun en az bir alt dizgisi varsa, p(k) = z'yi tanımlarız; burada z, ilk bu tür alt dizginin başlangıç konumudur.

Örneğin;

1, 14, 1402, … alt dizgilerinin
karşılıklı basamak toplamları 1, 5, 7, … olup
1 pozisyonundan başladığı için p(1) = p(5) = p(7) = … = 1.

4, 402, 4025, … alt dizgilerinin
karşılıklı basamak toplamları 4, 6, 11, … olup
2 pozisyonundan başladığı için p(4) = p(6) = p(11) = … = 2.

02, 0252, … alt dizgilerinin
karşılıklı basamak toplamları 2, 9, … olup
3 pozisyonundan başladığı için p(2) = p(9) = … = 3.

3 konumunda başlayan 025 alt dizgisinin 7'ye eşit bir rakam toplamına sahip olduğuna dikkat edin, ancak 7'ye eşit rakamları toplamı olan daha önce bir alt dizgi (konum 1'den başlayan) vardı, bu nedenle p(7) = 1 değil 3'tür.

0 < k ≤ 10³ için ∑ p(k) = 4742 olduğunu gösterebiliriz.

0 < k ≤ 2·10¹⁵ için ∑ p(k) değerini bulunuz.

Euler Projesi 219. Soru

A ve B bit dizileri olsun (0 ve 1 sayı dizileri). Eğer A, B'nin sol uzunluk(A) bitine eşitse, A'ya B'nin bir öneki denir. Örneğin, 00110 dizisi 001101001 dizisinin bir öneki fakat 00111 veya 100110 dizilerinin öneki değildir.

Herhangi bit dizisinin diğerinin öneki olmadığı n farklı bit dizisi kümesine n boyutlu önek-bağımsız kod adı verilir. Örneğin, $$0000, 0001, 001, 01, 10, 11$$ dizisi 6 boyutlu önek-bağımsız bir koddur.

Şimdi '0' bitini iletmenin maliyeti 1 sent ve '1' bitini iletmenin maliyeti 4 sent olsun. Bu durumda yukarıda verilen önek-bağımsız kodu iletmenin maliyeti 35 sent olur, ki bu aslında belitilen maliyet hesabına göre olası en ucuz maliyetli olanıdır. Yani Cost(6)=35 yazılır.

Bu durumda Cost($10^9$)=?

Euler Projesi 205. Soru

Zar Oyunu

Pelin'in elinde her yüzü 1,2,3,4 sayılarıyla numaralandırılmış 9 adet 4-yüzlü (piramidal) zar var. Cansu'nun elinde ise her yüzü 1,2,3,4,5,6 sayılarıyla numaralandırılmış 6 adet 6-yüzlü (kübik) zar var.

Pelin ve Cansu zarları atıyorlar ve toplamları karşılaştırıyorlar: yüksek olan kazanıyor. Eğer toplamlar eşitse beraberlik oluyor.

Piramidal Pelin'in Kübik Cansu'yu yenme olasılığı kaçtır? Cevabı 7 ondalık basamağa yuvarlayarak veriniz.