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

$m$ sayısını da $p$ tabanında $s$ basamaklı hale getirelim. (Başa $0$ ekleyerek)
$$\begin{array}{rcl}
m&=&a_{0}+a_{1}p+\ldots +a_{s}p^{s} \\
n &=& b_{0}+b_{1}p+\ldots +b_{s}p^{s} \\
n-m &=& k_{0}+k_{1}p+\ldots +k_{s}p^{s}
\end{array}$$
$k,x \in \mathbb N$ olmak üzere; $n! = M \cdot p^x$ eşitliğini sağlayan en büyük $x$ sayısı $$\Delta_p(n) = \left\lfloor \frac {n}{p} \right\rfloor + \left\lfloor \frac {n}{p^2} \right\rfloor + \dots + \left\lfloor \frac {n}{p^s} \right\rfloor$$ olacaktır. Biraz düzenlemeyle $$\begin{array}{rcl}
\Delta_p(n) &=& b_1 + b_2(p+1) + \dots + b_s(p^{s-1} + \dots + 1)\\
(p-1)\Delta_p(n) &=& b_1(p-1) + b_2(p^2-1) + \dots + b_s(p^s - 1) \\
(p-1)\Delta_p(n) &=& b_1p + b_2p^2 + \dots + b_sp^s - (b_1 + b_2 + \dots + b_s) \\
(p-1)\Delta_p(n) &=& b_0 + b_1p + b_2p^2 + \dots + b_sp^s - (b_0 + b_1 + b_2 + \dots + b_s) \\
(p-1)\Delta_p(n) &=& n - \sum\limits_{i=0}^s b_i
\end{array}$$
$n$ nin $p$ tabanında rakamları toplamına $\delta_p(n) = \sum\limits_{i=0}^s b_i$ dersek $$\Delta_p(n) = \dfrac{n - \delta_p(n)}{p-1}$$ olur.
$p^x | \binom{n}{m} = \dfrac{n!}{(n-m)!m!}$ şartını sağlayan en büyük $x$ sayısı $$\begin{array}{rcl}
\Delta_p\left(\binom{n}{m}\right) &=& \Delta_p(n) - \Delta_p(n-m) - \Delta_p(m)\\
&=&  \dfrac{n - \delta_p(n)}{p-1} -  \dfrac{n-m - \delta_p(n-m)}{p-1} -  \dfrac{m - \delta_p(m)}{p-1}\\
&=& \dfrac{\delta_p(m) + \delta_p(n-m) - \delta_p(n)}{p-1}
\end{array}$$ olacaktır.
Soruya dönersek; ilk önce, $m\prec_{p}n \Rightarrow p \nmid \binom{n}{m}$ olduğunu gösterelim:
$$m\prec_{p}n \Rightarrow \delta_p(m) + \delta_p(n-m) = \delta_p(n) \Rightarrow \Delta_p\left(\binom{n}{m}\right) = 0 \Rightarrow p \nmid \binom{n}{m} $$
Şimdi de $p \nmid \binom{n}{m} \Rightarrow m\prec_{p}n $ olduğunu gösterelim. Bu ifadenin karşıt tersi $m\not\prec_{p}n \Rightarrow p \mid \binom{n}{m}$ olur. Bu da önermesi ile özdeştir. Aslında daha güçlüsünü ispat edeceğiz.

Kummer Teoremi: $n-m$ ile $m$ sayılarının $p$ tabanında toplamında, elde sayısı $\Delta_p\left(\binom{n}{m}\right) = \dfrac{\delta_p(m) + \delta_p(n-m) - \delta_p(n)}{p-1}$ ye eşittir.
İspat:
Her basamaktaki elde $c_i = \begin{cases} 1, & a_i + k_i \geq p \\ 0, & a_i + k_i < p \\ \end{cases}$ şeklinde tanımlanır.

