Project Euler 114

114 epey kısa ama güzel bir Project Euler sorusu; Elimizde n uzunluğunda bir sıra var. Bu sıradaki elemanları siyaha ya da ardışık olarak en az 3 hücre olacak şekilde kırmızıya boyamak istiyoruz, kaç farklı şekilde boyayabiliriz?

Ben şöyle bir yol izledim; \(F(n, k)\) şeklinde bir fonksiyon olsun ve bu fonksiyon \(n\) uzunluğunda ve son \(k\) hücresi kırmızı olan sıraların sayısını tutsun. Fonksiyon için aşağıdakileri yazabiliriz:

  • 3'ten daha kısa kırmızı alt sıra olamayacağından \(F(1, 0) = 1\) ve \(F(2, 0) = 1\). Ayrıca aynı mantıkla tüm \(n\) değerleri için \(F(n, 1) = 0\) ve \(F(n, 2) = 0\).
  • \(F(i, 0) = \sum\limits_{k=0}^{i-1} F(i-1, k)\). Yani, \(n-1\) uzunluktaki herhangi bir sıranın sonuna ancak 1 siyah hücre ekleyerek onu \(n\) uzunlukta ve sıfır kırmızı hücre ile biten bir sıra yapabiliriz.
  • \(n\) uzunlukta ve \(k\) tane kırmızı hücre ile biten sıra sayıları, \(n-k\) uzunlukta ve 0 kırmızı hücre ile biten sıra sayılarına eşittir. Çünkü 0'dan daha fazla kırmızı ile biten sıra sayılarını da dahil edersek, \(k\)'dan daha fazla kırmızı hücre ile biten sıraları da hesaplamış oluruz.

Bu üç maddeye göre \(F(n, k)\) fonksiyonunun değerlerini hesapladığımızda cevap

\[\sum\limits_{i=0}^{50} F(50, i)\]

toplamının sonucu olacak.