Tübitak Lise Takım Seçme - 1998 Çözümleri

$|AB|=|AC|$ olmak üzere bir $ABC$ ikizkenar üçgeninin eşit kenarları üzerine, üçgenin dış bölgesinde kalacak şekilde $BAXX'$ ve $CAYY'$ kareleri çiziliyor. $[BC]$ nın herhangi bir $K$ noktasından $BY$ ve $CX$ doğrularına indirilen dikmelerin ayakları sırasıyla $E$ ve $F$, $[BC]$ nın orta noktası $D$ ile gösterilmek üzere, $\vert DE\vert =\vert DF\vert $ olduğunu ispatlayınız. $[EF]$ nın orta noktasının geometrik yerini bulunuz.

Çözüm:

$\angle BAC=2\alpha \Rightarrow \angle ABY=\angle AYB=\angle AXC=\angle XCA={45}^{\circ }-\alpha \Rightarrow \measuredangle \left(XC,\ YB\right)={90}^{\circ }$.

$XC\cap YB=\left\{N\right\}$ olsun. $\angle ABN=\angle ACN$ olduğu için $N\in AD$ dir. $BNC$ üçgeni $N$ açısı dik açı olan ikizkenar bir dik üçgendir. $ENFK$ bir dikdörtgendir. $ENFK$ dikdörtgeninin çevrel çemberinin merkezi $M$ olacaktır. $ENDK$ karşılıklı dik açıların toplamından dolayı kirişler dörtgeni olduğundan $D$ de bu çember üzerindedir. $ND$ açıortay olduğu için $DE=DF$ olur. $M$ merkezinden $ND$ kirişine inilen dikme $ND$ kirişini ortalar. Bu noktanın $D$ ye uzaklığı $\dfrac{DN}{2}=\dfrac{\frac{BC}{2}}{2}=\dfrac{BC}{4}=\text{Sabit}$ tir. Bu durumda $M$, $BC$ paralel olan ve $BC$ den uzaklığı $\dfrac{BC}{4}$ olan doğru üzerindedir. $M$ nin geometrik yerinin sınırları $K=B$ ve $K=C$ olduğunda elde edilir. Son durumda $M$ nin geometrik yeri $BN$ ile $CN$ doğru parçalarının orta noktalarını birleştiren doğru parçasıdır.

$a_{1}=t$ ve $n\ge 1$ için $a_{n+1}=4a_{n}(1-a_{n})$ şeklinde tanımlanan gerçel sayılar dizisinde $a_{1998}=0$ olmasını sağlayan kaç $t$ değeri olduğunu bulunuz.

Çözüm:

Tersten gidelim, yani önce $a_{1997}$'i bulalım. $$a_{1998}=4a_{1997}(1-a_{1997})=0\implies a_{1997}=0 ~~\text{ veya } ~~a_{1997}=1$$ Eğer $a_{1997}=0$ ise başa döneriz ve $a_{1996}$ için aynı iki seçeneğimiz çıkar. Geriye giderken $k$ defa dizinin elemanının $0$ çıktığını varsayalım ($k=0,1,\dots,1997$ olabilir). $k=1997$ ise $t=0$'dır. $k=1996$ için de $t=1$'dir. İkisi de değilse, tersten $(k+1).$ dizi elemanını ($a_{k+1}$'i değil geriye doğru giderken elde ettiğimiz $(k+1).$ terimi) hesaplarken $1$ bulacağız, yani $a_{1997-k}=1$ olacaktır. $$4a(1-a)=1-(2a-1)^2$$ olduğundan $a_{1996-k}=\frac{1}{2}$ olacaktır. Amacımız bundan sonraki her hamlede $2$ adet potansiyel dizi elemanı bulabileceğimizi göstermektir. $4a(1-a)$ parabolunun alabileceği değerler $(-\infty,1]$ olduğunu görebiliriz. $a_{1996-k}$'dan daha geriye giderken karşımıza asla $1$ veya $0$ çıkamaz çünkü bu durumda o elemandan $a_{1996-k}$'ya gelirken dizi elemanı tekrar $0$ olur ve sıfırı tekrar etmeye başlar. Dolayısıyla geriye giderken $1$ ile karşılaşmayız ve eğer $a_i$ terimi $1$'den büyük değilse $a_{i-1}$'in alabileceği tam olarak $2$ değer olur. Bu işlem sırasında asla $1$'i aşamayacağımızı gösterelim. Farz edelim ki $i<1996-k$ için $a_i>1$ olsun. Bu durumda $$a_{i+1}=4a_i(1-a_i)<0$$ olacaktır. Yine $$a_{i+2}=4a_{i+1}(1-a_{i+1})<0$$ olacaktır ve bu şekilde devam edersek $a_{1996-k}$ da negatif olacaktır. Bu bir çelişkidir.

