Tübitak Lise 2. Aşama - 2004 Çözümleri
« 2003 2005 »
« Sorulara Git
Geri

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

1
$m(\widehat{B})>m(\widehat{C})$ olan bir $ABC$ üçgeninde, $A$ köşesine ait yükseklik, açıortay ve kenarortayın ayakları, sırasıyla, $H$, $L$ ve $D$ noktalarıdır. $m(\widehat{HAL})=m(\widehat{DAL})$ olması için gerek ve yeter koşulun, $m(\widehat{BAC})=90^{\circ}$ olması olduğunu gösteriniz.
Çözüm:
İddia:
$\angle HAL=\angle DAL$  ise $\angle BAC={90}^{\circ }$


$AL$ açıortay olduğu için $\angle BAH=\angle CAD$.
$[AD$, $\triangle ABC$ nin çevrel çemberini $E$ de kessin. $\angle ABH={90}^{\circ }-\angle BAH=\angle AEC$ ve $\angle AEC+\angle EAC={90}^{\circ }$ olduğu için $AE$ çevrel çemberin çapıdır. Çemberin merkezi hem $BC$ nin orta dikmesi üzerinde, hem de $AE$ üzerinde olacak. $AE$ doğrusu ile $BC$ doğru parçasının orta dikmesi $D$ noktasında kesişir. O halde $D$, çevrel çemberin merkezi, yani, $\angle BAC={90}^{\circ }$.

İddia:
$\angle BAC={90}^{\circ }$ ise $\angle HAL=\angle DAL$

$\angle ACB=\angle DAC=\angle BAH$ ve $AL$ açıortay olduğu için $$\angle HAL=\angle LAB-\angle BAH=\angle LAC-\angle DAC=\angle DAL$$ elde edilir.
Bu durumda $\angle HAL=\angle DAL\Leftrightarrow \angle BAC={90}^{\circ }$.

Not:
Bir açının köşesinden geçen bir doğrunun, o açının açıortayına göre simetriğine o doğrunun izogonal eşleniği denir. Özel olarak, kenarortayın izogonal eşleniğine kenarortaysı denir. Bir üçgende yüksekliğin izogonal eşleniği, çevrel çemberin merkezinden geçer. Dik üçgende hipotenüse ait yükseklik, hipotenüse ait kenarortaysıdır.

Bu soru Ulusal Matematik Olimpiyatı 1. Aşama - 2012'de de soruldu.
2
Bir ülkedeki $80$ kentten bazıları arasında karşılıklı uçak seferleri yapılmaktadır. Her kentten en az $7$ başka kente doğrudan uçak seferi bulunmakta olup, herhangi bir kentten bir diğerine doğrudan ya da sonlu sayıda aktarma yaparak uçakla ulaşmak mümkündür. Karşılıklı uçak seferleri hangi kentler arasında düzenlenmiş olursa olsun, herhangi bir kentten bir diğerine en çok $k$ aktarmayla ulaşılmasını olanaklı kılan en küçük $k$ sayısını bulunuz.
Çözüm:
(Burak VARICI)

Bunu mümkün kılan en küçük $k$ sayısı $26$ dır.

$80$ kentimizi $80$ köşeli bir grafın köşeleri ve karşılıklı uçak seferlerini de bu köşeler arasındaki yönlü kenarlar olarak düşünelim. $k$ aktarma ile, yani grafımızı düşünürsek en fazla $k+1$  kenar üzerinden herhangi bir köşeden başka bir köşeye her zaman ulaşılmasını sağlayan en küçük $k$'yı arıyoruz. Ayrıca her köşenin derecesinin en az $7$ olduğunu biliyoruz.

Öncelikle $k=26$ aktarma için bir örnek verelim: $K_{m} $ ile $m$ köşeli bir complete grafı gösterelim. Eğer her $v_{1} \in K_{i} $, $K_{j} $deki köşelerden her birine direkt bağlı ve her $v_{2} \in K_{j} $, $K_{i} $ deki köşelerden her birine direkt bağlı ise bu durumu $K_{i} \leftrightarrow K_{j} $ ile gösterelim. Dolayısıyla eğer $K_{i} \leftrightarrow K_{j} $ ise bu $i+j$ köşe bir  $K_{i+j} $ oluşturur.

Grafımız şu şekilde olsun:   $\underbrace{K_{5} \leftrightarrow K_{3} }_{8 \text{ Köşe} }\leftrightarrow \underbrace{K_{3} \leftrightarrow K_{2} \leftrightarrow K_{3} }_{8 \text{ Köşe} }\leftrightarrow \underbrace{K_{3} \leftrightarrow K_{2} \leftrightarrow K_{3} }_{8 \text{ Köşe} }\leftrightarrow \dots\leftrightarrow \underbrace{K_{3} \leftrightarrow K_{2} \leftrightarrow K_{3} }_{8 \text{ Köşe} }\leftrightarrow \underbrace{K_{3} \leftrightarrow K_{5} }_{8 \text{ Köşe} }$ Aradaki  $K_{3} \leftrightarrow K_{2} \leftrightarrow K_{3} $ üçlülerinden $8$ tane olsun. Dolayısıyla toplamda $80$ köşe vardır ve her köşenin derecesi en az $7$ dir.


Diğer taraftan en soldaki  $K_{5} $ teki bir köşeden başlarsak, en sağdaki  $K_{5} $ e en az $27$ kenar üzerinden yani $26$ aktarma ile gidebiliriz. Ayrıca bu grafta belirtilen kenar bağlantıları dışında bir kenar da olmasın. Şimdi $27$ nin maksimum olduğunu ispatlayalım.

Grafımızı bir ağaç şeklinde ifade edeceğiz. Bir $V$ köşesi seçelim ve ağacın en tepesine koyalım. $V$ nin bir alt katmanına $V$ nin direkt bağlı olduğu köşeleri yerleştirelim. Ondan sonra gelen her $k.$ katmana, $1,2,..,(k-1).$ katmanlarda bulunmayan ve $(k-1).$katmandaki   köşelerden en az birine direkt   bağlı olan köşeleri yerleştireceğiz. Grafımızın sonlu sayıda köşesi olduğundan, sonlu sayıda katman yer alır.

Toplam m katman olsun.  $t.$ katmanda da  $a_{t} {\rm \; }(1\le t\le m)$ alsın. Grafımız bağlantılı olduğundan bu "katmanlandırma''   tüm köşeleri kapsar.

Dolayısıyla $a_{1} +a_{2} +..+a_{m} =80$ ve $l.$ katmandaki bir köşenin direkt bağlı olduğu köşeler sadece $l.{\rm \; ,}(l-1).$ veya $(l+1).$ katmanlarda yer alabilir. 

Fakat bir $v_{1} \in l.$katman alırsak, $7\le der(v_{i} )\le (a_{l} -1)+a_{l-1} +a_{l+1} $ olduğundan her $m-1\ge l\ge 2$  için $a_{l-1} +a_{l} +a_{l+1} \ge 8$ olmalıdır.

Ayrıca benzer mantıkla $a_{1} +a_{2} \ge 8$ ve $a_{m-1} +a_{m} \ge 8$ olduğunu söyleyebiliriz. $m\le 28$ olduğunu göstermek istiyoruz,  çünkü böylece $V$'den herhangi bir köşeye en fazla  $m-1\le 27$  kenar kullanılarak ve dolayısıyla $26$ aktarmada ulaşılmış olacak.

Aksini varsayalım, $m>28$ olsun. Her $r$ için $a_{r} >0$ olduğundan :  $$\begin{array}{l}
80=a_{1} +a_{2} + \dots +a_{m} \\
=(a_{1} +a_{2} )+(a_{3} +a_{4} +a_{5} )+\dots+(a_{24} +a_{25} +a_{26} )+(a_{27} +a_{28} +..a_{m-2} ) +(a_{m-1} +a_{m} ) \\
>(a_{1} +a_{2} )+(a_{3} +a_{4} +a_{5} )+\dots+(a_{24} +a_{25} +a_{26} )+(a_{m-1} +a_{m} ) \\
\ge 8+8+ \dots +8=80.
\end{array}$$

Böylece çelişki elde ederiz. Demek ki $m\le 28$ ve dolayısıyla${\rm \; }m-1\le 27$ bulunur.

Dolayısıyla en fazla $26$ aktarma ile istenilen yere ulaşılır. $\triangleright $
3
Çözüm:
(Eren DURLANIK)

  • $n=7$ için $n^2-1=,2^43^1$  olur ve pozitif bölenleri sayısı $10$ olur.
    $n=235$  için $n^2-2=7^4{23}^1$  olur ve pozitif bölenleri sayısı $10$ olur.
    $n=4936$  için $n^2-3={37}^4{13}^1$  olur ve pozitif bölenleri sayısı $10$ olur.
  • Genelliği bozmadan $n$  yi pozitif kabul edelim. $n^2-4$ ün pozitif bölen sayısının $10$ olması için, $p$  ve $q$ birbirinden farklı asal sayılar olmak üzere  $n^2-4=p^9$  veya $n^2-4=p^4q$  olmalıdır.
    • $n^2-4=p^9$  sağlanıyorsa:
      $(n-2)(n+2)=p^9$  olur. $n+2>1$  olduğundan $p|n+2$ olmalıdır. Eğer $p|n-2$ ise $p|4$  olur. Öyleyse $p=2$ dir ve $n^2=2^9+4$ sağlanır, ki bu durumda $n$  tamsayı olamaz. Eğer $p\nmid n-2$ ise $n-2=1$ yani $n=3$ olur. Dolayısıyla $p^9=5$ bulunur ve p tamsayı olamaz. Yani $n^2-4=p^9$  un çözümü yoktur.
    • $n^2-4=p^4q$  sağlanıyorsa:
      $(n-2)(n+2)=p^4q$  olur. $(n-2,n+2)=d$  olsun. $d\ne 1$  ise $d^2|p^4q$  olacağından,$p|d$  olmalıdır. Öyleyse $p|n-2$,  $p|n+2$ ve dolayısıyla $p|4$ yani $p=2$ elde ederiz.  Yani $(n-2)(n+2)=16q$  olmalıdır. $4\nmid n-2$  olsaydı $4\nmid n+2$ ve $16\nmid (n-2)(n+2)$ olurdu ve çelişki elde ederdik. $4|n-2$  ve $4|n+2$ olmalıdır. Öyleyse $n-2=4,\ n+2=4q$  ya da $n-2=4q,\ n+2=4$ olmalıdır. İki durumdan da çözüm gelmediği barizdir. Demek ki $d=1$ sağlanmalıdır. Bu durumda $n-2=p^4,\ n+2=q$  yada $n-2=q,\ n+2=p^4$  olmalıdır. İlk olarak   $n-2=p^4,\ n+2=q{\rm \ \ }$  durumunu inceleyelim. $p^4+4$  asal olmalı; fakat $p^4+4=(p^2-2p+2)(p^2+2p+2)$  olduğundan $p^2-2p+2=1$ olmalı ve $p=1$ bulunur, yani bu durum mümkün değildir. Şimdi de $n-2=q,\ n+2=p^4$  durumunu inceleyelim. $p^4-4$  asal olmalı; fakat $p^4-4=(p^2-2)(p^2+2)$  olduğundan $p^2-2=2$ olmalı ve buradan da çözüm gelmez.
    Sonuç olarak, $n^2-4$ ün hiçbir zaman $10$ pozitif böleni olamaz.


4
$\mathbb{Z}$ tam sayılar kümesini göstermek üzere, tüm $m,n \in \mathbb{Z}$ için, $ f(n)-f(n+f(m))=m$ koşulunu sağlayan bütün $f:\mathbb{Z}\to \mathbb{Z}$ fonksiyonlarını bulunuz.
Çözüm:
(Burak VARICI)

Cevap: Bu şartı sağlayan hiç $f:{\mathbb Z}\to {\mathbb Z}$ fonksiyonu yoktur.

$P(m,n)$ ile $f(n)-f(n+f(m))=m$ denklemini ifade edelim.
Varsayalım bir $a,b\in {\mathbb Z}$ikilisi için $f(a)=f(b)$ sağlansın. Sırasıyla $P(m,a)$ ve $P(m,b)$ ye bakarsak $a=f(n)-f(n+f(b))=f(n)-f(n+f(b))=b$ ve dolayısıyla $a=b$ bulunur. Demek ki $f$ fonksiyonu birebirdir.

$P(0,0):f(0)-f(f(0))=0 \Rightarrow {\rm \; }f(0)=f(f(0))$.  Fonksiyon birebir olduğundan $f(0)=0$ buluruz. $$P(m,0): f(0)-f(f(m))=m  \Rightarrow f(f(m))=-m{\rm \; }\dots(*)$$
$(*)$'ı kullanarak $P(f(m),n)$ i incelersek:
$f(n)-f(n+f(f(m))=f(n)-f(n-m)=f(m)$ $\Rightarrow {\rm \; }f(n)=f(m)+f(m-n)$ elde ederiz.  $a=n-m{\rm \; },{\rm \; }b=m$ şeklinde bir dönüşüm yaparsak:

$f(a+b)=f(a)+f(b)$, $\forall a,b\in {\mathbb Z}$. Yani fonksiyon Cauchy Eşitliği'ni sağlar.
Bu durumda $f(1)=c$ olmak üzere fonksiyon $f(x)=cx$ biçiminde olmalıdır.
Bunu ilk denklemde yerine yazarsak:
$cn-c(n+cm)=m{\rm \; \; }\Rightarrow {\rm \; }cm^{2} =-m$ bulunur. Fakat bu da $m\ne 0$ için $c^{2} =-1$ demektir, bu durum $c$'nin tamsayı olmasıyla çelişir.

Dolayısıyla böyle bir $f:{\mathbb Z}\to {\mathbb Z}$ fonksiyonu yoktur. $\triangleright $
5
Bir $ABC$ üçgenin, $[BC]$ kenarına ait dışteğet çemberinin, $ BC$, $CA$ ve $AB$ doğrularına değme noktaları, sırasıyla, $A_{1} $, $B_{1}$ ve $C_{1}$; $\lbrack CA\rbrack $ kenarına ait dışteğet çemberinin, aynı doğrulara değme noktaları, yine sırasıyla, $A_{2}, B_{2}$ ve $C_{2}$; $[AB]$ kenarına ait dışteğet çemberinin, aynı doğrulara değme noktaları, yine sırasıyla, $A_{3}$, $B_{3}$ ve $ C_{3}$ olsun. $A_{1}B_{1}C_{1}$, $A_{2}B_{2}C_{2}$ ve $ A_{3}B_{3}C_{3}$ üçgenlerinin çevrelerinin toplamının, $ABC$ üçgeninin çevrel çemberinin yarıçapına oranının alabileceği en büyük değeri bulunuz.
Çözüm:
(Burak VARICI)

Cevap: Bu oranın alabileceği en büyük değer $9+\dfrac{9\sqrt{3} }{2} $ dir ve eşitlik eşkenar üçgen için sağlanır.


$a,b,c$ ile üçgenin kenar uzunluklarını ve $\alpha ,\beta ,\gamma $ ile de iç açıları gösterelim. $s$ ile $\triangle ABC$ nin yarıçevresi, her $\triangle XYZ$ üçgeni için de $\text{Ç}\left (XYZ\right )$ ile üçgenin çevresi belirtilsin.

$M=\dfrac{Ç\left (A_{1} B_{1} C_{1} \right )+Ç\left (A_{2} B_{2} C_{2} \right )+Ç\left (A_{3} B_{3} C_{3} \right )}{R} $ olsun. $M$ nin alabileceği en büyük değeri bulmaya çalışıyoruz.

İlk olarak $a+BC_{3} =A_{3} B+b=CA_{3} =CB_{3} =AC_{3} +b{\rm \; }\Rightarrow {\rm \; }a-b=AC_{3} -BC_{3} $. Diğer taraftan $AC_{3} +C_{3} B=c$ olduğundan $AC_{3} =s-b$ ve $C_{3} B=s-a$  bulunur.

Dolayısıyla $CB_{3} =CA_{3} =s$ sağlanır. Sırasıyla $CA_{3} B_{3} $, $AB_{3} C_{3} $ ve $BA_{3} C_{3} $ üçgenlerinde Sinüs Teorem'inden:

$A_{3} B_{3} =2\sin \dfrac{\gamma }{2} .s$,  $B_{3} C_{3} =2\left (s-b\right ).\cos \dfrac{\alpha }{2} $ ,  $A_{3} C_{3} =2\left (s-a\right ).\cos \dfrac{\beta }{2} $.
Dolayısıyla da $Ç\left (A_{3} B_{3} C_{3} \right )=\left (a+b+c\right ).\sin \dfrac{\gamma }{2} +2\left (s-b\right ).\cos \dfrac{\alpha }{2} +2\left (s-a\right ).\cos \dfrac{\beta }{2} $ bulunur. Benzer şekilde:

$Ç\left (A_{1} B_{1} C_{1} \right )=\left (a+b+c\right ).\sin \dfrac{\alpha }{2} +2\left (s-b\right ).\cos \dfrac{\gamma }{2} +2\left (s-c\right ).\cos \dfrac{\beta }{2} $ ve

$Ç\left (A_{2} B_{2} C_{2} \right )=\left (a+b+c\right ).\sin \dfrac{\beta }{2} +2\left (s-a\right ).\cos \dfrac{\gamma }{2} +2\left (s-c\right ).\cos \dfrac{\alpha }{2} $  sağlanır.

Bu eşitlikleri kullanarak: $M=\dfrac{\left (a+b+c\right )\left (\sin \dfrac{\alpha }{2} +\sin \dfrac{\beta }{2} +\sin \dfrac{\gamma }{2} \right )+2a\cos \dfrac{\alpha }{2} +2b\cos \dfrac{\beta }{2} +2c\cos \dfrac{\gamma }{2} }{R} $  elde edilir. $\left (*\right )$

Şimdi, $M$ ifadesini parçalayarak her ifadenin alabileceği en büyük değerlere bakalım. İki ifadeyi inceleyeceğiz:
  • $\dfrac{\left (a+b+c\right )\left (\sin \dfrac{\alpha }{2} +\sin \dfrac{\beta }{2} +\sin \dfrac{\gamma }{2} \right )}{R} \le \dfrac{9\sqrt{3} }{2} $ sağlanır. Bunu ispatlarken $\dfrac{a+b+c}{R} \le 3\sqrt{3} $ ve ${\rm sin}\dfrac{\alpha }{{\rm 2}} +\sin \dfrac{\beta }{2} +\sin \dfrac{\gamma }{2} \le \dfrac{3}{2} {\rm \; }$ eşitsizliklerini kullanacağız.
    • $f\left (x\right )=\sin x$ fonksiyonu ve her $x\in \left[0,\pi \right]$ için $f^{\prime \prime} \left (x\right )=-\sin x\le 0$ olduğundan, fonksiyon $x\in \left[0,\pi \right]$ aralığında konkavdır. Dolayısıyla $\alpha ,\beta ,\gamma \in \left[0,\pi \right]$ için Jensen Eşitsizliği'nden:  $$\dfrac{1}{3} \left (\sin \alpha + \sin \beta + \sin \gamma \right ) \le \sin \left (\dfrac{\alpha +\beta +\gamma }{3} \right )=\sin 60^\circ=\dfrac{\sqrt{3} }{2}$$ $$\Rightarrow \dfrac{a+b+c}{R} =2\left (\sin \alpha +\sin \beta +\sin \gamma \right )\le 3\sqrt{3}$$ elde edilir.
    • Yine $f\left (x\right )=\sin x$ fonksiyonu ve $\dfrac{\alpha }{2} ,\dfrac{\beta }{2} ,\dfrac{\gamma }{2} \in \left[0,\pi \right]$ için Jensen Eşitsizliği'nden: $$\dfrac{1}{3} \left ( \sin \dfrac{\alpha }{2} + \sin\dfrac{\beta }{2} + \sin\dfrac{\gamma }{2} \right )\le \sin \left (\dfrac{\dfrac{\alpha }{2} +\dfrac{\beta }{2} +\dfrac{\gamma }{2} }{3} \right )=\sin 30^\circ =\dfrac{1}{2}$$ $$\Rightarrow  \sin \dfrac{\alpha }{2} +\sin \dfrac{\beta }{2} +\sin \dfrac{\gamma }{2} \le \dfrac{3}{2}$$ bulunur.

    Sonuç olarak, $\dfrac{\left (a+b+c\right )\left (\sin \dfrac{\alpha }{2} +\sin \dfrac{\beta }{2} +\sin \dfrac{\gamma }{2} \right )}{R} \le \dfrac{9\sqrt{3} }{2} $ elde ederiz.

  • $\dfrac{2a\cos \dfrac{\alpha }{2} +2b\cos \dfrac{\beta }{2} +2c\cos \dfrac{\gamma }{2} }{R} \le {\rm 9}$ sağlanır. Öncelikle $a\cos \dfrac{\alpha }{2} +b\cos \dfrac{\beta }{2} +c\cos \dfrac{\gamma }{2} $ ifadesine bakalım.

    Genelliği bozmadan $a\ge b\ge c$ varsayalım. Dolayısıyla $\alpha \ge \beta \ge \gamma $ sağlanır.
    Ayrıca  $f\left (x\right )=\sin x$ fonksiyonu, $x\in \left[0,\dfrac{\pi }{2} \right]$ aralığında artan olduğundan,  $$\sin \dfrac{\alpha }{2} \ge \sin \dfrac{\beta }{2} \ge \sin \dfrac{\gamma }{2}$$ bulunur. $\Rightarrow \cos \dfrac{\alpha }{2} \le \cos \dfrac{\beta }{2} \le \cos \dfrac{\gamma }{2} $.

    Yani  $a\ge b\ge c$ ve $\cos \dfrac{\alpha }{2} \le \cos \dfrac{\beta }{2} \le \cos \dfrac{\gamma }{2} $.  Chebyshev Eşitsizliği'nden:
    $$a\cos \dfrac{\alpha }{2} +b\cos \dfrac{\beta }{2} +c\cos \dfrac{\gamma }{2} \le \left (\dfrac{a+b+c}{3} \right )\left (\cos \dfrac{\alpha }{2} +\cos \dfrac{\beta }{2} +\cos \dfrac{\gamma }{2} \right ){\rm \; }\dots\left (1\right )$$

    $f\left (x\right )=\cos x$ fonksiyonu ve $x\in \left[0,\dfrac{\pi }{2} \right]$ için $f^{\prime \prime}\left (x\right )=-\cos x\le 0$  olduğundan, fonksiyon    $x\in \left[0,\dfrac{\pi }{2} \right]$ aralığında konkavdır. Dolayısıyla Jensen Eşitsizliği'nden   
    $$\dfrac{1}{3} \left ( \cos\dfrac{\alpha }{2} \cos\dfrac{\beta }{2} + \cos \dfrac{\gamma }{2} \right )\le \cos \left (\dfrac{\dfrac{\alpha }{2} +\dfrac{\beta }{2} +\dfrac{\gamma }{2} }{3} \right )=\cos 30^\circ=\dfrac{\sqrt{3} }{2}$$ $$\Rightarrow \left ( \cos \dfrac{\alpha }{2} +\cos \dfrac{\beta }{2} +\cos \dfrac{\gamma }{2} \right )\le \dfrac{3\sqrt{3} }{2}$$ bulunur. Bunu $\left (1\right )$'de yerine koyarsak:

    $a\cos \dfrac{\alpha }{2} +b\cos \dfrac{\beta }{2} +c\cos \dfrac{\gamma }{2} \le \left (\dfrac{a+b+c}{3} \right )\left (\cos \dfrac{\alpha }{2} +\cos \dfrac{\beta }{2} +\cos \dfrac{\gamma }{2} \right ){\rm \; }\le \dfrac{\sqrt{3} }{2} \left (a+b+c\right )$ sağlanır. Buradan ve $\left (i\right )-\left (a\right )$ dan hareketle, $\dfrac{2a\cos \dfrac{\alpha }{2} +2b\cos \dfrac{\beta }{2} +2c\cos \dfrac{\gamma }{2} }{R} \le 2.\dfrac{\sqrt{3} }{2} \left (\dfrac{a+b+c}{R} \right )\le {\rm 9}$ bulunur.

Ana eşitsizliğimize dönersek, $\left (i\right )$ ve $\left (ii\right )$'den:

$M=\dfrac{\left (a+b+c\right )\left (\sin \dfrac{\alpha }{2} +\sin \dfrac{\beta }{2} +\sin \dfrac{\gamma }{2} \right )+2a\cos \dfrac{\alpha }{2} +2b\cos \dfrac{\beta }{2} +2c\cos \dfrac{\gamma }{2} }{R} \le 9+\dfrac{9\sqrt{3} }{2} $ elde ederiz. Eşitlik, Jensen Eşitsizliklerinde eşitlik varken, yani  $\alpha =\beta =\gamma =60^\circ$ iken sağlanır, İspat biter.  $\square $
6
$n,m\ge 0$ tam sayıları için, $K(n,0)=\phi $ ve $$K(n,m+1)=\lbrace k \mid 1\le k\le n \text{ ve } K(k,m)\cap K(n-k,m)=\phi \rbrace$$ ise, $K(2004,2004)$ kümesinin eleman sayısını bulunuz.
Çözüm:
(Eren DURLANIK)

Cevap: $\left|K\left(2004,2004\right)\right|=127$

İddia-1: Her pozitif tamsayı, 2 nin farklı kuvvetlerinin toplamı biçiminde tek türlü ifade edilebilir.

İspat:  Tümevarımla ispatlayalım. $n=1$ ve $n=2$  için doğruluğu bariz. İddiamız $1,2,\dots ,n-1$  için doğru olsun, n için de doğru olacağını gösterelim. $2^t\le n<2^{t+1},\ t\in {\mathbb Z}$  ve $n=2^{x_1}+2^{x_2}+\dots 2^{x_k},\ x_1>x_2>\dots >x_k$ olsun; böyle bir yazılımın her zaman bulunduğu açıktır, örnek olarak iki tabanında yazılım verilebilir. Eğer $x_1<t$ olsaydı; $2^t\le n\le 2^0+2^1+\dots +2^{t-1}=2^t-1$ olurdu ve çelişki elde ederdik. $x_1>t$  olamayacağı zaten açıktır, demek ki $x_1=t$ olur. Tümevarım varsayımından $n-2^t$  nin yazılımı da tek türlü belirli olacağından; $n$  in yazılımı da tek türlüdür. Böylece iddianın ispatı tamamlandı.

Her $n=2^{x_1}+2^{x_2}+\dots +2^{x_k}$  pozitif tamsayısı için, $S_n=\{2^{x_1},2^{x_2},\dots ,2^{x_k}\}$  olarak tanımlayalım. İddia-1 den ötürü $S_n$  tek türlü belirlidir.     

İddia-2: Her $m\ge n$  için $K(n,m)=K(n,n)$ eşitliği sağlanır.

İspat: $n$  üzerine tümevarımla ispatlayacağız. $n=0$  için $K(0,m)=\{k|1\le k\le 0$ ve $K(k,m)\cap K(-k,m)=\emptyset \}=\emptyset $ olur, çünkü $1\le k\le 0$ şartını sağlayan $k$ değeri yoktur. İddiamız $1,2,\dots ,n-1$  için doğru olsun, $n$  için de doğru olacağını gösterelim. $m=n$ durumu açıktır, varsayalım  $m\ge n+1$ olsun. Tanım gereği, $K(n,m)=\{k|1\le k\le n$ ve $K(k,m-1)\cap K(n-k,m-1)=\emptyset \}$ sağlanır.

$m-1\ge n\ge k$ ve $m-1\ge n-1\ge n-k$  olduğundan, tümevarım varsayımını kullanarak, her $k\le n-1$ için $K(k,m-1)=K(k,k)=K(k,n-1)$  ve $K(n-k,m-1)=K(n-k,n-k)=K(n-k,n-1)$ olduğu söylenebilir. Öyleyse $K(n,m)=\{k|1\le k\le n-1$ ve $K(k,n-1)\cap K(n-k,n-1)=\emptyset \}\cup \left\{k\right|k=n\ ve\ K(n,m)\cap K(0,m)=\emptyset \}$ bulunur. Diğer taraftan, $K\left(0,m-1\right)=\emptyset =K\left(0,n-1\right)$ olduğundan, $\left\{k\right|k=n\ ve\ K(n,m-1)\cap K(0,m-1)=\emptyset \}=\{n\}=\left\{k\right|k=n\ ve\ K(n,n-1)\cap K(0,n-1)=\emptyset \}$ olduğunu söyleyebiliriz. Bu eşitliği $K\left(n,m\right)$ ifadesinde yerine yazarsak; $K\left(n,m\right)=\left\{k\right|k=n\ ve\ K(n,n-1)\cap K(0,n-1)=\emptyset \}\cup \{k|1\le k\le n-1$ ve $K(k,n-1)\cap K(n-k,n-1)=\emptyset \}=K(n,n)$  bulunur, tümevarım varsayımı n için doğrudur.

Dolayısıyla tümevarımdan iddia ispatlanmış olur.

$K(n,n)=K_n$ olarak tanımlayalım, yukarıdaki iddiadan ötürü her $1\le m\le n-1$ için $K(m,m)=K(m,n-1)$ ve $K(n-m,n-1)=K(n-m,n-m)$ sağlanır. Bunu $K_n$ de yerine yazarsak$K_n=\left\{k\right|k=n\ ve\ K(n,n-1)\cap K(0,n-1)=\emptyset \}\cup \{k|1\le k\le n-1$ ve $K(k,n-1)\cap K(n-k,n-1)=\emptyset \}=\{n\}\cup \{m|1\le m\le n-1$  ve $K_m\cap K_{n-m}=\emptyset \}$  bulunur \dots  (*).

İddia-3: $K_n,\ $ $S_n$  in boş olmayan tüm altkümelerinin elemanları toplamının oluşturduğu kümedir.

İspat: $n$ üzerinden tümevarımla kanıtlayalım. $n=0$  ve $n=1$ için iddianın doğruluğu kolayca kontrol edilir. İddiamız $1,2,\dots ,n-1$ için doğru olsun, $n$  için de doğru olacağını gösterelim. İspatlamamız gereken şey, $S_m\subset S_n\Longleftrightarrow m\in K_n$  olduğudur.($S_m\subset S_n$ olması, $m$ nin $S_n$ in bir altkümesinin elemanları toplamı şeklinde ifade edilebildiği anlamına gelmektedir.) İfadenin iki yönünü de inceleyelim:

$S_m\subset S_n\Rightarrow m\in K_n$: İlk olarak, tümevarım varsayımından, her $1\le m\le n-1$ için $a\in K_m{\rm ,\ }K_{n-m}\Longleftrightarrow S_a\subset S_m,S_{n-m}\Longleftrightarrow {S_a\subset S}_m\cap S_{n-m}\ $elde edilir. Fakat $S_m\subset S_n$  ise $S_{n-m}=S_n/S_m$  olacağından  $S_m\cap S_{n-m}=\emptyset $ sağlanır. Demek ki ${S_a\subset S}_m\cap S_{n-m}$ ve dolayısıyla da $a\in K_m{\rm ,\ }K_{n-m}$ olan bir $a$ yoktur. Sonuç olarak, $1\le m\le n-1$ için $S_m\subset S_n$  durumunda $K_m\cap K_{n-m}=\emptyset $  sağlanır ve (*) dan $m\in K_n$  olur. Ayrıca $m=n$ durumunda, (*) dan ötürü $S_n\subset S_n\Longleftrightarrow n\in K_n$ de sağlanır.

$S_m\subset S_n\Leftarrow m\in K_n$: Bunun için, $S_m\not\subset S_n$  ise $m\notin K_n$  olduğunu göstermek yeterlidir. Varsayalım $S_m\not\subset S_n$  ve  $m\in K_n$  olsun. (*) dan ötürü $K_m\cap K_{n-m}=\emptyset $  olmalıdır. Dolayısıyla $S_m\cap S_{n-m}=\emptyset $  bulunur. Öyleyse $S_n=S_m\cup S_{n-m}$  olur; fakat bu da $S_m\not\subset S_n$  olması ile çelişir. Demek ki $m\notin K_n{\rm \ }$ olmalıymış.

Sonuç olarak tümevarım varsayımı $n$ için de doğrudur, tümevarımdan iddia ispatlanmış olur.

İddia-3 den ötürü $S_{2004}=\{1024,\ 512,\ 256,\ 128,\ 64,\ 16,4\}$ dür. $S_{2004}$  ün boş olmayan altkümelerinin sayısı  $2^7-1=127$ dir. Öte yandan İddia-1 den, bu altkümelerden elemanları toplamı aynı olan farklı iki tanesi yoktur, çünkü bu alt kümelerdeki elemanların toplamı, farklı sayıların ikinin kuvvetleri toplamı şeklindeki yazılımını vermektedir. Öyleyse cevabımız $127$ olacaktır.