Ayrıca $n$ nin $p$ tabanındaki basamakları, $b_i = a_i + k_i + c_{i-1} - p\cdot c_i$ şeklinde tanımlanır. Özel olarak $c_{-1}=0$ alınabilir. Ayrıca $b_s$ hesaplanırken elde olmayacağı için $c_s = 0$ dır.
$$\begin{array}{rcl}
\delta_p(m) + \delta_p(n-m) - \delta_p(n) &=& \sum\limits_{i=0}^s a_i + \sum\limits_{i=0}^s k_i - \sum\limits_{i=0}^s b_i = \sum\limits_{i=0}^s (a_i+k_i-b_i)\\
&=& \sum\limits_{i=0}^s (pc_i - c_{i-1}) \\
&=& \sum\limits_{i=0}^s (p-1)c_i + \sum\limits_{i=0}^s (c_i - c_{i-1}) \\
&=& \sum\limits_{i=0}^s (p-1)c_i + c_s - c_{-1} \\
&=& \sum\limits_{i=0}^s (p-1)c_i
\end{array}$$ Bu durumda $\Delta_p\left(\binom{n}{m}\right) =\dfrac{\delta_p(m) + \delta_p(n-m) - \delta_p(n)}{p-1} = \sum\limits_{i=0}^s c_i$ $\blacksquare$

$ m\not\prec_{p}n \Leftrightarrow \sum\limits_{i=0}^s c_i > 0 \Rightarrow p \mid \binom{n}{m}$.

Not:
Bu soru, Lucas Teoremi ile doğrudan ilgilidir.

Kirişler dörtgeninin çemberinin merkezi $O$ olsun. $C$ nin $ON$ üzerindeki çapına göre simetriği $E$ olsun. $CN=NE$ ve $ON\bot CE$ olacaktır. $BD\bot ON$ olduğu için $BD\parallel CE$ ve $\angle BNC=\angle NCE=\angle NEC=\angle ANB$ olur ki, bu da $A,N,E$ noktalarının doğrusal olduğu anlamına gelir.



$\angle ANC=\angle AOC=2\cdot \angle AEC$ bağıntısı $A,N,O,C$ noktalarının çembersel olduğu anlamına gelir. Bu çemberin $OL$ yi kestiği nokta $P$ olsun. $AP$ küçük yayının ölçüsü $\angle AOP/2$ yani, $\angle ANB/2$ kadardır. Bu durumda $NB$ doğrusu söz konusu çemberi $P$ de keser. $\angle PNO={90}^{\circ }$ olduğu için $\angle PAO={90}^{\circ}$, yani $PA$ doğrusu, $\left(ABCD\right)$ çemberine teğettir. $PA=PC$ olduğu için de $PC$ doğrusu da teğettir.


Aslında bundan sonrası Pole-Polar gösterimi ve temel özellikleri ile ilgili. Biz soruya geri dönelim.

$PD\cap AC=\{F\}$ olsun.

$F$ noktasının $O$ merkezli çembere göre kuvvetinden $BF\cdot FD=AF\cdot FC$.

$P$ noktasının $O$ merkezli çembere göre kuvvetinden $PA^2=PB\cdot PD$.

$\triangle PAC$ de, Stewart'ın özel halinden $PF^2=PA^2-AF\cdot FC$.
$$PF^2=PB\cdot PD-BF\cdot FD\Rightarrow {\left(PD-FD\right)}^2=PB\cdot PD-BF\cdot FD$$ $$\Rightarrow PD^2+FD^2-2\cdot PD\cdot FD=PD^2-FD\cdot PD-BF\cdot PD-BF\cdot FD$$ $$\Rightarrow BF\cdot PD=-FD^2+FD\cdot PD-FD\cdot BF=FD\left(PD-BF-FD\right)=FD\cdot PB$$
Son elde edilen eşitliği orantı şeklinde yazarsak
$$\dfrac{BF}{FD}=\dfrac{BP}{PD}$$
elde ederiz. $\angle PLF={90}^{\circ }$ bilgisini de dikkate aldığımızda, $\triangle BLD$ üçgeninin iç açıortayı $LF$, dış açıortayı da $LP$ çıkar.

Bu son çıkarımımızı biraz daha teknik bir dille anlatmaya çalışalım.

