Perkuat soal USAMO 2014.

03:57:00  

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.

ShareShare on Facebook

TweetShare on Twitter

Pin ItShare on Pinterest