Tübitak Lise 2. Aşama 2022 Soru 2

[matematikolimpiyati]

$k,n$ pozitif tam sayılar olmak üzere $k \geq n!$  ise

                                           $\phi (k) \geq (n-1)!$

olduğunu gösteriniz.

[Metin Can Aydemir]

$k=1$ için sadece $n=1$ durumunu incelememiz yeterlidir. $\phi(1)=1\geq 0!$ olduğundan iddia doğrudur. Genel olarak $n=1$ için de iddia her zaman doğrudur.

$n,k\geq 2$ için $k=p_1^{a_1}p_2^{a_2}\cdots p_m^{a_m}$ diyelim. $p_1^{a_1}p_2^{a_2}\cdots p_m^{a_m}\geq n!$ için $$\phi(k)=p_1^{a_1-1}p_2^{a_2-1}\cdots p_{m}^{a_m-1}(p_1-1)(p_2-1)\cdots (p_m-1)=\frac{k(p_1-1)(p_2-1)\cdots (p_m-1)}{p_1p_2\cdots p_m}\geq \frac{n!(p_1-1)(p_2-1)\cdots (p_m-1)}{p_1p_2\cdots p_m}$$ olacaktır. Genelliği bozmadan $p_1<p_2<\cdots <p_m$ olduğunu kabul edelim. $x>0$ için $\frac{x-1}{x}=1-\frac{1}{x}$ artan bir fonksiyondur. $p_i\geq i+1$ olduğundan $$\frac{p_i-1}{p_i}\geq \frac{i}{i+1}$$ olacaktır. Buradan $$\phi(k)\geq \frac{n!(p_1-1)(p_2-1)\cdots (p_m-1)}{p_1p_2\cdots p_m}\geq \frac{n!\cdot 1\cdot 2\cdots m}{2\cdot 3\cdots (m+1)}=\frac{n!}{m+1}$$ olacaktır. Eğer $n-1\geq m$ olursa $$\phi(k)\geq \frac{n!}{m+1}\geq \frac{n!}{n}=(n-1)!$$ elde edilir.

Eğer $m\geq n$ ise $k\geq p_1p_2\cdots p_m$ ve $p_i\geq i+1$ olduğundan $$\phi(k)=\frac{k(p_1-1)(p_2-1)\cdots (p_m-1)}{p_1p_2\cdots p_m}\geq (p_1-1)(p_2-1)\cdots (p_m-1)\geq 1\cdot 2\cdots m\geq n!\geq (n-1)!$$ elde edilir.

Dolayısıyla $k\geq n!$ ise $\phi(k)\geq (n-1)!$ olacaktır.

[AtakanCİCEK]

Elementer bir yöntem değil ama yine de paylaşmak istedim. Bu soruyu bu teoremlerden türetilen bir eşitsizliğin özel durumu ile ispatlamayı denemiştim fakat her durumu kapsayan geçiş olmadığını fark ettim. Kaldırdığım çözümde $\varphi(k)\geq \varphi(n!)$  olduğunu iddia edip ispatlamaya çalışarak geçiş yapmayı denemiştim ancak bu ifade her zaman sağlanmıyor. İspatı o yüzden daha genel teoremlerle yazmam gerekti.

\[
\varphi(m)\;=\;m\prod_{p\,\mid\,m}\Bigl(1-\tfrac1p\Bigr).
\]

$k$ yı sınırlandıralım.

Her $k\in\mathbb Z_{>0}$ için
\[
m\;:=\;\max\bigl\{\,j\in\mathbb N : j!\le k \bigr\}
\]
iyi tanımlıdır. ($\varphi(n!)\geq (n-1)!$)
Lemma:
$n=p_1^{e_1}p_2^{e_2}\dots p_s^{e_s}$
\[
\varphi(n!)\;\ge\;(n-1)!.
\]

Kanıt: İfademiz
\[
\varphi(n!) \;=\;
n!\prod_{p\le n}\Bigl(1-\tfrac1p\Bigr).
\]
Dolayısıyla
$\varphi(n!)\ge(n-1)!$ eşitsizliği,
\[
\prod_{p\le n}\Bigl(1-\tfrac1p\Bigr)\;\ge\;\frac1n
\tag{1}
\]
ifadesine dönüşür. Bu İfadeyi $n\geq 2 $  için ispatlayalım ve $n=1$  i ayrı kontrol edelim.

Bu ifadenin kanıtı için tümevarım kullanalım. Başlangıç durumumuz $n=2$  için her iki taraf $\frac{1}{2}$ olduğu için sağlanır.

 $n \ge 2$ için
$$
\prod_{p \le n} \left(1 - \frac{1}{p} \right) \ge \frac{1}{n}
$$
eşitsizliği doğru olsun.

 $n+1$ ifadesi için eşitsizliğin iki durumu söz konusu.

1.   $n+1$ asal değilse o zaman $p \le n$ olan asal sayılar kümesi değişmez. Dolayısıyla sol taraf değişmez: 
   $$
   \prod_{p \le n+1} \left(1 - \frac{1}{p} \right) = \prod_{p \le n} \left(1 - \frac{1}{p} \right)
   \ge \frac{1}{n} > \frac{1}{n+1}.
   $$ olduğu kolaylıklar görülebilir.

