Tübitak Lise 2. Aşama - 2017 Çözümleri

Söz konusu grup $\{ A_1, A_2, \ldots , A_k \}$ olsun.

İddia 1: Buradan sadece $A_1$ i içeren bir uygun davetli listesi vardır.

Aksini varsayalım. O zaman $A_1$ i içeren her uygun davetli listesinde bu kamber grubundan başka bir eleman daha bulunur. Öyleyse $\{ A_2, \ldots, A_k\}$ de bir kamber grubudur, çelişki.

Bu davetli listesi $\{ A_1, B_1, \ldots , B_l\}$ olsun.

İddia 2: Bu davetli listesinden sadece $A_1$ in sevdiği en az bir yemek vardır.

Aksini varsayalım. O zaman $A_1$ in sevdiği her yemek için bu yemeği seven bir $B_i$ bulunur. Bu durumda $\{B_1, \ldots , B_l\}$ uygun davetli listesidir, ama kamber grubunda bu listeden eleman yok, çelişki.

Bu yemekler $Y_1, Y_2, \ldots, Y_m$ olsun.

İddia 3: Bu yemeklerden öyle biri vardır ki, verilen kamber grubu dışındakilerden o yemeği seven yoktur.

Aksini varsayalım. Her $Y_i$ yemeği için bu yemeği seven bir $C_i$ vardır (bunlar aynı kişi olabilir), o zaman $C_i$ lerin birleşimi ile $B_j$ leri içeren davetli listesi uygundur, ama kamber grubunda bu listeden eleman yok, çelişki.

Bu yemeklerden biri $Y$ olsun.

İddia 4: $A_i$ lerin tümü $Y$ yi sever.

Aksini varsayalım, $A_i$ $Y$ yi sevmiyor olsun. Kamber grubundan sadece $A_i$ yi içeren uygun davetli listesi $\{ A_i, D_1, \ldots , D_n\}$ ye bakalım. $D_i$ lerden hiçbiri $Y$ yi sevmez, $A_i$ de $Y$ yi sevmediğinden bu davetli listesi uygun değildir, çelişki.

İddianın soruyu bitirdiği açıktır.

Genelliği bozmadan $B$ ve $D$, $X$ e yakın olan köşeler olsun. $A$, $B$, $D$ merkezli çemberlerin kuvvet merkezi $T$ olsun. $T$ den $AB$ ye inilen dik ayağı $U$, $CD$ ye inilen dik ayağı $V$ olsun.

$|TA|^2-r_1^2 = |TB|^2-r_1^2 \Rightarrow |TA| = |TB| \Rightarrow |UA| = |UB|$

$|XB|\cdot |XA| = (|XU|-|UB|)\cdot (|XU|+|UA|) = |XU|^2-|UA|^2=|TX|^2-|TA|^2$

Diğer yandan $|TA|^2-r_1^2=|TD|^2-r_2^2$

Birleştirip yerine yazarsak,

$|TX|^2-|TD|^2=|XC|\cdot |XD|$

Diğer yandan $|TX|^2-|TD|^2 = |XV|^2-|VC|^2 = (|XV|-|VC|)\cdot (|XV|+|VC|) = (|XV|-|VC|)\cdot |XC|$

Birleştirirsek $|VD|=|VC| \Rightarrow |TC|=|TD|$

Dolayısıyla $T$ $A$,$B$,$C$,$D$ merkezli çemberlerin kuvvet merkezidir. $PQ$ $A$ ve $C$ merkezli, $RS$ $B$ ve $D$ merkezli çemberlerin kuvvet ekseni olduğundan $T$ den geçer ve $|TR|\cdot |TS|=|TP|\cdot |TQ|$  $T$ nin bu çemberlere göre kuvvetine eşittir.

Dolayısıyla $PQRS$ çemberseldir, q.e.d

$n$ üzerinden tümevarım yapalım.

$n=1,2$ için ifadenin $1$ e eşit olduğu kolayca görülür.

$n=k-1$ için doğru olsun, $n=k$ için doğruluğunu gösterelim.

$d_i=a_{1i}+\ldots +a_{(k-1)i}$ olsun.

$1\leq i \leq k-1$ için $\frac{1}{c_i}=\frac{1}{d_i+a_{ki}}=\frac{a_{ik}}{d_i\cdot a_{ik} + 1}$

$e_i=\frac{1}{d_i}$ tanımlayıp yerine yazarsak $1\leq i \leq k-1$ için

$\frac{1}{c_i}=\frac{a_{ik}\cdot e_i}{a_{ik} + e_i}$ ve $\frac{1}{c_k}=\frac{1}{a_{ik}+\ldots + a_{(k-1)k} + 1}$ olmak üzere

$\frac{a_{1k}\cdot e_1}{a_{1k} + e_1}+\ldots +\frac{a_{(k-1)k}\cdot e_{k-1}}{a_{(k-1)k} + e_{k-1}}+\frac{1}{a_{1k}+\ldots + a_{(k-1)k} + 1}\leq 1$ olduğunu göstermek yeterlidir. Bu da

$\frac{a_{1k}\cdot e_1}{a_{1k} + e_1}+\ldots +\frac{a_{(k-1)k}\cdot e_{k-1}}{a_{(k-1)k} + e_{k-1}}\leq\frac{a_{1k}+\ldots + a_{(k-1)k}}{a_{1k}+\ldots + a_{(k-1)k} + 1}$ olmasına denktir.

Lemma: $\frac{a_1\cdot b_1}{a_1 + b_1}+\frac{a_2\cdot b_2}{a_2 + b_2}\leq\frac{(a_1 + a_2)\cdot (b_1 + b_2)}{(a_1+a_2)+(b_1+b_2)}$

Lemmayı ispatlamak için ifadeyi açıp düzenlersek $2a_1a_2b_1b_2\leq (a_1b_2)^2 + (a_2b_1)^2$ elde ederiz ki doğrudur.

Lemmayı tekrarlı bir şekilde kullanırsak

$\frac{a_{1k}\cdot e_1}{a_{1k} + e_1}+\ldots +\frac{a_{(k-1)k}\cdot e_{k-1}}{a_{(k-1)k} + e_{k-1}}\leq\frac{(a_{1k}+\ldots + a_{(k-1)k})\cdot (e_1+\ldots + e_{k-1})}{(a_{1k}+\ldots + a_{(k-1)k})+(e_1+\ldots + e_{k-1})}$ elde ederiz.

Son olarak $\frac{(a_{1k}+\ldots + a_{(k-1)k})\cdot (e_1+\ldots + e_{k-1})}{(a_{1k}+\ldots + a_{(k-1)k})+(e_1+\ldots + e_{k-1})}\leq\frac{a_{1k}+\ldots + a_{(k-1)k}}{a_{1k}+\ldots + a_{(k-1)k} + 1}$ olduğunu gösterelim.

Taraf tarafa çarpıp düzenlersek, ifade $e_1+\ldots e_{k-1}\leq 1$ olmasına denktir ki tümevarım varsayımından doğrudur, q.e.d

$i)$ $n$ tek ise, $m=n$ ve $k=2n$ için şartın sağlanacağı açıktır.

$ii)$ $n$ çift ise, $n$'nin en büyük asal böleni $p$ olsun.

$iia)$ Her $q<p$ asal sayısı için $q\vert n$ ise $p$'den büyük en küçük asal sayı $r$ olsun. $p<r<2p$'dir.(Bertrand Postulatı) Dolayısıyla $r-1$ sayısının tüm asal bölenleri $p$'den küçüktür veya eşittir ve $n$'yi böler.$k=n\cdot r$ ve $m=n\cdot (r-1)$ seçersek, $d(k)=d(n)+1$ ve $d(m)=d(n)$ bulunur yani şart sağlanır.

$iib)$ En az bir $q<p$ asal sayısı için $q \nmid n$ ise,  $n$'yi bölmeyen en küçük asal $r$ olsun, $r<p$'dir. $r-1$'in tüm asal bölenleri $n$'yi böler.Eğer $k=n\cdot r$ ve $m=n\cdot (r-1)$ seçersek, $d(k)=d(n)+1$ ve $d(m)=d(n)$ bulunur yani şart sağlanır.

