Gönderen Konu: Uluslararası Matematik Olimpiyatı 2018 Soru 3  (Okunma sayısı 170 defa)

Çevrimdışı Eray

  • G.O Genel Moderator
  • G.O Demirbaş
  • ******
  • İleti: 318
  • Karma: 5
Uluslararası Matematik Olimpiyatı 2018 Soru 3
« : Temmuz 09, 2018, 07:26:27 ös »
Eşkenar üçgen şeklindeki bir sayı dizilişinde en alttaki satır dışındaki her bir sayı kendisinin hemen altındaki iki sayının farkının mutlak değerine eşitse bu dizilişe bir $\textit{tuhaf Pascal üçgeni}$ diyelim. Örneğin, aşağıda $1$ den $10$ a kadar tüm tam sayıları içeren dört satırlı bir tuhaf Pascal üçgeni gösterilmiştir.
$$4$$ $$2\quad 6$$ $$5\quad 7 \quad 1$$ $$8\quad 3 \quad 10 \quad 9$$
$1$ den $1+2+\cdots+2018$ sayısına kadar tüm sayıları içeren $2018$ satırlı bir tuhaf Pascal üçgeni var mıdır?
Matematik bilimlerin sultanıdır
-Carl Friedrich Gauss

Çevrimdışı nk6

  • G.O Yeni Üye
  • *
  • İleti: 12
  • Karma: 0
Ynt: Uluslararası Matematik Olimpiyatı 2018 Soru 3
« Yanıtla #1 : Temmuz 14, 2018, 06:09:38 ös »
İddia: $n>36$ tam sayısı için $1$ den $1+2+\ldots+n$ sayısına kadar tüm sayıları içeren $n$ satırlı bir tuhaf Pascal üçgeni yoktur. ($n=2018$ için aşağıdaki çözüm çok daha kaba ve basit sınırlarla yapılabilir)

Böyle bir üçgen bulunduğunu varsayalım.

$1, 2, \ldots, n$ sayılarına beyaz sayı diyelim.

Gözlem 1:  Beyaz sayıların hepsi farklı satırlardadır.

İspat: Üçgenin en üstündeki sayıya $a_1$ diyelim. Bu sayının farkı olduğu bir alttaki satırdaki büyük sayıya $b_2$, küçük sayıya $a_2$ diyelim. Benzer şekilde $a_3,\ldots,a_n$ ve $b_3,\ldots, b_n$ tanımlayalım. Şimdi görelim ki

$1+2+\ldots+n\geq b_n=a_1+a_2+\ldots+a_n\geq1+2+\ldots+n$

Dolayısıyla $\{a_1,\ldots,a_n\}=\{1,2,\ldots,n\}$ olmalıdır.

Ayrıca bu demektir ki $b_n=1+2+\ldots+n$ en alt satırda olmak zorundadır.

Şimdi $b_n, b_n-1, \ldots, b_n-n$ sayılarına kırmızı sayı diyelim.

Gözlem 2: $n.$ satırda en fazla $\frac{n}{2}+1$ kırmızı sayı bulunabilir.

İspat: Aksini varsayalım. Bu durumda $n.$ satırda öyle iki yan yana sayı çifti bulunur ki ikisi de kırmızı sayıdır (bu sayı çiftleri çakışabilir, sıkıntı yok) Ayrıca iki kırmızı sayının farkı beyaz sayı olduğundan, bu iki sayı çiftinin farkından gelen bir üst satırdaki sayılar beyaz olacaktır, yalnız birinci gözlemden dolayı bir satırda iki beyaz sayı bulunamaz, çelişki.

Gözlem 3: $n.$ satır haricindeki satırlarda en fazla iki kırmızı sayı bulunabilir.

İspat: Eğer son satır harici bir satırda kırmızı sayı bulunuyorsa, bu kırmızı sayı iki sayının farkı olmak zorundadır. Görelim ki bu iki sayıdan küçük olanı beyaz sayı olmak zorundadır. Bir satırda tam olarak bir beyaz sayı bulunduğundan, bu satırın üst satırındaki kırmızı sayılar bu sayıya çaprazdan komşu olmak zorundadır, dolayısıyla en fazla iki kırmızı sayı bulunabilir.

Gözlem 4: $m.$ satırdaki en büyük sayı $a_m=b_n-a_n-a_{n-1}-\ldots-a_{m+1}\leq b_n-\frac{(n-m)(n-m+1)}{2}$ olur.

İspat: $m.$ satırdaki en büyük sayıyı alıp, bu sayıdan başlayarak bu sayının farkı olduğu iki sayıdan büyük olanı takip edersek her seferinde sayımız bir alt satırdaki en küçük sayı kadar artar. Bu en küçük sayı da en az o satırdaki beyaz sayı olacağından yukarı çıktıkça en büyük sayı bir alt satırdaki beyaz sayı kadar azalır.

Gözlemden dolayı $\frac{(n-m)(n-m+1)}{2}>n$ şartını sağlayan bir $m$ sayısı için $m.$ satır ve üstünde kırmızı sayı bulunamaz. Bu şartı sağlamayan en büyük $m$ tam sayısı için üçgende bulunabilecek kırmızı sayıların sayısı en fazla $\frac{n}{2}+1+2(n-m)$ veya daha az olur, eğer $m>\frac{3n}{4}$ olduğunu gösterirsek tüm kırmızı sayıları yerleştirmeyeceğimizi elde ederiz, bu da böyle bir üçgen olmadığını kanıtlar.

Eğer ifadede $m$ yerine $\frac{3n}{4}+1$ koyduğumuzda sol taraf büyük oluyorsa isteneni elde etmiş oluruz, koyduğumuzda ise

$n^2-4n>32n$ elde ederiz, $n>36$ olduğu için doğrudur, ispat tamamlanır.

Not: Daha uygun bir ispat ile sınır $n>5$ e kadar çekilebiliyor, buradaki makalede ispatı ve bazı tuhaf Pascal üçgenleri sıralanıyor.
« Son Düzenleme: Temmuz 15, 2018, 02:14:07 ös Gönderen: nk6 »

 


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 
SimplePortal 2.3.3 © 2008-2010, SimplePortal