2.   $n+1$ asalsa o zaman $p = n+1$ çarpıma dahil edilir: 
   $$
   \prod_{p \le n+1} \left(1 - \frac{1}{p} \right)
   = \left(1 - \frac{1}{n+1} \right) \cdot \prod_{p \le n} \left(1 - \frac{1}{p} \right)
   \ge \left(1 - \frac{1}{n+1} \right) \cdot \frac{1}{n}.$$
   $$
   \prod_{p \le n+1} \left(1 - \frac{1}{p} \right) \ge \frac{1}{n+1}
   $$

Her iki durumda da $n+1$ için eşitsizlik sağlanır. Tümevarım biter.  Şimdi $m$ için yazdığımız tanıma dönelim.

\[
m!\;\le\;k\;<\;(m+1)!.\tag{1}
\]

Varsayılan $k\ge n!$ olduğundan
\[
m\;\ge\;n.\tag{2}
\]

Landau Mertens Alt sınırı:

Hardy–Wright (Landau–Mertens) bağı: $m\ge3$ için 
\[
\boxed{\;
\varphi(m) \;>\; \frac{e^{-\gamma}}{\log\log m}\,m
\;}
\tag{LM}
\]

3. $\varphi(k)$ için kaba alt sınır oluşturalım.

(1) ile $k\ge m!$; bağı için Lemma ($LM$) doğrudan kullanılabilir.
\[
\varphi(k)
\;>\;
\frac{e^{-\gamma}}{\log\log k}\;k
\;\ge\;
\frac{e^{-\gamma}}{\log\log(m!)}\;m!.
\tag{3}
\]
$(m-1)!$ için bir stirling teoremi yardımıyla bir bound kuralım. Stirling formülü ve $\log\log(m!) = \log m + O(\log\log m)$ ile
\[
\frac{e^{-\gamma}}{\log\!\log (m!)}\,m! \;\ge\; \frac{m!}{m}
\quad\Longleftrightarrow\quad
\frac{e^{-\gamma}}{\log\!\log (m!)} \;\ge\; \frac{1}{m}.
\tag{1}
\]

Logaritma için üst sınır tahmininde bulunalım.

\[
m! \le m^m \;\Rightarrow\;
\log(m!) \le m \log m.
\]

Buradan bir kez daha log alalım:

\[
\log\!\log(m!) \le \log(m \log m)
= \log m + \log\!\log m.
\]

$\log\!\log m \le \log m$ olduğundan (çünkü $m \ge e$)

\[
\boxed{
\log\!\log(m!) \le 2\log m
}
\tag{2}
\]
(1)'deki ifadeyi (2) ile kaba üstten sınırlarız:
\[
\frac{e^{-\gamma}}{\log\!\log(m!)}
\ge \frac{e^{-\gamma}}{2\log m}.
\]

Dolayısıyla (1)'in sağlanması için yeterli olan koşul:

\[
\frac{e^{-\gamma}}{2\log m} \ge \frac{1}{m}
\ \] ifadesini ispatlamak için $e^{-\gamma}m \ge 2\log m. \tag{3} $ olduğunu göstermek yeterlidir.

$f(m)$ fonksiyonu tanımlayalım.
\[
f(m) = e^{-\gamma}m - 2\log m.
\]

Türevi:\[
f'(m) = e^{-\gamma} - \frac{2}{m}.
\]

$f'(m) > 0$ demek $m > \frac{2}{e^{-\gamma}} \approx 3,56$ anlamına gelir.  Yani $m \ge 4$ iken $f(m)$ artan bir fonksiyondur. En küçük ilgilendiğimiz tam sayı $m = 7$ için çünkü ifade en erken $7$ için fonksiyon pozitif oluyor:
\[
f(4) = e^{-\gamma} \cdot 7 - 2\log 7
\approx 0,03 > 0.
\]

Dolayısıyla

\[
f(m) \ge f(7) > 0
\quad \text{tüm } m \ge 7.
\tag{4}
\] olur. (2) ve (4) birlikte:
\[
\frac{e^{-\gamma}}{\log\!\log(m!)} \ge \frac{1}{m}
\quad \text{tüm } m \ge 7.
\]

Bu da (1)'i sağlar ve şu sonuç elde edilir:

\[
\boxed{
\frac{e^{-\gamma}}{\log\!\log(m!)}\,m!
\ge
\frac{m!}{m}
= (m-1)!
\quad (m \ge 7).
}
\]

$\,m = 1, 2, 3,4,5,6 \,$ durumları da doğrudan elle kontrol edilebilir ve eşitsizlik her durumda sağlanır.
\[
\frac{e^{-\gamma}}{\log\log(m!)}\,m!
\;\ge\;\frac{m!}{m}
\;=\;(m-1)!
\quad\text{(tüm $m\ge 7$).}
\tag{4}
\]
Dolayısıyla (3) $\,+\,$(4):
\[
\varphi(k)\;\ge\;(m-1)!
\quad(m\ge 7).\tag{5}
\] (2) ile $m\ge n$, dolayısıyla monotonluk gereği
\[
(m-1)!\;\ge\;(n-1)!\tag{6}
\]
ve (5)$\,+$(6) birleşince $(*)$ elde edilir. İspat biter.