Gönderen Konu: Tübitak Avrupa Kızlar Takım Seçme 2019 Soru 6  (Okunma sayısı 557 defa)

Çevrimdışı Arman

  • G.O Sevecen Üye
  • ****
  • İleti: 52
  • Karma: +2/-0
Tübitak Avrupa Kızlar Takım Seçme 2019 Soru 6
« : Ş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.

Çevrimdışı nk6

  • G.O İlgili Üye
  • **
  • İleti: 15
  • Karma: +0/-0
Ynt: Tübitak Avrupa Kızlar Takım Seçme 2019 Soru 6
« Yanıtla #1 : Şubat 28, 2019, 05:01:08 ös »
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.

 


Sitemap 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 
SimplePortal 2.3.3 © 2008-2010, SimplePortal