$P$ ve $F$ noktalarının $B$ ve $D$ noktalarına uzaklıkları oranı aynıdır. Bu durumda, bu tip diğer noktaların geometrik yeri, $B$ ve $D$ noktalarına ait bir Apolonyus çemberidir. $PF$, bu çemberin bir çapı; dolayısıyla da $\angle PLF={90}^{\circ }$ olduğu için de $L$ noktası da geometrik yer üzerindedir. Bu durumda
$$\dfrac{BF}{FD}=\dfrac{BP}{PD}=\dfrac{BL}{LD}$$
olur. Bu da, $BLD$ üçgeninde $LF$ nin iç açıortay olduğu anlamına gelir.

$k\ne 1$ ve $x_k-f\left(x_k\right)=k$ olsun. $\dfrac{f\left(x_k-1-f\left(x_k\right)\right)}{k-1}=\dfrac{f\left(k-1\right)}{k-1}=\dfrac{f\left(x_k\right)-x_k-1}{k-1}=\dfrac{-k-1}{k-1}=-1-\dfrac{2}{k-1}$ olacağından $\left\{\dfrac{f\left(k-1\right)}{k-1}|k\ne 1\right\}$ kümesinin sonlu sayıda elemanı olduğu için $-1-\dfrac{2}{k-1}$ ifadesi sonlu sayıda farklı değer alabilmeli, bu da ancak sonlu sayıda $x_k-f\left(x_k\right)=k$ olduğunda mümkün. Yani $\left\{x-f\left(x\right)|x\in R\right\}$ kümesi sonludur. Sonlu kümelerin en büyük ve en küçük elemanları vardır. Bunlar arasıdan $|x-f(x)|$ ifadesini en büyük yapan değer $x=x_0$ olsun.

$y=x_0-1-f(x_0)$ değişkeni ile $y-f\left(y\right)=y-\left(f\left(x_0\right)-x_0-1\right)\ =2\left(x_0-f\left(x_0\right)\right)$ olur. Bu da $x_0$ ın en büyük şartını $\left|x_0-f\left(x_0\right)\right|=0$ olmadıkça ihlal eder. $|x-f(x)|$ ifadesinin en büyük değeri $\left|x_0-f\left(x_0\right)\right|=0$ olduğuna göre tüm değerleri $0$ dır. Buradan da $f\left(x\right)=x$ elde edilir. Yerine koyduğumuzda $f\left(x-1-x\right)=x-x-1=f(-1)$ olduğu için $f\left(x\right)=x$ verilen denklemi sağlar.

Çemberin merkezi $I$, yarıçapı $1$, söz konusu teğetler dörtgeni $ABCD$ ve çember $AB$, $BC$, $CD$, $DA$ kenarlarına sırasıyla $D,E,F,G$ noktalarında dokunsun.
$\angle GID = 2\alpha$, $\angle DIE = 2\beta$, $\angle EIF = 2\theta$, $\angle FIG = 2\gamma$ olsun.
$AG=AD=\tan \alpha$, $BD=BE=\tan \beta$, $CE=CF=\tan \theta$, $FD=GD=\tan\gamma$ ve $GD=2\sin\alpha$, $DE=2\sin\beta$, $EF=2\sin \theta$, $FG=2\sin \gamma$ olacaktır. Bu durumda $$\begin{array}{rcl}
A_K &=& \dfrac{\sin 2\alpha + \sin 2\beta + \sin 2\theta + \sin 2\gamma}2 = \sin \alpha \cos \alpha + \sin \beta \cos \beta + \sin \theta \cos \theta + \sin \gamma \cos \gamma \\
A_T &=& \tan \alpha + \tan \beta + \tan \theta + \tan \gamma \\
C_K &=& 2\sin\alpha+2\sin\beta+2\sin \theta+2\sin \gamma \\
C_T &=& 2\tan \alpha + 2\tan \beta + 2\tan \theta + 2\tan \gamma
\end{array}$$ olur. $$\dfrac{\sin \alpha \cos \alpha + \sin \beta \cos \beta + \sin \theta \cos \theta + \sin \gamma \cos \gamma}{\tan \alpha + \tan \beta + \tan \theta + \tan \gamma} \geq \left(\dfrac{2\sin\alpha+2\sin\beta+2\sin \theta+2\sin \gamma}{2\tan \alpha + 2\tan \beta + 2\tan \theta + 2\tan \gamma}\right)^2$$ $$\left(\sin \alpha \cos \alpha + \sin \beta \cos \beta + \sin \theta \cos \theta + \sin \gamma \cos \gamma \right)(\tan \alpha + \tan \beta + \tan \theta + \tan \gamma) $$ $$\geq (\sin\alpha+\sin\beta+\sin \theta+\sin \gamma)^2$$ $\sqrt {\sin \alpha \cos \alpha} = a_1$ ve $\sqrt {\tan \alpha} = b_1$ dediğimizde $a_1b_1 = \sin \alpha$ olacağı için eşitsizlik Cauchy–Schwarz'a dönüşür.
Eşitlik $\sin \alpha = \sin \beta = \sin \theta = \sin \gamma$ olduğunda sağlanır. $\alpha + \beta + \theta + \gamma = 180^\circ$ olduğu için açılar $45^\circ$ ve $ABCD$ ve $DEFG$ birer kare olacak. Yani eşitlik, kirişler dörtgeni kare iken sağlanır.

