Perkuat soal USAMO 2014.
Buktikan bahwa terdapat konstan $c>0$ yang memenuhi syarat berikut: Jika $a,b,n$ adalah bilangan bulat positif sedemikian sehingga $FPB(a+i, b+j)>1$ untuk setiap $i,j \in \{0,1,...,n\}$ maka berlaku
\[\min\{a,b\} > c^{n} n^{n/2}\]
Kita bisa perkuat batas pada soal menjadi $(cn)^{1.09n}$.
Motivasi pada pengerjaan soal ini adalah membatasi faktor-faktor dari $a$ atau $b$ kedalam sesuatu yang bergantung pada $n$. Karena faktor-faktor tersebut terbentuk dari prima-prima, maka yang akan kita batasi adalah faktor prima dari $a$ atau $b$. Tanpa kehilangan keumuman bukti, kita asumsikan saja $a\geq b$, sehingga $\min\{a,b\}=b$ , jadi yang akan kita batasi adalah faktor prima dari $b$.
Hubungan faktor prima $b$ dan bilangan $n$, dapat diperoleh dari syarat $FPB(a+i, b+j)>1$. Syarat ini mengakibatkan untuk setiap pasangan $(i,j)$ dengan $0 \leq i,j \leq n$, terdapat bilangan prima $p_{ij}$ sedemikian sehingga $p_{ij} | a+i$ dan $p_{ij} | b+j$. Untuk ilustrasi kita bisa menuliskan bilangan-bilangan prima ini dalam sebuah matriks $(n+1) \times (n+1)$ dengan entri merupakan bilangan prima $p_{ij}$.
\[\begin{pmatrix}
p_{11} & p_{12} & ... & p_{1n} \\
p_{21} & p_{22} & ... & p_{2n } \\
\vdots & \vdots & \ddots & \vdots \\
p_{n1} & p_{n2} & ... & p_{nn}
\end{pmatrix}\]
Bilangan prima $p$ yang bisa dimasukan ke matrix diatas adalah bilangan-bilangan prima yang relevant. Intinya jika kita "kuli", semakin besar $n$ , kita akan semakin sulit untuk mengisi tabel diatas dengan prima relevant. Perhatikan bahwa karena untuk setiap bilangan prima relevant $p$, pasti terdapat $i,j \leq n$ yang memenuhi $p | a+i$ dan $p | b+j$, maka haruslah memenuhi $p \leq \min(a,b) + n$.
Kita akan mengestimasi banyak prima relevant dan berapa kali mereka muncul di matriks diatas. Jika $p$ adalah sebarang prima, maka banyak kali $p$ berada di matriks diatas adalah paling banyak
\[ \left \lceil \frac{n+1}{p} \right\rceil^2 \]
Ini karena terdapat paling banyak $\left \lceil \frac{n+1}{p} \right\rceil$ buah kelipatan $p$ pada barisan
\[a, a+1, a+2, ... , a+n\]
dan secara similar paling banyak $\left \lceil \frac{n+1}{p} \right\rceil$ untuk $b, b+1, ..., b+n$. Jika $S(M)$ menyatakan banyak prima yang kurang dari sebuah bilangan asli $M$ yang berada pada matriks diatas (dihitung dengan multlipisitas), maka diperoleh
\[S(M) \leq \sum_{\substack{p \leq M, \\ p \, \text{prima}}} \left \lceil \frac{n+1}{p} \right\rceil^2 < \sum_{\substack{p \leq M, \\ p \, \text{prima}}} \left(\frac{n}{p} + 1\right)^2 = n^2 \sum_{\substack{p \leq M, \\ p \, \text{prima}}} \frac{1}{p^2} + 2n \sum_{\substack{p \leq M, \\ p \, \text{prima}}} \frac{1}{p} + \sum_{\substack{p \leq M, \\ p \, \text{prima}}} 1 \]
Dengan Teorema Bilangan Prima [1] kita peroleh
\[\sum_{\substack{p \leq M, \\ p \, \text{prima}}} 1 = O \left( \frac{M}{\log M} \right)\]
Berikutnya kita gunakan estimasi dari :
\[\sum_{\substack{p \leq M, \\ p \, \text{prima}}} \frac{1}{p^2} < 0.4522474200\]
\[\sum_{\substack{p \leq M, \\ p \, \text{prima}}} \frac{1}{p} = O\left(\log (\log M) \right)\]
Untuk kemudahan penulisan, selanjutnya kita sebut $\rho = 0.45224742$.
Jadi diperoleh
\[S(M) < \rho n^2 + 2n \cdot O( \log \log M) + O\left(\frac{M}{\log M}\right) \]
Ide yang muncul dari sini adalah ternyata banyak prima yang $ \leq M$ yang bisa dimasukan ke matriks diatas berbentuk $\rho n^2+ (\text{sesuatu dalam $n$ dan } M)$, sedangkan matriks diatas mempunyai paling banyak $(n+1)^2$ buah prima, jadi sisa sebanyak $(n+1)^2 - \rho n^2 - (\text{sesuatu dalam $n$ dan } M)$ haruslah memenuhi $p>M$, dengan pemilihan $M$ yang bergantung pada $n$, "sisa" ini akan semakin membesar. Kita akan formalisir ide ini, dengan memilih $M$ yang sesuai untuk estimasi kita.
Perhatikan bahwa terdapat lebih dari $(n+1)^2- (\rho n^2 + 2n \cdot O( \log \log M) + O\left(\frac{M}{\log M}\right))$ buah entri pada matriks diatas yang lebih dari $M$, dan karena ada $n+1$ buah kolom maka, berdasarkan Prinsip Pigeonhole terdapat sebuah kolom yang mempunyai lebih dari
\[S(M) = n+1 - \frac{\rho n^2}{(n+1)} -\frac{2n}{n+1} O(\log \log M) - \frac{1}{n+1} O\left(\frac{M}{\log M}\right)\]
buah entri yang lebih besar dari $M$.
Pemilihan $M$ yang terlalu dominant seperti misalnya $M=O((n+1)^3)$, akan menyebabkan faktor $O\left(\frac{M}{\log M}\right) = O\left(\frac{(n+1)^3}{3\log (n+1)}\right)$ yang lebih besar dari $O(n^2)$ sehingga kuantitas diatas akan negatif untuk $n$ yang besar. Kita pilih $M$ yang lebih kecil yaitu $M=K^4(n+1)^2$, dimana $K>0$ sebuah konstanta.
Dengan perhitungan sederhana, dapat dibuktikan bahwa $\lim_{n \rightarrow \infty} \frac{S(K^4(n+1)^2 )}{n/2}=2(1-\rho)$. Ini berarti untuk setiap $\epsilon > 0$, terdapat $N_1$ sedemikian sehingga untuk $n \geq N(\epsilon)$ berlaku
\[S(K^4(n+1)^2)>(2(1-\rho)-\epsilon)\frac{n}{2}\]
Jadi untuk setiap $\epsilon>0$, kita bisa pilih $n$ cukup besar sedemikian sehingga pada $(n+1) \times (n+1)$ matriks diatas terdapat sebuah kolom, katakanlah kolom ke-$i$, sedemikian sehingga terdapat lebih $(2(1-\rho)-\epsilon)\frac{n}{2}$ buah entri pada kolom ini, yang lebih besar dari $K^4(n+1)^2$. Perhatikan bahwa entri-entri yang demikian harus berbeda, karena jika misalkan $p_{ki} = p_{li}$ untuk suatu $k \neq l$, maka dari syarat $p_{ki} | b+k$ dan $p_{ki}=p_{li} | b+i$ diperoleh $p_{ki} | k-i$ , sehingga $p_{ki} \leq |k-i |\leq n < K^4(n+1)^2$.
Jadi diperoleh
\[a+i \geq (K^4(n+1)^2)^{(2(1-\rho)-\epsilon)\frac{n}{2}} = K^{2(2(1-\rho)-\epsilon)n} (n+1)^{(2(1-\rho)-\epsilon)n}\]
Jadi untuk $\epsilon=0.00001$, kita bisa temukan $N$ yang cukup besar sedemikian sehingga
\[\min\{a,b\} \geq (K^2 (n+1))^{1.09n}-n\]
Sedangkan $\lim_{n \rightarrow \infty} \frac{(K^2 (n+1))^{1.09n}-n}{(K^2 n)^{1.09n}} =e^{1.09} $, ini berarti untuk setiap $\epsilon>0$ terdapat $N_2$ sedemikian sehingga untuk $n > \max\{ N_1,N_2 \} $
\[(K^2 (n+1))^{1.09n}-n \geq (e^{1.09} - \epsilon) (K^2 n)^{1.09n}\]
Pilih $\epsilon$ cukup kecil sedemikian sehingga $e^{1.09}-\epsilon> 1$ . Jadi kita peroleh untuk $n> \max \{N_1, N_2\}$ berlaku
\[\min\{a,b\} \geq (e^{1.09} - \epsilon) (K^2n)^{1.09n} > (K^2n)^{1.09n} \]
Tapi ketaksamaan ini berlaku hanya untuk $n> N$ dimana $N=\max\{N_1,N_2\}$, sedangkan untuk $N$ yang lain, karena hanya ada berhingga buah, maka pasti terdapat konstanta $K_1$ sedemikian sehingga
\[\min\{a,b\} \geq (K_1 n)^{1.09n}\]
untuk $n=1, 2, ... , N$.
Jadi apabla kita pilih $c=\min\{K_1, K^2\}$, maka soal terbukti.
Post a Comment: