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

Her $n$ pozitif tamsayısı için $$P_{n}(x)=x^{n-1}+x^{n-2}+x^{n-3}+\ldots +x+1$$ şeklinde tanımlanıyor. Her $a$ pozitif tamsayısı için, $$P_{n}(x)=(1+ax+x^{2}R(x)) Q(x)$$ olacak şekilde bir $n$ pozitif tam sayısı ile, katsayıları tam sayılar olan $R(x)$ ve $Q(x)$ polinomlarının bulunduğunu gösteriniz.

Çözüm 1:

$n$, ilk $k$ asal sayının çarpımı olsun.
$k=2$ için, $n=6$ dır.
$$P_6\left(x\right)\left(x-1\right)=x^6-1=\left(x-1\right)\underbrace{\left(x+1\right)\left(x^2+x+1\right)}_{x^2R\left(x\right)+2x+1}\cdot\underbrace{\left(x^2-x+1\right)}_{Q\left(x\right)}.$$
$a=2$ için $n=6$, $R\left(x\right)=x+2$ ve $Q\left(x\right)=x^2-x+1$ olarak bulunabiliyor.
Genel olarak $\left(\dots +x+1\right)$ şeklinde $a$ ifadeyi yan yana çarpasak, $ax$ li bir terim elde ederiz.
$k=3$ için, $n=2\cdot 3\cdot 5=30$.
$$P_{30}\left(x\right)\left(x-1\right)=x^{30}-1$$
polinomunun $x^2-1$, $x^6-1$, $x^{10}-1$ polinomları ayrı ayrı böler. Ama hep birlikte bölmez.
Benzer şekilde $x-1$, $x+1$, $x^3-1$, $x^3+1$, $x^5-1$, $x^5+1$ polinomları da $x^{30}-1$ i ayrı ayrı böler. Ama hep birlikte bölmez.
Bu durumda $x^2+x+1$ ile $x^4+x^3+x^2+x+1$ polinomları da $x^{30}-1$ i ayrı ayrı böler. Bu iki polinomun $\text{ebob}$ ları $1$ ise $x^{30}-1$ i ikisi birlikteyken böler. Yani $$\left(x^2+x+1\right)\left(x^4+x^3+x^2+x+1\right)|x^{30}-1$$ Bu iki polinomun aralarında asal olduğu $$x^4+x^3+x^2+x+1=x^2\left(x^2+x+1\right)+x^2+x+1-x^2=\left(x^2+x+1\right)\left(x+1\right)-x^2$$ şeklinde gösterilebilir. Bu durumda $$x^{30}-1=Q\left(x\right)\left(x-1\right)\underbrace{\left(x+1\right)\left(x^2+x+1\right)\left(x^4+x^3+x^2+x+1\right)}_{\dots +3x+1}$$ şeklinde $n$ sayısı ile $R\left(x\right)$ ve $Q\left(x\right)$ polinomları bulunabilir.

İddia:
$p>q$ asal sayıları için, $$\text{ebob}\left(x^p-1,x^q-1\right)=x-1$$
İspat:
$(p,q)=1$ olduğu için, Öklid algoritması uyguladığımızda $(x^p-1, x^q-1)=(x^{p \mod q}-1, x^q-1)=\ldots=(x^{r}-1, x^{\text{ebob}(p,q)}-1)=x-1$ olacaktır. $\blacksquare$

Soruya geri dönersek,
$k=a$ için, $n$ sayısı ilk $a$ asal sayının çarpımı olacak.
Her $p|n$ asal sayısı için $x^p-1|x^n-1$ olacağı aşikar. Bu durumda $1+x+\dots +x^{p-1}|x^n-1$.
Bu şekilde asal sayılardan $a$ tane olduğu için, en az $a$ tane $\left(1+x+\dots \right)$ şeklinde bölen vardır. Bu $a$ bölenin hepsinin ikişerli olarak aralarında asal olduğunu yukarıdaki iddiada gösterdik. Bu durumda bu $a$ bölenin hepsi birlikte çarpandır. Bu durumda $$x^n-1=\left(x-1\right)\underbrace{\ \dots \ }_{Q\left(x\right)}(1+ax+\underbrace{\ \dots \ }_{x^2R\left(x\right)})$$ elde edilir.

Not:
$n$ asalken $P(x) = x^{n-1} + x^{n-2} + \dots + x + 1$ polinomlarının indirgenemez olduğunu Eisenstein Kriteri ile de gösterebiliriz.

Çözüm 2:

$n,m\geq 2$ ve $(n,m)=1$ olsun.

