Project Euler 121

Bugün, 300 küsur gün sonra ProjectEuler’e bir bakayım dedim. “Unlucky Squares” denen rozeti de almak için 121. soruyu çözmeye çalıştım.

Soruda rastgele diskleri bir torbadan çektiğimiz bir oyun var. Başlangıçta torbada 1 kırmızı 1 de mavi disk var. Her elde torbadan rastgele bir disk seçip torbaya geri atıyoruz. Bunun dışında, her adımda torbaya bir tane de kırmızı disk atıyoruz. Önceden belirlenen kadar adım sonra eğer çektiğimiz mavi toplar kırmızılardan fazlaysa kazanıyoruz. Her oyuncunun oyuna girmeden önce 1£ verdiğini düşünürsek, kazanan oyuncunun ödülü ne kadar olmalı ki kasa zarar etmesin?

Kağıt üzerinde hesabı şöyle; ilk adımda 2 olasılık var, sonrasında bu 3, 4, ..., n olarak artıyor. Her seferinde sadece 1 mavi top olduğu için n el sonunda k kez mavi top çekme olasılığı

(1)   \begin{equation*} S(n, k) =\frac{1^k F(n, n - k)}{(n+1)!} \end{equation*}

olacak. Burada F(a, b), 1’den a‘ya kadar olan tamsayıların bulunduğu kümedeki b elemanlı altkümelerin elemanları çarpımının toplamı oluyor. Böyle bir fonksiyona ihtiyaç duymamızın sebebi ise, farklı adımlarda kırmızı çekme olasılığının, torbaya her seferinde bir kırmızı disk daha eklediğimiz için değişmesi (artması). Mesela 3 adımlı oyun sonunda 2 defa kırmızı çektiğimiz durumlar

M-K-K, K-M-K, K-K-M

olabilir. İlk durumun olasılığı

(2)   \begin{equation*} \frac{1}{2}\frac{2}{3}\frac{3}{4} = \frac{1}{4} \end{equation*}

iken ikinci durumun olasılığı

(3)   \begin{equation*} \frac{1}{2}\frac{1}{3}\frac{3}{4} =\frac{1}{8} \end{equation*}

üçüncü durumun ise

(4)   \begin{equation*} \frac{1}{2}\frac{2}{3}\frac{1}{4} =\frac{1}{12} \end{equation*}

olacaktır.

Bunu adım adım hesaplamaktansa kapalı bir formülü var mıdır diye araştırırken Quora’da bu sonucu Stirling Sayıları benzeri bir yöntem ile hesaplayabileceğimi öğrendim. F(a, b) sayısını iki kısımda hesaplayabilirim;

a-1 elemanla oluşturulmuş b elemanlı sonuçlar.

a-1 elemanla oluşturulmuş b-1 elemanlı sonuçlar.

İlk kısım olduğu gibi alınabilir. 2. kısım’daki tüm kümelere a elemanını eklersek bu kümeleri de sonuca ekleyebiliriz. 2. kısımdaki sonuç a F(a-1, b-1) olacaktır. Böylece F(a, b)

(5)   \begin{equation*} F(a, b) = F(a-1, b) + a F(a-1, b-1) \end{equation*}

olacaktır.

Oyuna geri dönersek, tüm olasılıklar içinde oyuncunun kazanacağı oyunların sayısını bu yöntemle basitçe hesaplayabiliriz. Sonrasında hesaplamamız gereken nokta ise ödülün ne kadar olması gerektiği. n adım sonrası oyuncunun kazanma olasılığına x diyelim. y de ödül olmak üzere şu eşitliği yazabiliriz;

(6)   \begin{equation*} x(y-1) - (1-x) = 0 \end{equation*}

x‘i daha önce hesapladığımıza göre y de kolayca hesaplanabilir.

Soruyu çözen kod aşağıdaki gibi