İfadenin minimum değerini almasını sağlayan diziye bakalım.

İddia 1: Bu dizi için sözü geçen alt dizideki $25$ pozitif tam sayı $1, 2, \ldots , 25$ tir.

Aksini varsayalım. Sayılar $a_1,\ldots , a_{25}$ olsun.

$a_1>1$ ise $x_1, x_2,\ldots x_{2017}$ yerine $(x_1-1), (x_2-1),\ldots , (x_{2017}-1)$ yazarsak $x_i\cdot (x_i-x_{i-2})$ teriminde $x_i$ azalır, $(x_i-x_{i-2})$ ise azalır veya sabit kalır, $(x_i-x_{i-2})\neq 0$ olan en az bir $i$ olduğundan ifadeye daha küçük bir değer aldıran bir dizi elde ederiz, çelişki.

$a_i>a_{i-1}+1$ olan en küçük $i$ ye bakalım. Benzer şekilde $a_i,\ldots , a_{25}$ e eşit olan sayıları bir eksikleriyle değiştirirsek  ifadeye daha küçük bir değer aldıran bir dizi elde ederiz, çelişki.

Gözlem: Bir sayı dizide ikiden fazla geçiyorsa fazlalıkları atabiliriz.

$a_i=a_{i+1}=\ldots=a_{i+k}=m$ olsun.

$a_{i+2}\cdot (a_{i+2}-a_i)=\ldots=a_{i+k}\cdot (a_{i+k}-a_{k-2})=0$,

$a_{i+k+1}\cdot(a_{i+k+1}-a_{i+k-1})=a_{i+k+1}\cdot(a_{i+k+1}-a_i)$ ve

$a_{i+k+2}\cdot(a_{i+k+2}-a_{i+k})=a_{i+k+2}\cdot(a_{i+k+2}-a_{i+1})$ olduğundan diziden $a_{i+2}, \ldots , a_{i+k}$ yi çıkardığımızda ifade değişmez. (dizi hala şartları sağlar)

Bu da demektir ki elimizde kalan $y_0, \ldots , y_n$ dizisi $1, 2,\ldots , 25$ sayılarının bir veya iki kere geçtiği bir dizidir.

İddia 2: $25$ sayısı dizide tam bir kere geçer, yani sadece $y_n$ terimi $25$ e eşittir.

Aksini varsayalım. Son dört terim $y_{n-3}, 24, 25, 25$ olsun. Bu dizinin yerine $y_{n-3}, 24, 25$ ile biten diziye bakarsak ifade $25$ azalır, yani ifadeye daha küçük bir değer aldıran bir dizi elde ederiz, çelişki.

İddia 3: $1, 2,\ldots , 24$ sayıları dizide iki kez geçer.

Aksini varsayalım. Dizide iki kez geçmeyen ilk sayı $a$ olsun. Dizinin $a$ yı içeren kesiti $a-1, a-1, a, a+1$ olmak üzere bunun yerine $a-1, a-1, a, a, a+1$ i içeren diziye bakarsak ifadeden $(a+1)\cdot ((a+1)-(a-1))=2a+2$ çıkarıp $a\cdot (a-(a-1))+(a+1)\cdot ((a+1)-a)=2a+1$ eklemiş oluruz, yani ifadeye daha küçük bir değer aldıran bir dizi elde ederiz, çelişki.

Dolayısıyla dizimiz $1, 1, 2, 2, \ldots , 24, 24, 25$ olur ve toplam $2+2+3+3+\ldots +24+24+25=623$ olur.

$x_0, x_1, \ldots , x_{2017}$ dizisi ise $1, 2, \ldots , 24$ sayılarını en az iki kere içeren, $25$ sayısını tam bir kere içeren herhangi bir dizidir. Bu dizilerin sayısı ise $b$ sayısının dizide geçme sayısı $u_b\geq 2$ ve $v_b=u_b-2\geq 0$ olmak üzere $v_1+\ldots + v_{24}=2017-2\cdot 24=1969$ denkleminin çözüm sayısıdır, bu da bilindik bir şekilde $\binom{1992}{23}$ olur.