Tübitak Lise 2. Aşama 2008 Soru 4

[geo]

$\mathbb{N}$ negatif olmayan tam sayıların ve $\mathbb{Z}$ de tüm tam sayıların kümesini göstermek üzere, $f:\mathbb{N}\times \mathbb{Z}\to \mathbb{Z}$ fonksiyonu,

• $f(0,0)=1$, $f(0,1)=1$,
• her $k\not\in \lbrace 0,1\rbrace $ için, $f(0,k)=0$ ve
• her $n\ge 1$ ve $k$ için, $f(n,k)=f(n-1,k)+f(n-1,k-2n)$

koşullarını sağlıyorsa $$\sum\limits_{k=0}^{\binom{2009}{2}}{f(2008,k)}$$ toplamının değerini bulunuz.

(Serhat Doğan)

[geo]

(Mehmet KAYSİ)

İddia 1: $k<0$ veya $k>n^2+n+1$ ise $f(n,k)=0$ dır.

İspat: $n$ üzerinden tümevarım yapalım. $n=0$ için iddia doğrudur.
İddia $n-1$ için doğru olsun, yani $k<0$ ya da $k> n^2-n+1$ ise $f(n-1,k)=0$. Şimdi $n$ ye bakalım.
$k<0$ ise $k-2n<0$ olacağından, $f(n,k)=f(n-1,k)+f(n-1,k-2n)=0+0=0$ dır.
$k>n^2+n+1$ ise $k-2n>n^2-n+1$ olacağından $f(n,k)=f(n-1,k)+f(n-1,k-2n)=0+0=0$ olur.

İddia 2: Her $k$ tamsayısıiçin $f(n,k)=f(n,n^2+n+1-k)$.

İspat: Yine $n$ üzerinden tümevarım yapalım. $n=0$ için iddia doğrudur.
İddia $n-1$ iddia doğru olsun, yani $0\leq k\leq n^2-n+1$ ise $f(n-1,k)=f(n-1,n^2-n+1-k)$ (1). Burada $k$ yerine $k-2n$ yazarsak, $f(n-1,k-2n)=f(n-1,n^2-n+1-(k-2n))=f(n-1,n^2+n+1-k)$ (2). (1) ve (2) yi taraf tarafa toplayalım.
$f(n-1,k)+f(n-1,k-2n)=f(n-1,n^2-n+1-k)+f(n-1,n^2+n+1-k)$
$=f(n-1, n^2+n+1-(k-2n))+f(n-1,n^2+n+1-k)$ ise $f(n,k)=f(n,n^2+n-1-k)$. 
 
İddia 3: $\sum_{k=0}^{n^2+n+1}f(n,k)=2^{n+1}$
İspat: Yine tümevarım yapalım. $n=0$ için iddia doğrudur.
İddia $n-1$ için doğru olsun, yani $\sum_{k=0}^{n^2-n+1}f(n-1,k)=2^{n}$.
$n$ için bakalım.
$\sum_{k=0}^{n^2+n+1}f(n,k)=  \sum_{k=0}^{n^2+n+1}f(n-1,k)+f(n-1,k-2n)$
$=\sum_{k=0}^{n^2+n+1}f(n-1,k)+\sum_{k=0}^{n^2+n+1}f(n-1,k-2n)$
$=\sum_{k=0}^{n^2-n+1}f(n-1,k)+\sum_{l=-2n}^{n^2-n+1}f(n-1,l)$
$=2^n+\sum_{l=0}^{n^2-n+1}f(n-1,l)=2^n+2^n=2^{n+1}$ (Burada iddia 1 birkaç kez kullanılıyor).
 
$k=0$'dan $k=n^2+n+1$'e kadar değisiyor yani $n^2+n+2$ terim var ve iddia 2'ye göre $f(n,k)=f(n,n^2+n+1-k)$. O zaman ilk $\frac{n^2+n+2}{2}$ terimin toplamı $\frac{2^{n+1}}{2}=2^n$ olur. Toplam şeklinde ifade edelim: $\sum_{k=0}^{\frac{n^2+n}{2}}f(n,k)=2^n$. Burada $n=2008$ koyarsak istenilen sonucu elde ederiz.

[geo]

(Mehmet KAYSİ)

$A=\left\{1,2,4,6,8,10, \ldots 2n\right\}$ olsun.
İddia: $f(n,k)$ sayısı $A$ kümesinin alt kümeleri arasında toplamları $k$ olan altkümelerin sayısına eşittir.
İspat: İddia $0$ için doğrudur. İddia $n-1$ için doğru olsun. $n$ için bakalım.
Toplamı $k$ olan kümelerden bazılarında $2n$ vardır, bazılarında yoktur. İçinde $2n$ varsa, bu kümelerin sayısı $f(n-1,k-2n)$ ye eşittir, çünkü $2n$ yi çıkardığımızda kalan sayılarin toplamı $k-2n$ olur. İçinda $2n$ yoksa, bu kümelerin sayısı $f(n-1,k)$ ye eşittir. Dolayısıyla $f(n,k)=f(n-1,k)+f(n-1,k-2n)$ olur.
 
$A$ kümesindeki tüm elemanların toplamı  $n^2+n+1$ dir. Bu yüzden toplamı $k$ olan alt kümelerin sayısı ile toplamı $n^2+n+1-k$ olan alt kümelerin sayısı birbirine eşittir. (Toplamı $k$ olan kümenin tümleyenindeki elemanların toplamı $n^2+n+1-k$ dır ve bu, bir eşleme belirtir.)
 
Soruda bize toplamları $0,1, \ldots \frac{n^2+n}{2}$ olan elemanların sayısını soruyor. Yukarıdaki sonucu da göz önüne alırsak bu sayı tüm alt kümelerin sayısının yarısına eşittir. $\left|A\right|=n+1$ olduğundan cevap $2^n$ dir. $n=2008$ için $2^{2008}$ bulunur.