$\begin{array}{lcl}
P_{nm}(x) &=& x^{nm - 1} + \dots + x + 1 \\
&=& \dfrac {x^{nm} - 1}{x-1} \\
&=& \dfrac {x^n - 1}{x-1}\cdot (1+x^n + x^{2n} + \dots + x^{(m-1)\cdot n}) \\
&=& P_n(x) \cdot P_{m}(x^n)
\end{array}$

İddia: $P_{m}(x) \mid P_{m}(x^n)$

İspat: $P_{m}(x^n)(x-1) = (x^{m} - 1)S(x) + 0$ olduğunu göstermemiz isteniyor.
$(1+x^n + \dots + x^{(m-1)n})(x-1) = (x + x^{n+1} + x^{2n+1} + \dots + x^{(m-1)\cdot n + 1}) - (1 + x^n + x^{2n} + \dots + x^{(m-1)n})$.
$P_{m}(x^n)(x-1)$ sayısının $x^{m}-1$ ile bölümünden kalanı bulmak için $x^{m}=1$ yazacağız.
$(n,m)=1$ olduğu için $0\cdot n, 1\cdot n, \dots, (m-1)\cdot n$ sayıları $\bmod {(m)}$ de tam kalan sistemi oluşturur. Yani, $0$ dan $(m-1)$ e tüm kalanları alır. (İspatı: $xn\equiv yn \pmod {m} \Longrightarrow (x-y)n\equiv 0 \pmod {m} \Longrightarrow x\equiv y \pmod {m}$)
Dolayısıyla bunların $1$ fazlaları da, $1+ 0\cdot n, 1+ 1\cdot n, \dots, 1+ (m-1)\cdot n$ sayıları da, $\bmod {(m)}$ de tam kalan sistemi oluşturur.
O halde $P_{m}(x^n)(x-1)$ polinomu $x^{m}-1$ ile kalansız bölünür.$\blacksquare$

İddianın sonucu olarak da $P_{nm}(x) = P_n(x) \cdot P_{m}(x^n) = P_n(x) \cdot P_{m}(x) Q(x)$ elde edilir.

Şimdi de sorunun çözümü için tümevarım uygulayalım.
$a=1$ için $n\geq 2$, $R(x)=1+x+\ldots + x^{n-3}$ ($n=2$ için $R(x)=0$), $Q(x)=1$ bulunur.
$a$ için $n, Q(x), R(x)$ bulunduğunu varsayalım.