Yani $a_{1996-k}$'dan geriye giderken her dizi elemanında $2$ farklı ihtimalimiz olacaktır ve $a_1$'e ulaştığımızda $2^{1995-k}$ olası $t$ değeri elde ederiz. Bunların hepsi birbirinden farklıdır çünkü aynı olup farklı yollardan gelselerdi, bu $t$ değerlerinden $a_{1996-k}$'ya tek şekilde ulaşabildiğimizden dolayı farklı yollardan gelemezlerdi. Sonuç olarak $k=1997$ ve $k=1996$ için birer, geri kalan $k$'lar için $2^{1995-k}$ olası $t$ değeri vardır. Her $k$ için toplarsak $$1+1+2^0+2^1+\cdots+2^{1995}=2+(2^{1996}-1)=2^{1996}+1$$ adet olası $t$ değeri vardır.

Not: Soruyu genelleştirirsek $n\geq 2$ için $a_{n}=0$ olmasını sağlayan $2^{n-2}+1$ adet $t$ değeri vardır. Bunu fark edip tümevarım da uygulanabilir veya çözüm sayısı üzerinden yeni bir indirgemeli dizi tanımlanabilir.

$A=\lbrace 1,2,3,4,5\rbrace $ olsun. Tüm $B, C \subset A$ kümeleri için $f(B) \in B$ ve $f(B\cup C) \in \{f(B), f(C)\}$ koşullarını sağlayan bütün $f:2^A \setminus \{\emptyset\} \rightarrow A$ fonksiyonlarının sayısını bulunuz.

Çözüm:

