Tübitak Lise 2. Aşama 1999 Soru 3

[geo]

$n$ ve $p$ pozitif tamsayılar olmak üzere, $i,j\in \lbrace 1,2,\ldots ,n\rbrace $ için $\vert f(i)-f(j)\vert \le p$ şartını sağlayan $$f:\lbrace 1,2,\ldots ,n\rbrace \to \lbrace -p,-p+1,\ldots ,p-1,p\rbrace $$ fonksiyonlarının sayısının $(p+1)^{n+1}-p^{n+1}$ olduğunu gösteriniz.

[geo]

Verilen koşulları sağlayan ve aldığı en yüksek değer $q$ olan fonksiyonların sayısını $Q(q)$ ile gösterelim. Önce $q\in \left\{0,\dots ,p\right\}$ olduğu duruma bakalım. Her $i,j\in \left\{0,\dots ,n\right\}$ için $\left|f\left(i\right)-f\left(j\right)\right|\le p$ koşulu nedeniyle, bu durumda, her $k\in \left\{0,\dots ,n\right\}$ için $f\left(k\right)\in \{q-p,\ q-p+1,\dots ,q\}$ olur. Aldığı tüm değerler bu kümeye ait olan ${\left(p+1\right)}^n$ tane fonksiyon bulunup, bunlardan $q$ değerini hiç alamayanların sayısı $p^n$ dir. Dolayısıyla, $Q\left(p\right)={\left(p+1\right)}^n-p$ olur.
Eğer $q\in \{1,\dots ,p\}$ ise, benzer biçimde $Q\left(-q\right)={\left(p-q+1\right)}^n-{\left(p-q\right)}^n$ bulunur. Verilen koşulları sağlayan fonksiyonların toplam sayısı, $$\left(p+1\right)\left({\left(p+1\right)}^n-p^n\right)+\sum^p_{q=1}{\left({\left(p-q+1\right)}^n-{\left(p-q\right)}^n\right)}$$ $$={\left(p+1\right)}^{n+1}-\left(p+1\right)p^n+p^n={\left(p+1\right)}^{n+1}-p^{n+1}$$ olur.

Kaynak:
Matematik Dünyası 2000-II

[geo]

$f:\lbrace 1,2,\ldots ,n\rbrace \to \lbrace -p,-p+1,\ldots ,-1,0\rbrace$ şeklinde $(p+1)^n$ fonsksiyon yazılabilir. Açıktır ki bu fonksiyonlardan birinin herhangi iki elemanı arasındaki fark $p$ den fazla olamaz.

$f:\lbrace 1,2,\ldots ,n\rbrace \to \lbrace -p+1,-p+1,\ldots ,0,1\rbrace$ fonksiyonlarından görüntü kümesinde $1$'i içermeyenleri yukarıda saydık. O halde bu fonksiyonlardan $1$'i içerenleri genel toplamımıza ekleyeceğiz. Toplam $(p+1)^n$ tane fonksiyondan, $p^n$ tanesi $1$ içermez. O halde $(p+1)^n - p^n$ tanesi $1$ içerir.

Bu son yaptığımızı $1$ den başlayıp $p$ ye kadar devam ettirmemiz gerekiyor.
O halde aradığımız yanıt $$(p+1)^n + ((p+1)^n - p^n)\cdot p = (p+1)^{n+1} - p^{n+1}.$$