$(n,m)=1$ ve $m\geq 2$ olmak üzere;
$\begin{array}{lcl}
P_{nm} &=& P_n(x) \cdot P_{m}(x)Q'(x) \\
&=& (1+ax+x^2R(x))(1+x+\dots + x^{m-1})Q'(x) \\
&=& (1+(a+1)x+R'(x))Q'(x)\end{array}$
olacağı için $a+1$ için de $nm$ sayısı, $R'(x)$, $Q'(x)$ polinomları bulunur.

$n$; her biri $1$ den büyük ve aralarında asal $a$ sayının çarpımı şeklinde alınabilir.

Kaynak: Barış Koyuncu'nun AoPS deki çözümü biraz değiştirilerek buraya taşınmıştır.
O çözümde $m=n+1$ olarak alınmıştır. Doğal olarak $(n,m)=1$ şartı sağlandığı için, yukarıdaki çözümün bir örneğidir.

Tüm $x,y \in \lbrace 1,2, \ldots ,2000\rbrace $ için tanımlanmış ve en çok $n$ sıralı $(x,y)$ ikilisinde farklı değerler alan her $f(x,y)$, $g(x,y)$ fonksiyon çifti için $x\not\in X$ ve $y \not\in Y$ iken $f(x,y)=g(x,y)$ olmasını sağlayacak biçimde, her biri $1000$ elemanlı $X,Y \subset \lbrace 1,2, \ldots ,2000\rbrace $ kümeleri bulunabiliyorsa, $n$ tamsayısının en çok kaç olabileceğini belirleyiniz.

Çözüm 1:

Tanım: $$h(x,y) =
\begin{cases}
1, & f(x,y) = g(x,y) \\
0, & f(x,y) \neq g(x,y) \\
\end{cases}$$
olsun.
$x_i$ sayısı verildiğinde, $y$ bilinmeyeni için $h(x_i,y) = 1$ denkleminin çözüm kümesi $S_i$ olsun.
$x_1, x_2, \dots, x_{2000}$ dizisi; $\{1,2,\dots, 2000\}$ kümesinin $$2000\geq |S_1| \geq |S_2| \geq \cdots \geq |S_{2000}| \geq 0$$ şeklinde bir permütasyonu olsun.

Gözlem:
$$\left |\bigcap_{i=1}^{1000}S_i \right | \geq 1000$$ olduğunda, $\bigcap\limits_{i=1}^{1000}S_i$ kümesinin herhangi $1000$ elemanı, $y_1, y_2, \dots, y_{1000}$ olsun.
$X=\{x_{1001}, x_{1002}, \dots, x_{2000}\}$ ve $Y=\{y_{1001}, y_{1002}, \dots, y_{2000}\}$ olarak seçildiğinde, $x \not\in X$ ve $y\not\in Y$ iken, yani $x \in \{x_1, x_2, \dots, x_{10000}\}$ ve $y\in \{y_1, y_2, \dots, y_{1000}\}$ iken, $1 \leq i,j\leq 1000$ olmak üzere; her $(x_i, y_i)$ çifti için $h(x_i, y_i) = 1$ olacağı tanımda belirtilmişti.
Demek ki, $\left |\bigcap\limits_{i=1}^{1000}S_i \right | \geq 1000$ olduğunda, her $h(x,y)$ için, her biri $1000$ er elemanlı $X,Y \subset \{1,2,\dots, 2000\}$ kümeleri bulunabiliyor.

İddia 1:
$n=3000$ olduğunda, herhangi bir $h(x,y)$ için bahsedilen şekilde $X$ ve $Y$ kümeleri bulunabilir.
İspat:
$S'_i = \{1,2,\dots, 2000\} - S_i$ olsun.
Tanım gereği, $$2000\geq |S_1| \geq |S_2| \geq \cdots \geq |S_{2000}| \geq 0$$ olduğu için, $$0\leq |S'_1| \leq |S'_2| \leq \cdots \leq |S'_{2000}| \leq 2000$$ olacaktır.
$y\in S'_i$ ise $h(x_i, y) = 0$ olacağı tanımda verilmişti. Bu durumda $h(x,y) = 0$ olan ikililerin sayısı $n=3000$ olduğu için, $$\sum_{i=1}^{2000}|S'_i| \leq n=3000$$ dir. $|S'_{1000}| > 2$ olsaydı, $$n=3000 \geq \sum_{i=1}^{999}|S'_i| + \sum_{i=1000}^{2000}|S'_i| \geq \sum_{i=1}^{999}|S'_i| + 3 \cdot 1001 \geq 3003$$ olacaktı. Demek ki, $|S'_{1000}| \leq 2$.
$|S'_{1000}|=2$ olduğunda, $$n=3000 = \sum_{i=1}^{1000}|S'_i| + \sum_{i=1001}^{2000}|S'_i| \geq \sum_{i=1}^{1000}|S'_i| + 2 \cdot 1000 \Rightarrow \sum_{i=1}^{1000}|S'_i| \leq 1000$$ olacaktır. $|S'_{1000}|<2$ olduğunda, $0\leq |S'_i| \leq |S'_2| \leq \cdot \leq |S'_{1000}| \leq 1$ olduğu için, yine $$\sum_{i=1}^{1000}|S'_i| \leq 1000$$ olacaktır.
Her iki durumda da $\sum\limits_{i=1}^{1000}|S'_i| \leq 1000$ olduğu için, $\bigcup\limits_{i=1}^{1000}|S'_i|$ kümesi en fazla $1000$ elemanlı olabilir. Diğer bir deyişle, $\bigcup\limits_{i=1}^{1000}|S'_i|$ kümesinin elemanı olmayan en az $1000$ tane $a_k\in{1,2,\dots2000}$ elemanı bulunabilir. $a_k$ elemanı $\bigcup\limits_{i=1}^{1000}|S'_i|$ kümesinin dışında olduğu için, $a_k \not \in S'_i$, yani $a_k \in S_i$ dir. Demek oluyor ki, bu en az $1000$ eleman $S_1,S_2,\dots,S_{1000} $ kümelerinin hepsi tarafından içeriliyor. Yani $$\left |\bigcap\limits_{i=1}^{1000} S_i \right |\geq 1000$$ dir. Bu şart sağlandığında, her $h(x,y)$ için, her biri $1000$ er elemanlı $X,Y \subset \{1,2,\dots,2000\}$ kümeleri bulunabildiğini gözlem bölümünde göstermiştik. $\blacksquare$

İddia 2:
$3001$ $(x,y)$ çifti için $0$ değeri alan aşağıdaki $h(x,y)$ fonksiyonu için, bahsedilen şekilde $X$ ve $Y$ kümelerini bulmak mümkün değildir.
Her $a \in \{1,2,\dots,2000\}$ için $h(a,a)=0$,
$h(1,2)=h(2,3)=\cdots=h(1000,1001)=h(1001,1)=0$,
aksi takdirde $h(x,y)=1$.

İspat:
$X$ ve $Y$ kümelerinin bulunabildiğini varsayalım.
$X'=\{1,2,\dots,2000\}-X$ ve $Y'=\{1,2,\dots,2000\}-Y$ olsun. $|X'|=|Y'|=1000$ dir.
Herhangi $a \in \{1,2,\dots,2000\}$ sayısı için, $a \in X'$ ise, $a \in Y'$ olmak zorunda. Aksi takdirde, $a\in X'$ ve $a\in Y'$ iken $h(a,a)=1$ olması gerekecek ki, bu da $h(x,y)$ fonksiyonunun tanımına aykırı.
Demek ki $X'$ ve $Y'$ kümeleri ayrık. $|X'|=|Y'|=1000$ olduğu için de $X'\in Y'=\{1,2,\dots,2000\}$ dir.
$1\in X'$ olduğunu varsayalım. $h(1,2)=0$ olduğu için, $2\not \in Y'$ olmalı. Bu durumda $2 \in X'$ dür.
Bunu böyle devam ettirirsek, $1000 \in X' \Rightarrow 1001 \not \in Y' \Rightarrow 1001 \in X'$ elde edilir. Halbu ki, $|X'|=1000$ elemanlı, $1001$ elemanlı değil.
Benzer şekilde, $1\in Y'$ olduğunu varsayalım. $h(1001,1)=0$ olduğu için, $1001 \not \in X'$ olmalı. Bu durumda $1001 \in Y'$ dür.
Bunu böyle devam ettirirsek, $3 \in Y' \Rightarrow 2 \not \in X' \Rightarrow 2 \in Y'$ elde edilir. Halbu ki, $|Y'|=1000$ elemanlı, $1001$ elemanlı değil.
Demek ki, $n=3001$ olduğunda, soruda bahsedilen şekilde $X$ ve $Y$ kümeleri bulmak her zaman mümkün olmayabiliyor. $\blacksquare$

Sonuç:
$n$ tam sayısı en çok $3000$ olabilir. $\blacksquare$

Not:
Bu soru aşağıdaki soruyla özdeştir.
$2m\times 2m$ bir matrisin $n$ elemanı $0$, diğerleri $1$ dir. Bu şekilde herhangi bir matrisin tam olarak $m$ satırını ve $m$ sütununu sildiğimizde tüm elemanları $1$ olan $m\times m$ bir matris elde edilebiliyorsa, $n$ nin alabileceği en büyük değerin $3m$ olduğunu gösteriniz.

Bu problemin genel hali literatürde Zarankiewicz problemi olarak geçiyor. Bizim sorumuzdaki özel hali için On the Half-Half Case of the Zarankiewicz Problem makalesine müracaat edebilirsiniz.

Çözüm 2:

Bir önceki çözümün not kısmında belirtilen matris dönüşümünü yaparak, soruyu daha sözel bir dille çözelim:

$$h(x,y) =
\begin{cases}
1, & f(x,y) = g(x,y) \\
0, & f(x,y) \neq g(x,y) \\
\end{cases}$$
olsun.

Sorudaki tanım gereği; $h(x,y)$ fonksiyonu en çok $n$ ikili için $0$ değerini alabiliyor. Bu fonksiyona eşdeğer gösterim, elemanlarının en çok $n$ tanesi $0$, gerisi $1$ olan $2000\times 2000$ bir matris olacaktır.

Bu durumda sorumuz, aşağıdaki soruya dönüşür:

Yeni Soru:
$0-1$ lerden oluşan $2000\times 2000$ matris nasıl verilirse verilsin, öyle $1000$ satır ve öyle $1000$ sütun silindiğinde geride sadece $1$ lerden oluşan $1000\times 1000$ matris kalabiliyorsa; bu matristeki $0$ ların sayısı en çok kaç olabilir?

Biraz inceleme yapalım.
$n=0$ ise matriste sadece $1$ ler vardır. Bu durumda hangi $1000$ satır ve $1000$ sütunu silersek silelim geriye $1$ lerden oluşan $1000\times 1000$ bir matris kalır.

$n=1$ ise matriste bu tek $0$ değerini içeren sütunun yer aldığı $1000$ sütunu ve herhangi $1000$ satırı silersek; yine sadece $1$ lerden oluşan $1000\times 1000$ lik bir matris elde ederiz.

Soru bizden $n$ yi kaça kadar artırabileceğimizi bulmamızı istiyor.

$M_1$ matirisinden bazı sütunların yerini değiştirerek $M_2$ matrisini elde edelim. $M_1$ den $1000$ satır ve $1000$ sütun silerek istediğimiz $1000\times 1000$ matrisi elde ettiğimizi düşünelim. Aynı satırları ve $M_1$ deki sütunların $M_2$ deki karşılıklarını silersek de $M_2$ matrisinden sadece $1$ lerden oluşan $1000\times 1000$ matrisi elde ederiz. O halde; çözüme giderken sütunların yerini değiştirebiliriz.

Şimdi de, sütunları içerdikleri $0$ sayısına göre azalan sırada sıraladığımız yeni bir matris düşünelim.
$n=3000$ değerini inceleyelim.

$1001.$ sütunda $2$ den fazla sayıda $0$ olamaz. Aksi halde, ilk $1000$ sütunda $3000$ den fazla $0$ olur.
$1001.$ sütunda tam olarak $2$ tane $0$ olduğunu varsayalım. Bu durumda ilk $1000$ sütunda en az $2000$ tane $0$ olacaktır. $n=3000$ olduğu için de ikinci $1000$ sütunda en fazla $1000$ tane $0$ olabilir.
$1001.$ sütunda tam olarak $1$ tane $0$ olduğunu varsayalım. Bu durumda ikinci $1000$ sütunda yine en fazla $1000$ tane $0$ olacaktır.

Her durumda, ikinci $1000$ sütunda en fazla $1000$ tane $0$ olacaktır.

İlk $1000$ sütunu sildiğimizi varsayalım. İkinci $1000$ sütundan $0$ ları içeren satırları silelim. Toplamda en fazla $1000$ tane $0$ olacağı için silinecek satırların sayısı da en fazla $1000$ olacaktır. $1000$ e tamamlamak için geriye kalanlardan istediğimiz (rastgele) satırları da silerek sadece $1$ lerden oluşan $1000\times 1000$ bir matris elde ederiz.
O halde, $n=3000$ için de sorudaki şart sağlanıyor.

$n=3001$ durumu için; aşağıdaki gibi bir matris oluşturalım:

İlk $1000$ satır için; $i.$ satırın $i.$ ve $(i+1).$ elemanları $0$ olsun.
$1001.$ satırın $1.$ ve $1001$. elemanları $0$ olsun.
Diğer satırlar için de; $i.$ satırın $i.$ elemanı $0$ olsun.

$$\begin{array}{|cccccc|cccccc|}
\hline
0 & 0 & &&& &&&&& \\
& 0 & 0 &&& &&&&& \\
& & \ddots & \ddots && &&&&& \\ \\
&&&& 0& 0 &&& && \\
&&&&& 0 & 0&&&& \\
\hline
0 &&&&& & 0 &\ &&&& \\
&&&&& & &0 &&&& \\
&&&&& && & \ddots & \quad && \\
&&&&& &&&&&& \\
&&&&& & &&&& 0 & \\
&&&&& & &&&&& 0 \\
\hline
\end{array}$$
Dikkat edilirse, $1000\times 2 + 2 + 999 = 3001$ tane $0$ var.
Silinecek sütunları $X$ kümesi ile, silinecek satırları da $Y$ kümesi ile ifade edelim.
Köşegendeki tüm elemanlar $0$ olduğu ve $|X|+|Y|=2000$ olduğu için $|X \cap Y| = 0$ olmalı. Yani $k.$ sütunu silersek, $k.$ satırı silmememiz lazım. Aksi halde köşegenin üzerinde $0$ lardan biri silinmemiş olur.

$1.$ sütunun silindiğini varsayalım. $1.$ satır silinemeyeceği için $2$. sütundaki ilk eleman, bir sütun silme işlemi ile silinmeli. O halde, $1.$ sütun silindiyse, $2.$ sütun da silinmeli.
Bu böyle devam ettiğinde $999.$ sütundan dolayı $1000.$ sütun; $1000.$ sütundan dolayı da $1001.$ sütun silinmeli. Halbuki; silinebilecek sütun sayısı $1000$. Bu durumda bir çelişki elde etmiş olduk.

Şimdi de $1.$ satırın silindiği durumdan başlayalım. $1.$ satır silindiği için, $1.$ sütun silinemez. $1.$ sütun $1001.$ satırdaki $0$ ın silinmesi için $1001.$ satırın da silinmesi gerekir.
$1001.$ satırdan dolayı, $1000.$ satır; $1000.$ satırdan dolayı, $999.$ satır silinmeli. Bu böyle devam ettiğinde $3.$ satırdan dolayı; $2.$ satır da silinecek. Bu durumda silinmesi gereken satır sayısı $1001$ olacak. Yine çelişki elde etmiş olduk.

O halde; $n=0,1,\dots, 3000$ değerleri için söz konusu $X$ ve $Y$ kümeleri bulunabiliyor. $n=3001$ için; öyle kötü bir örnek verilebiliyor ki, $1000$ er elemanlı $X$ ve $Y$ kümeleri bulunamıyor.
Bu durumda aradığımız yanıt, en çok $\boxed {3000}$ dir.

$p$ asal bir sayı olsun. Derecesi $p$'den küçük olan, katsayıları $\{0,1,\dots,p-1\}$ kümesinde yer alan ve tüm $m$, $n$ tam sayıları için $$T(n)\equiv T(m) \pmod {p} \Rightarrow n\equiv m \pmod {p}$$ koşulunu sağlayan bir $T(x)$ polinomunun derecesinin en çok kaç olabileceğini belirleyiniz.

Çözüm:

$p=2$ için $T(x)=x$ polinomu verilen denkliği sağlar. Bu durumda $p=2$ ise $\max{\deg(T)} = 1 = p-1$.

$p>2$ asal sayısı için $T(x) = x^{p-2}$ polinomunu ele alalım.
$m,n \not \equiv 0 \pmod p$ ve $T(n) \equiv T(m) \equiv n^{p-2} \equiv m^{p-2} \pmod p$ olsun.
Her iki tarafı $mn$ ile çarpalım. $$mn^{p-1} \equiv nm^{p-1} \pmod p$$ ve Fermat'ın Küçük Teoreminden $$n^{p-1} \equiv m^{p-1} \equiv 1 \pmod p$$ olacağı için $$n\equiv m \pmod p$$ elde edilir.
Yani her $p>2$ asal sayısı için derecesi $p-2$ olan ve sorudaki gerektirmeyi sağlayan bir $T(x)$ polinomu bulunabiliyor. Geriye kontrol edilmesi gereken tek bir sayı kalıyor: $p-1$.

$T(x) = a_{p-1}x^{p-1} + \dots + a_0$ polinomu verilen şartı sağlasın. $i\not \equiv j$ olduğunda $T(i) \equiv T(j)$ olamaz. Bu durumda tüm $T(i)$ sayıları farklıdır. Yani $T(x)$ birebir ve örtendir.
$\sum\limits_{i=0}^{p-1}T(i)$ toplamını iki yoldan sayalım.
Birincisi birebir ve örtenlikten $\sum\limits_{i=0}^{p-1}T(i) \equiv \sum\limits_{i=0}^{p-1}i \equiv \dfrac {(p-1)p}{2}$ elde ederiz. $p$ asal sayısı tek olduğu için sonuç olarak $\sum\limits_{i=0}^{p-1}T(i) \equiv \dfrac {p-1}{2}\cdot p \equiv 0 \pmod p$ elde ederiz.

Diğer yoldan saydığımızda da $T(i)$ lerin toplamının $p$ ye bölünmesi gerekecek.
$T(0) = a_0$
$T(1) = a_{p-1}\cdot 1^{p-1} + \dots + a_0$
$\vdots$
$T(p-1) = a_{p-1}\cdot (p-1)^{p-1} + \dots + a_0$
polinomlarını alt alta toplarsak
$\begin{array}{rcl}\sum\limits_{i=0}^{p-1}T(i) &=& a_{p-1}\left(1^{p-1} + \dots + (p-1)^{p-1}\right) \\ && + a_{p-2}\left(1^{p-2} + \dots + (p-1)^{p-2}\right) \\ && + \dots + a_1\left(1+2+\dots + (p-1)\right) + p\cdot a_0
\end{array}$.

Fermat'ın Küçük teoreminden $a_{p-1}$ in parantezinde olan tüm sayılar $1$ e denk olacağı için
$\sum\limits_{i=0}^{p-1}T(i) = \underbrace{a_{p-1}(p-1)}_{\not \equiv 0 \pmod p} + a_{p-2}\left(1^{p-2} + \dots + (p-1)^{p-2}\right) + \dots + \underbrace{a_1\left(1+2+\dots + (p-1)\right)}_{\equiv 0 \pmod p} + \underbrace{p\cdot a_0}_{\equiv 0 \pmod p}$ elde ederiz.

İddia:
$0<a<p-1$ için $\sum\limits_{i=1}^{p-1} i^a \equiv \sum\limits_{i=1}^{p-1} i^1 \equiv 0 \pmod p$.

İspat:
Her $p$ asal sayısı için bir $g$ ilkel kökü vardır. (Bunun ispatı için internete bakınız.)
İlkel kök tanımı gereği $j=1,\dots, p-1$ için $g^j$ sayıları $\{1,2,\dots, p-1\}$ kümesini örter. Bu durumda herhangi bir $i=1,2,\dots, p-1$ sayısı için buna denk $g^j$ sayısı bulabiliriz.
$$\sum\limits_{i=1}^{p-1} i^a \equiv \sum\limits_{j=1}^{p-1} (g^j)^a \equiv \sum\limits_{j=1}^{p-1} (g^a)^j \equiv \underbrace{g^a + g^{2a} + \dots + g^{(p-1)a}}_{\text{Geometrik Seri}} \equiv \dfrac {g^{pa} - g^a}{g^a - 1} \pmod p$$
$a \neq p - 1$ olduğu için $g^a \not \equiv 1 \pmod p$ ve Fermat'ın Küçük Teoremince $g^{pa} \equiv (g^a)^p \equiv g^a$ olacağı için $\dfrac {g^{pa} - g^a}{g^a - 1}$ sayısı $p$ ile bölünür. $\blacksquare$

Soruya geri dönersek,

$\sum\limits_{i=0}^{p-1}T(i) = \underbrace{a_{p-1}(p-1)}_{\not \equiv 0 \pmod p} + \underbrace{a_{p-2}\left(1^{p-2} + \dots + (p-1)^{p-2}\right)}_{\equiv 0 \pmod p} + \dots + \underbrace{a_1\left(1+2+\dots + (p-1)\right)}_{\equiv 0 \pmod p} + \underbrace{p\cdot a_0}_{\equiv 0 \pmod p} \not \equiv 0 \pmod p$.

Bu durumda diğer yoldan saydığımızın tersi bir durumla karşılaştık. Yani çelişki elde ettik.

Sonuç olarak, $\max \deg(T) = \max (1, p-2)$ elde etmiş olduk.

Bir $a$ pozitif gerçel sayısı ve tepesi $A$ noktasında bulunan bir açı verilmiş olsun. $A$ dan geçen ve bu açının kenarlarını $\vert AB\vert +\vert AC\vert =a$ koşulunu sağlayan $B$ ve $C$ noktalarında kesen tüm çemberlerin $A$ nın dışında bir ortak noktasının daha bulunduğunu gösteriniz.

Çözüm 1:

$B' \in [AB$ ve $C' \in [AC$ olmak üzere $AB'+AC'=AB+AC=k$ olsun. $B'B=CC'$ olduğu aşikar.

Bu iki üçgenin çevrel çemberleri $A$ dışında $A'$ noktasında kesişsin.

$AB'A'C'$ kirişler dörtgeninde $\angle A'B'B=\angle A'C'C$ ve $ABA'C$ kirişler dörtgeninde $\angle A'CC'=\angle ABB'$ olduğundan $\triangle A'BB'\sim \triangle A'C'C$ olur.
$BB'=CC'$ olduğundan $\triangle A'BB' \cong \triangle A'C'C$ yani $A'B=A'C$ ve $A'B'=A'C'$. Yani $AA'$, $BAC$ açısının açıortayıdır.

$AB'=AC'=\dfrac{a}{2}$ alındığında $A'$ noktası sabit bir üçgende açıortayın çevrel çemberi kestiği nokta, yani sabit bir nokta olacaktır.
Demek ki $\left(ABC\right)$ çemberlerinin hepsi $A'$ noktasından geçer.

Çözüm 2:

$\angle BAC=\alpha$ olsun. $\left(ABC\right)$ ile $A$ açısının açıortayı $P$ noktasında kesişsin. Ptolemy teoreminden $$\left(AB+AC\right)\cdot BP=AP\cdot BC.$$
$BCP$ üçgeninde Sinüs teoreminden $\dfrac{BC}{{\sin \left({180}^{\circ }-\alpha\right)\ }}=\dfrac {BP}{\sin \dfrac{\alpha}{2}\ }$ elde edilir.
İki eşitliği birleştirirsek $$AP=\dfrac{a}{2 \cos \dfrac{\alpha}{2}}=Sabit$$ elde ederiz. $AP$ sabit ve $|AP|$ sabit olduğuna göre $P$ noktası da sabittir. Tüm $ABC$ üçgenlerinin çevrel çembeleri sabit $P$ noktasından geçer.

Her $x\in [0,1]$ için $f^{n}(x)=x$ olacak şekilde bir $n$ pozitif tam sayının bulunmasını olanaklı kılan tüm $f:\lbrack 0,1\rbrack \to \lbrack 0,1\rbrack $ sürekli fonksiyonlarını bulunuz.
($x \in [0,1]$ olmak üzere, $f^{n}(x)$; $f^{1}(x)=f(x)$ ve her $k$ pozitif tam sayısı için $f^{k+1}(x) = f\left(f^{k}(x)\right)$ bağıntıları aracılığıyla tanımlanıyor.)

Çözüm:

$f(a) = f(b) \Rightarrow f^n(a) = f^n(b) = a = b$ olacağı için $f$ birebir ve örtendir. Bu durumda sürekli $f$ fonksiyonu ya artandır ya azalandır. (Aksi durumda, en az iki nokta için $f$ aynı değeri alırdı.)

$f$ azalan olsun.
$f(0) = 1$ ve $f(1)=0$ olmalı. Bu durumda fonksiyon $y=x$ doğrusunu bir $0<k<1$ noktasında kesmeli. Bu noktada $f(k)=k$ dır.
$0<a<k$ şeklinde bir sayı alalım. Bu sayı için $f(a)=b$, $f(b)=c$ olsun.

$(i)$ $f^2(a) = c > a$ olarak kabul edelim.
$b>k>c>a$ olduğu için $f(a)>f^2(a)>a$ dır.
Her iki tarafın $f$ sini alırsak, ($f$ azalan bir fonksiyon olduğu için) eşitsizlik yön değiştirecektir.
Bu durumda $f^2(a) < f^3(a) < f(a)$ olur. Bir önceki eşitsizliğimizdeki $a<f^2(a)$ ifadesini de bu yeni eşitsizliğe eklemlersek $a< f^2(a)<f^3(a)<f(a)$ ele ederiz.

Her tarafın tekrar $f$ sini alırsak, $f(a) > f^3(a)>f^4(a)>f^2(a)>a$ elde edeceğiz.
Sonuç olarak $f^n(a)$ sürekli $f(a)$ ile $f^2(a)$ arasında yer alıyor. Bu durumda $c>a$ için $ f^n(a)\neq a $ olduğunu gözlemlemiş olduk.

$(ii)$ $f^2(a) = c < a$ olarak kabul edelim.
$b>k>a>c$ olduğu için $f(a) > a > f^2(a)$.
Her iki tarafın $f$ sini alırsak $f^2(a)<f(a)<f^3(a)$. Elde edilen eşitsizliği $ f^2(a)<a<f(a) $ ile birleştirirsek $ f^2(a)<a<f(a)<f^3(a) $ elde edeceğiz.
$f$ almaya devam edersek;
$ f^3(a)<f(a)<f^2(a)<f^4(a)\Rightarrow f^3(a)<f(a)< a < f^2(a)<f^4(a) $, dolayısıyla da $ f^n\not\in\left[f(a), f^2(a)\right] $ elde edeceğiz. $ a\in\left(f(a), f^2(a)\right) $ olduğu için de $c<a$ için $ f^n(a)\neq a $ elde etmiş olduk.

Geriye sadece bir ihtimal kalıyor.
$(iii)$ $ f^2(a) = c = a$.
Bu durumda her $x$ için $f^2(x)=x$ olacaktır. Bu tarzda fonksiyonların genel tanımını ise şöyle yapabiliriz.
$g$ fonksiyonu; $0<k<1$ için $g:[0,k] \rightarrow [k,1]$, $g(0)=1$, $g(k)=k$ olacak şekilde sürekli ve azalan bir fonksiyon olarak tanımlansın.
Bu durumda soruda aradığımız azalan $f$ fonksiyonları
$$ f(x) =\left\{\begin{array}{ll}g(x) &\quad , 0\leq x\leq k\\ g^{-1}(x) &\quad , k < x\leq 1\end{array}\right. $$ şeklinde olacaktır.
$f$ artan olsun.
$f(0)=0$ ve $f(1)=1$ olacaktır.

$(i)$ $ f(a)>a\Rightarrow f(f(a))>f(a)>a\Rightarrow f^n(a)>a $
ve
$(ii)$ $ f(a)<a\Rightarrow f(f(a))<f(a)<a\Rightarrow f^n(a)<a $
olduğu için geriye sadece
$(iii)$ $f(a)=a$
kalıyor.
Bu durumda tek artan $f$ fonksiyonu $f(x)=x$.

Not:
Bu sorunun benzeri, Analiz ve Cebirde İlginç Olimpiyat Problemleri ve Çözümleri kitabında (5. Basım - 2003, Syf. 220, Problem 6.19) geçmektedir.