Literatürde Gossiping (Dedikodu Problemi) olarak geçen bir konu sorulmuş:
$n\geq 4$ kişi sayısını göstermek üzere, herkesin tüm bilgiye erişmesi için gerekli telefon görüşmesi sayısı $f(n) = 2n-4$ tür.
O halde sorunun yanıtı $f(6) = 2\cdot 6 - 4 = 8$ dir.

Bollobás'ın The Art of Mathematics kitabında ([1]) Gossiping Dons adlı problemin çözümünde anlatıldığı üzere, bu soru 1970'lerde popüler olmuş bir soruymuş.

Sorunun çözümünde iki temel aşama var:
Birincisi, minimum telefon görüşmesi sayısının $f(n) \leq 2n - 4$ olduğu;
İkincisi, $f(n) = 2n - 5$ görüşmede tüm bilginin paylaşılamadığı, yani $f(n)=2n-4$ olduğu.

Birinci aşama için birkaç çözüm paylaşacağım. İkinci aşama için sonda verdiğim kaynaklara müracaat edebilirsiniz. (Ya da birisi tüm çözümün çevirisini yapıp paylaşabilir.)

Açık şekilde; $f(1) = 0$, $f(2) = 1$.
$3$ kişi için, $A-B$, $A-C$, $B-C$, yani $f(3)=3$.
$4$ kişi için, $A-B$, $C-D$, $A-C$, $B-D$, $f(4)=4$.
$n$ kişi için yapılan görüşmeler $T_n$ listesi ile ifade edilsin. İlk görüşmedeki kişilerden biri $X_n$, son görüşmedeki kişilerden biri $Y_n$ olsun.
$(n+1).$ kişi $X_{n+1}$ olsun. $T_{n+1} = [X_{n+1}X_n] + T_n + [Y_nX_{n+1}]$ şeklinde bir görüşme ile $n+1$ kişi tüm bilgilere erişebilir.
Bu durumda her seferinde fazladan $2$ telefon görüşmesi ile kişi sayısını artırabildiğimiz ortaya çıkıyor. O halde $f(n) \leq 4 + 2(n-4) = 2n - 4$.
Burada $2n-4$ konuşma ile tüm bilgiyi paylaşabildiğimiz ortaya çıkıyor; ama daha az sayıda konuşma ile de belki tüm bilgi paylaşılabilirdi. Onun için $f(n) = 2n - 5$ konuşma ile tüm bilgiyi paylaşamayacağımızı göstermemiz gerekiyor. Sorunun bu kısmı daha zor.

$f(n) \leq 2n-4$ olduğu şu şekilde de gösterilebilir:
$n$ kişiden $4$ ü $A,B,C,D$ olsun. $A$ diğer $n-4$ kişi ile görüşsün.
Sonra $A,B,C,D$ kendi aralarında görüşsün. $f(4)=4$ olduğu için, $4$ görüşme yeterli olacak.
Sonra da $D$ diğer $n-4$ kişi ile görüşsün.
Bu durumda $(n-4)+4+(n-4) = 2n-4$ görüşmeyle herkes tüm bilgiye sahip olabilir.


Kaynaklar:

[1]
Bollobás, B. (2006). The Art of Mathematics: Coffee Time in Memphis. Cambridge: Cambridge University Press. doi:10.1017/CBO9780511816574
Sayfa 136-139.
Google Kitaplar Linki