$a\in\{1,2,3,4,5\}$ olsun. $f(\{a\})\in\{a\}$ olduğundan $f(\{a\})=a$ olmalıdır. $f(A)=n\in A$ diyelim. Bu durumda $n$'yi içeren herhangi bir $B\subset A$ için $$n=f(A)\in \{f(B),f(A-B)\}$$ olacağından ve $n\not\in A-B$ olduğundan $f(B)=n$ olmalıdır. Benzer şekilde $A'=A-\{n\}$ dersek ve $f(A')=m$ ise $m$'yi içeren her $A'$ altkümesi için $f$ fonksiyonunun sonucu $m$ olmalıdır. Yani $A_0=A$ ve $A_{i+1}=A_{i}-\{f(A_i)\}$ şeklinde $5$ küme oluşturabiliriz ve $$f(A_0), f(A_1), f(A_2), f(A_3), f(A_4)$$ kümelerini $A$'nın farklı elemanlarına sahip olmalıdır ve her permütasyonda farklı bir tane $f$ fonksiyonu oluşturabiliriz. Dolayısıyla $\boxed{5!=120}$ farklı fonksiyon vardır.

Anlaşılması için örnek verelim. $(f(A_0), f(A_1), f(A_2), f(A_3), f(A_4))=(2,1,5,3,4)$ için buna karşılık gelen fonksiyon, $$f(B)=\begin{cases} 2 & \text{eğer } 2\in B\\ 1 & \text{eğer } 1 \in B, 2\not\in B\\ 5 & \text{eğer } 5 \in B, 1,2\not\in B\\ 3 & \text{eğer } 3 \in B, 1,2,5\not\in B\\ 4 & \text{eğer } B=\{4\} \end{cases}$$ olacaktır.

$n$ değişik lojman $n$ kişiye dağıtılacaktır. Herkesin lojmanlara ilişkin bir tercih sıralaması vardır ve hiç kimse farklı iki lojman arasında kayıtsız değildir. Dağıtım yapıldıktan sonra, herkesi en az bu dağıtım kadar hoşnut edecek ve en az bir kişiyi de bu dağıtımda kendisine düşen lojmana tercih ettiği bir lojmana kavuşturacak başka bir dağtımın bulunmadığı anlaşılır. Yapılan dağıtımda, en az bir kişiye $n$ lojman arasında en çok tercih ettiği lojmanın düşmüş olduğunu kanıtlayınız.

Çözüm:

Aksini varsayalım. Yani hiç kimseye $1.$ tercihi çıkmasın.

$n$ köşeli bir çizge düşünelim. Köşelerle kişileri ifade edelim. $P_i$ kişisinin $1.$ tercihi olan lojman $P_j$ kişisine çıkmışsa, $P_i$ den $P_j$ ye bir yönlü kenar çizelim.
Şimdi de $P_1$ den başlayarak yönlü kenarları takip edelim. $P_1=P_{a_0}$, $P_{a_1}$, $P_{a_2}$, $\ldots$, $P_{a_n}$, $\ldots$ dizisinde bir yerden sonra döngü olmak zorunda. Çünkü çizgede $n$ tane köşe var. Diyelim döngü $P_{a_i}, P_{a_{i+1}}, \ldots, P_{a_j}, P_{a_i}$ şeklinde.
$P_{a_i}$ kişisine $P_{a_{i+1}}$ kişisine çıkan evi, $\ldots$, $P_{a_j}$ kişisine de $P_{a_i}$ kişisine çıkan evi verirsek, bu döngüdeki kişiler bir öncekinden daha hoşnut olur. Soruda böyle bir dağılım olmadığı söylenmişti. Çelişki.
O zaman en az bir kişi $1.$ tercihini almış olmalı.

Bir $ABC$ üçgeninin $[AB]$ kenarına $A$ noktasında teğet olan ve $C$ noktasından geçen çember ile $[AC]$ kenarına yine $A$ noktasında teğet olan ve $B$ noktasından geçen çemberin yarıçapları farklı olup bu iki çember $A$ dan farklı bir $D$ noktasında kesişiyor. $E$ noktası $[AB$ ışını üzerinde bulunan ve $|AB|=|BE|$ koşulunu gerçekleyen nokta olma üzere; $A,D,E$ noktalarından geçen çember ile $[CA$ ışının $A$ dan farklı olan kesişim noktası $F$ ise, $\vert CF\vert =\vert AC\vert $ olduğunu ispatlayınız.

Çözüm:

Soruyu sade bir şekilde çizmek çok önemli. Çevre açı ile teğet-kiriş açıların eşitliğinden

$\angle ABD=\angle DAC$ ve $\angle ACD=\angle BAD$. $A,D,F,E$ aynı çember üzerinde bulunduğundan $\angle AED=\angle AFD$ dir. Açı-Açı benzerliğinden $\triangle ABD\sim \triangle CAD$ ve $\triangle AFD\sim \triangle BED$ elde edilir. $\dfrac{AB}{AC}=\dfrac{BD}{AD}$ ve $\dfrac{BE}{AF}=\dfrac{2\cdot AB}{AF}=\dfrac{BD}{AD}$ eşitliklerini birleştirirsek $AF=2\cdot AC\Rightarrow AC=CF$ çıkar.

$f(x_{1},\ldots ,x_{n})$ katsayıları tam sayılar ve derecesi $n$ den küçük olan bir polinom olsun. $N$, $f(x_{1},\ldots ,x_{n})\equiv 0 \pmod {13}$ denkliğini ve $1\leq i \leq n$ için $0\le x_{i} < 13$ koşulunu sağlayan $(x_{1}, x_2, \ldots ,x_{n})$ sıralı $n$ lilerinin sayısı ise, $13 \mid N$ olduğunu gösteriniz.

Çözüm:

(Bu problemdeki tüm denklikler $\bmod 13$ te incelenmiştir.)

İddia: $0 \leq k<12 $ için $$\sum_{x=0}^{12} x^k \equiv 0 $$
İspat: $k=0$ durumu açıktır, bu nedenle $k>0$ durumunu ele alalım. $g$, $\bmod 13$ te bir ilkel kök olsun; o zaman $g, 2g, \ldots, 12g$ sayıları $\{1,2, \ldots, 12\}$ kümesini oluşturur. Bu nedenle $$
\sum_{x=0}^{12} x^k \equiv \sum_{x=0}^{12}(g x)^k=g^k \sum_{x=0}^{12} x^k ;$$ $g^k \not \equiv 1$ olduğu için $\sum_{x=0}^{12} x^k \equiv 0$ olmalıdır. Bu, iddiamızı kanıtlar. $\blacksquare$

Şimdi, $S=\left\{\left(x_1, \ldots, x_n\right) \mid 0 \leq x_i \leq 12\right\}$ kümesini düşünelim. $f\left(x_1, \ldots, x_n\right) \not \equiv 0$ olan $n$-lilerin sayısının $13$'e bölünebilir olması yeterlidir, çünkü $|S|=13^n$ sayısı $13$ ile bölünebilir. Şu toplamı ele alalım:
$$
\sum_{\left(x_1, \ldots, x_n\right) \in S}\left(f\left(x_1, \ldots, x_n\right)\right)^{12} .
$$
Bu toplam, $f\left(x_1, \ldots, x_n\right) \not \equiv 0$ olan $n$-lilerin sayısını sayar, çünkü Fermat'ın Küçük Teoremi'ne göre
$$
\left(f\left(x_1, \ldots, x_n\right)\right)^{12} \equiv \begin{cases}1, & f\left(x_1, \ldots, x_n\right) \not \equiv 0 \text { ise } \\ 0, & f\left(x_1, \ldots, x_n\right) \equiv 0 \text { ise }\end{cases}
$$
Öte yandan, $\left(f\left(x_1, \ldots, x_n\right)\right)^{12}$'yi uygun $N, c_j, e_{j i}$ sayıları ile aşağıdaki gibi açabiliriz: $$
\left(f\left(x_1, \ldots, x_n\right)\right)^{12}=\sum_{j=1}^N c_j \prod_{i=1}^n x_i^{e_{j i}}
$$ $f$'nin toplam derecesi $n$'den küçük olduğundan, her $j$ için $e_{j 1}+e_{j 2}+\cdots+e_{j n}<12n$ olmalıdır, bu nedenle her $j$ için $e_{j i}<12$ olan bir $i$ vardır. O halde, iddiamıza göre
$$
\sum_{\left(x_1, \ldots, x_n\right) \in S} c_j \prod_{i=1}^n x_i^{e_{j i}}=c_j \prod_{i=1}^n \sum_{x=0}^{12} x^{e_{j i}} \equiv 0
$$ dır; çünkü çarpımın içindeki toplamlardan biri $0$'dır. Bu nedenle
$$
\sum_{\left(x_1, \ldots, x_n\right) \in S}\left(f\left(x_1, \ldots, x_n\right)\right)^{12}=\sum_{\left(x_1, \ldots, x_n\right) \in S} \sum_{j=1}^N c_j \prod_{i=1}^n x_i^{e_j i} \equiv 0
$$ olur. Böylece $f\left(x_1, \ldots, x_n\right) \not \equiv 0$ olan $n$ lilerin sayısı $13$'e bölünebilir ve çözüm tamamlanır.

Kaynak: Mathematical Olympiads Problems and Solutions from Around the World 1998-1999, Syf. 152-153.