Soru Maratonu 2016 Çözümleri: Soru 3 – Farklı Toplamlar

Soru Maratonu 2016’da sorulan belki de en zor soru diyebileceğimiz Farklı Toplamlar sorusunun çözümünü sizinle paylaşıyoruz.

Tabi önce sorumuza gelelim:

Bir grup pozitif tam sayıyla ilgili şunlar biliniyor:
-Sayıların hepsi farklı ve 100’den küçük.
-Tüm sayı çiftlerinin toplamı farklı.
Bu sayıların toplamı en fazla ne olabilir?

 

Öncelikle fark etmişsinizdir soru oldukça kısa ve anlaşılır görünüyor. Fakat çözümü pek de o kadar kolay değil! Şimdi verilenleri değerlendirelim:

  • Sayılarımızın hepsinin farklı olması zaten toplamlarının en fazla olması için gerekli bir durum, dolayısıyla fazladan verilmiş bir bilgi mevcut diyebiliriz.
  • 100’den küçük olması gereksinimi ise bizi denemek için milyarlarca olasılığa bakmanızı emrediyor ve program için pek de iyi bir durum olmayabilir.
  • Tüm sayı çiftlerinin toplamının farklı olması da kontrol aşamasında her seçtiğimiz sayı kümesi için bakılması ayrı bir sıkıntıyı ortaya çıkartıyor.
  • Tabi bulduğumuz sayılarla belki yukarıdaki şartları sağlıyoruz, fakat bu sayılar en büyük olmayabilir işte asıl sorun burada başlıyor!

İşte bizi en çok kısıtlayan durum bu bulduğumuz kümenin içerisindeki sayıların toplamının en fazla olması durumudur. Bunu optimize etmek için öncelikle programı sizinle paylaşıyoruz. Post’u çok uzatmamak için size bir .txt dosyası hazırladık ve ayrıca pastebin linkini de paylaşıyoruz:

Program iki kısımdan oluşuyor; birinci kısım seçtiğimiz sayı kümelerinin 2’li toplamlarının hepsinin birbirinden farklı olup olmadığı durumunu kontrol etmek ve sayı seçmek. Fakat 100 ile başlayınca pek de bir sonuç ortaya bir anda çıkmıyor, dolayısıyla bu aşamada tümevarım yaklaşımıyla ilk başta daha küçük sayılarla başlayarak nasıl bir düzende sayı kümesi oluştuğunu gözlemleyebiliriz.

100’e kadar olan sonuçlara dikkat ederseniz ilk 4 sayı aslında hiç değişmiyor. Dolayısıyla 4 sayı için seçmeye hiç gerek yok ve programı da bu şekilde değiştirerek 100’e ulaşabiliyoruz. Özellikle oluşan dizilere dikkat ederseniz gelen olarak bir öncekinden bir fazla şeklinde ilerliyor. Tabi bazı yerlerde kırılma noktaları mevcut (Örnek: 28,68,51 vs), fakat bu kırılma noktalarını için de programınızı düzenleyebilirsiniz.

Sonuç itibarıyla, sorunun cevabı olan 879’e ulaşmış bulunuyoruz ve karşımıza 10 ila 100 arasında bu sorunun sorulması durumunda tüm sonuçlar ortaya çıkmış oluyor. Tabi bu soruyu daha çok şekillendirerek ileride daha zorları ve çeşitli versiyonlarının sorulması mümkün olmakla birlikte (örneğin daha büyük bir sayı, daha 2’li toplamlar yerine 3’lü, 4’lü toplamlar vs.) sadece programlama bilmenin bu soruyu çözmeye yetmeyeceğini de ifade etmeye çalıştık. Çünkü sadece programlamayla bu soruyu çözmek kodu çalıştırırsanız göreceksiniz, hiç de o kadar kolay olmayacak ve günler alabilecek sonuçlar olabilmektedir. Yukarıda da bahsettiğim tümevarım ile yapılan işlemi hızlandırarak ancak doğru sonuca hızlı bir şekilde ulaşmak mümkündür.

Bir de not etmek gerekir ki bu soruya çok benzer bir soru Oyun 2016 yarışmasında sorulmuş olup çok daha basit halidir.