Geomania.Org Forumları
Yarışma Soruları => Tübitak Avrupa Kızlar Takım Seçme => 2019 => Konuyu başlatan: Arman - Şubat 27, 2019, 07:02:37 ös
-
Başlangıçta masa üzerindeki $k$ öbekte toplam $2019$ boncuk bulunuyor. Her işlemde bir öbek seçilip iki öbeğe bölünüyor ya da masadan kaldırılıyor. Her başlangıç durumu için birkaç işlem sonucunda masada birbirinden farklı sayıda boncuk içeren $k$ öbek oluşturulabiliyorsa, $k$ nin alabileceği en büyük değeri bulunuz.
-
Cevap: $45$
Eğer başlangıç durumunda hepsindeki taş sayısı en fazla $45$ olan $n\geq 46$ sayıda öbek varsa, son durumda da herhangi bir öbekte en fazla $45$ taş bulunacağından farklı sayılarda taş içeren $n$ öbek oluşturulamaz.
Şimdi tümevarım ile toplamda tam $n^2-n+1$ sayıda taş içeren $n$ öbekten $1,2,\ldots, n$ öbeklerini oluşturabileceğimizi gösterelim.
$n=1,2$ için doğru olduğu kolaylıkla görülebilir. $n=k$ için doğru olsun, $n=k+1$ için inceleyelim.
Elimizdeki $k+1$ öbekte toplam $k^2+k+1 > k(k+1)$ taş bulunduğundan en az bir öbekte en az $k+1$ taş bulunacaktır. Bu öbeği $k+1$ ve kalanlar olmak üzere iki öbeğe ayırıp $k+1$ taş içeren öbeği kenara koyalım.
Şimdi elimizde toplam $k^2$ taş içeren $k+1$ öbek var. Eğer bu öbeklerden en küçüğünü attığımızda elimizde hala en az $k^2-k+1$ taş kalıyorsa (fazlalıkları kolayca atabiliriz) tümevarım varsayımından ispatı bitirmiş oluruz.
Yani en fazla $k-1$ taş içeren bir öbek varsa ispat biter. Aksini varsayalım, o zaman bir önceki durumda elimizde toplam en az $k(k+1) + (k+1)$ taş olurdu, çelişki.
Şimdi toplam $2019$ taş içeren öbeklerden her adımda $m>1$ sayıda eleman içeren bir öbeği alıp $m-1$ ve $1$ olarak ayırıp küçük olanı atarak $45^2-45+1=1981$ taş bulunan bir duruma getirebiliriz. Buradan sonra ise yaptığımız tümevarım soruyu bitirir.