Keloğlan’ın Cüceler İçin Düzenlediği Orman Gezileri Sorusunun Çözümü

Cevap: 7

Keloğlan orman gezilerini en uzun süreli olandan en kısa süreli olana doğru (yani ilk olarak süresi 64 saat, ikinci olarak süresi 63 saat, …, son olarak süresi 1 saat olan orman gezisini) oylamaya sunarsa süreleri 64 saat, 63 saat, 61 saat, 57 saat, 49 saat, 33 saat ve 1 saat olan 7 gezi iptal edilmemiş olup bunların dışında kalan 57 gezinin tamamı iptal edilecektir.

Şimdi de iptal edilmemiş orman gezisi sayısının 7’den daha fazla olamayacağını gösterelim. Tüm oylamalar yapıldıktan sonra iptal edilmemiş gezileri daha uzun süresi olan gezilerden daha az süresi olan gezilere doğru 1, 2, . . ., m olarak numaralandıralım. Bu gezilere katılacak cüce sayıları sırasıyla X₁, X₂, _{. . .,} X_m olsun.

1 numaralı yani süresi 64 saat süren gezi iptal edilemeyeceğine göre X₁ = 1.

Bu geziler iptal edilmediklerine göre her 1 ≤ s  indisi için:

X_s ≥ X_s-1 + X_s-2 + ∙ ∙ ∙ + X₁ olacaktır.

Buna göre

64 = X_m + X_m-1 + X_m-2 + ∙ ∙ ∙ + X₁ ≥ 2 (X_m-1 + X_m-2 + ∙ ∙ ∙ + X₁) ≥ 4 (X_m-2 + X_m-3 + ∙ ∙ ∙ + X₁) ≥ ∙ ∙ ∙ ≥ 2^m-1 X₁ = 2^m-1 olur.

Sonuçta m ≤ 7 elde edilir.