[2]
Çeşitli Makaleler: https://www.math.uni-bielefeld.de/~sillke/PUZZLES/gossips.pdf

Düzlemde bir parabol alalım ve koordinat sistemini öyle seçelim ki, bu sistemde parabolün denklemi $y=ax^2$, $(a>0)$ olsun. Parabolün iç bölgesindeki $(x,y)$ noktaları (sınırlardaki noktalar dahil) için $y\ge ax^2$ sağlanacaktır.
Şimdi, $y$-eksenine paralel olmayan herhangi bir $y=kx+b$ doğrusunu ele alalım. Bu doğrunun en fazla sonlu bir kısmının ``aydınlanabileceğini'' görelim. Aydınlanmış noktaların birinci koordinatı olan $x$ için $kx+b\ge ax^2$ eşitsizliği sağlanmalıdır. Buradan, $ax^2-kx+b\le 0$ olduğu görülür. Eğer $P\left(x\right)=ax^2-kx+b\ $ $\left(a>0\right)$ polinomunun diskriminantı $D=k^2-4ab$ negatif ise, doğru, parabolü hiç kesmiyor; $D\ge 0$ ise; doğru, parabolü $\left(x_1,y_1\right),\left(x_2,y_2\right)$ gibi, $D=0$ durumunda çakışan, iki noktada keser ve doğrunun aydınlanan kısmı bu iki noktayı birleştiren doğru parçasıdır. $D=0$ durumunda doğrunun bir tek noktası aydınlanmıştır. Böylece, parabolün simetri eksenine paralel olmayan her doğrunun en fazla sonlu bir parçası aydınlanabilir.


Şimdi, sonlu sayıda fener, dolayısıyla, onların aydınlattığı sonlu sayıda parabol, düzlemde nasıl yerleştirilmiş olursa olsun, bu parabollerin hiç birinin simetri eksenine paralel olmayan bir doğrunun tamamı aydınlanamaz. (Böyle bir doğru var mıdır? Bir noktadan geçen $n$ adet parabollerin simetri eksenlerine paralel olan $n$ adet doğru vardır. Bu noktadan geçen diğer doğruların hiçbirisi bu parabollerin simetri eksenlerinden birine paralel değildir.) Bu nedenle düzlemin tamamı aydınlanamaz.


Not:
Bu soru 2000 yılındaki 5. Antalya Matematik Olimpiyatında da sorulmuştur.

Kaynak:
Matematik Dünyası 2000-IV

Bir parabolün iç bölgesini istediğimiz kadar küçük bir açının iç bölgesi içine alabiliriz.
Çünkü, düzlemde koordinat sistemini, şekilde görüldüğü gibi, parabolün tepe noktası orijin ve simetri ekseni $y$-ekseni olacak şekilde seçersek; parabol üzerinde $y$-eksenine göre simetrik olan iki noktadan teğetler çizersek, bu teğetler $y$-eksenin üzerinde bir $A$ noktasında kesişirler. Böylece oluşan açının iç bölgesi, parabolün iç bölgesini içerir. Teğetleri uygun yerden çizerek, oluşan  $\alpha$ açısını istediğimiz kadar küçültebileceğimiz açıktır.

Parabollerin sayısı $n$ olsun ver her bir parabolü köşesi $A_i$, $1\le i\le n$ de olan ve $\dfrac{2\pi}{n}$ den küçük olan $\alpha_i$ açısının içine alalım. Eğer düzlem bu şekilde $\dfrac{2\pi}{n}$ den küçük $n$ tane açı tarafından örtülebilseydi, köşeleri çakışan $n$ tane $\dfrac{2\pi}{n}$ den küçük açı tarafından örtülebilmesi gerekirdi. Fakat bu mümkün değildir; çünkü sözü edilen ortak köşeyi merkez kabul eden bir çember çizilirse, çemberin bu açılarla örtülemeyeceği görülür.

Kaynak:
Sabri YILMAZ
Matematik Dünyası 2000-IV

Aynı soru 1996 yılında 6. Vojtěch Jarník Uluslararası Matematik Yarışması, Kategori 2 Soru 1 de sorulmuş.