Dari kemacetan Jakarta ke Dirichlet Divisor Function

Dari kemacetan Jakarta ke Dirichlet Divisor Function

02:54:00   Analytic, Umum,

Ini sebenarnya cuma follow up dari kejadian beberapa hari lalu ketika saya sedang terjebak kemacetan. Saya melihat beberapa mobil yang ada didepan saya , dan biasa nya saya suka melakukan arithmetic kepada angka plat dari mobil-mobil tersebut (kurang kerjaan sih emang, cm klo udah kena macet, main ginian pun jadi).

Kemarin saya menemukan dua mobil didepan saya yang nomor plat-nya menarik. Saya lupa angka-angka persisnya, tapi untuk cerita ini sebut saja lah plat nya adalah B 1856 ESE dan  B 9280 ATE. Ini menarik,  setelah sekian lama saya melakukan kerjaan iseng ini, ini adalah pertama kali nya saya menemukan dua mobil didepan saya  dimana angka plat nya 4 digit dan  memenuhi $x \lvert y$, contoh disini $9280 = 5 \times 1856$.

Dari sini saya berpikir, seberapa langka sih sebenarnya hal ini?

Jadi apabila ada sepasang bilangan bulat $(a,b)$ diambil secara random, berapa sering kah mereka memenuhi $a \lvert b$ atau $b \lvert a$ ?

Perhatikan bahwa  saya menggunakan kata "seberapa sering", untuk hal ini saya akan menggunakan alat yang biasa dipakai di Teori Bilangan Analitik yaitu Natural Density  (Sebenarnya ada bentuk Density yang lain seperti Logarithmic Density dan Analytic Density, tapi dikasus ini Natural Density -nya ternyata  sudah ada, sehingga Logartihmic/Analytic Density nya juga ada dan sama.)

Hal ini dengan melihat kembali suatu hasil dari Cesaro yang mengatakan bahwa apabila dua bilangan diambil secara random maka probabilitas bahwa mereka relatif prima adalah $\frac{1}{\zeta(2)} = \frac{6}{\pi^2}$, disini sebenarnya yang digunakan bukanlah probability yang biasa kita kenal ( yang dengan Borel Algebra dll).  Angka $\frac{1}{\zeta(2)}$ tersebut adalah natural density dari $\{(a,b)  : gcd(a,b)=1\}$.

Pada bukti dari hasil $\frac{1}{\zeta(2)}$ diatas, biasanya digunakan estimasi \[\sum_{n\leq x} \varphi(n) = \frac{3x^2}{\pi^2} + O(x \log x)\],
ini disebut estimasi Mertens.

Perhitungan natural density nomor plat membagi diatas dapat dikerjakan dengan cara serupa menggunakan Dirichlet Divisor Estimation

\[\sum_{n \leq x} d(n) = x \log x + (2 \gamma -1 )x + \Delta(x)\]

Dimana $\Delta(x)= O(\sqrt{x})$, sampai saat ini masih merupakan famous open problem tentang bilangan terkecil $\alpha$ sehingga $\Delta(x) = O(x^{\alpha+\epsilon})$ untuk setiap $\epsilon>0$.
(Aproksimasi untuk $\Delta(x)$ merupakan sebuah topik riset, ini disebut Dirichlet Divisor Problem).

Tapi menurut saya itu agak overkill, jadi saya coba cara yang lebih elementer dibawah ini.

Saya akan menghitung

\[d(\mathcal{A}) = \lim_{N \rightarrow \infty} \frac{\# \{ (x,y) : 1\leq x, y \leq N, x| y \text{ atau } y| x  \} }{\#\{(x,y) :  1\leq x, y \leq N \} } \]

dimana $\mathcal{A} = \{(x,y) \in \mathbb{N}^2 : x| y \text{ atau } y|x \}$.

Perhatikan juga bahwa Natural Density itu bukan Probability Measure, karena tidak memenuhi sifat countably additive  ( $d\left(\bigcup_{i=1}^{\infty} \mathcal{A}_i\right) \neq \sum_{i=1}^{\infty} d(\mathcal{A}_i) $ ) tapi memang dibangun untuk membuat make-sense beberapa prinsip probabilitas terhadap Arithmetic Function (dalam ranah ilmu Teori Bilangan). Kita sebut ekspresi pada limit diatas sebagai $p_N$, dan kita ingin mengetahui $\lim_{N \rightarrow \infty} p_N$.


Untuk bilangan-bilangan kecil, sebenarnya cukup banyak, contoh pada interval $[1,5]$, yang mempunyai $25$ buah pasangan, terdapat pasangan $(1, j)$ dan $(j,1)$, dimana $j= 1, 2, 3, 4, 5$ yang totalnya adalah $10-1=9$ buah, lalu pasangan $(j,j)$ untuk $j=2,3,4,5$ ada $4$ pasangan, dan $(2,4)$ dan $(4,2)$ , jadi ada $9+4+2=15$ pasangan, dan rasio nya $p_5 = \frac{15}{25} = \frac{3}{5}$.

Kita akan representasikan $\{ (x,y) : 1\leq x, y \leq N, x| y \text{ atau } y| x  \}$ sebagai titik lattice pada kuadran pertama.

   

Terdapat tepat $N^2$ buah titik lattice pada kuadran pertama yang memenuhi $1 \leq x,y \leq N$. Kita sebut titik lattice $(a,b)$ dimana $1 \leq a,b \leq N$ yang memenuhi $a\lvert b$ dan $b \lvert a$ sebagai titik bagus, berdasarkan simetri, kita cukup mengitung banyak titik bagus yang berada dibawah garis $y=x$, kemudian mengkalikan hasilnya dengan $2$, dan menambahkan banyak titik bagus pada garis $y=x$

Banyak titik bagus yang berada pada garis $y=x$ adalah $N$.

Kita akan menghitung banyak titik bagus pada  tiap-tiap ruas garis yang berwarna biru diatas, ruas garis biru diatas adalah ruas garis $y=k$ iris $k < x \leq N$, dimana $k=1,2, \cdots, N-1$. Untuk sebarang $k$, banyak bilangan pada ruas garis biru yang merupakan kelipatan $k$ adalah $\left\lfloor \frac{N}{k} \right\rfloor - 1$.  Jadi total titik bagus adalah

\[2 \sum_{k=1}^{N}\left( \left\lfloor \frac{N}{k} \right\rfloor - 1\right) +N  = \sum_{k=1}^{N}2\left( \left\lfloor \frac{N}{k} \right\rfloor\right)- N \]

Sebenarnya dari sini kita bisa menggunakan Teorema Dirichlet yang saya sebutkan diatas.


Tapi mari kita gunakan cara yang lebih elementer (bukti Teorema Dirichlet diatas sebenarnya juga elementer dan menggunakan titik lattice).

Perhatikan bahwa $x-\lfloor x \rfloor < 1$ sehingga $ x-\lfloor x \rfloor = O(1)$ ini berarti

\[\sum_{k=1}^{N}2\left( \left\lfloor \frac{N}{k} \right\rfloor\right)- N = \sum_{k=1}^{N}2\left( \frac{N}{k} - O(1) \right)- N =2N \left( \sum_{k=1}^{N} \frac{1}{k}\right) - O(N)-N = 2N \left(H_N\right)  + O(N)  \]

dimana $H_N =  \sum_{k=1}^{N} \frac{1}{k}$. Untuk menggaproksimasi $H_n$, pandang fungsi $f(x) = \frac{1}{x}$ pada interval $[k, k+1]$ dimana $k \in [1, N]$, fungsi ini monoton turun sehingga

\[  f(k+1) \leq f(x) \leq f(k) \Rightarrow \int_k^{k+1} f(k+1) \, dx \leq \int_k^{k+1} f(x) \, dx \leq \int_k^{k+1}f(k) \, dx \]

Diperoleh

\[f(k+1) \leq \int_k^{k+1}f(x) \, dx \leq f(k)\]

Jumlahkan dari $k=1$ sampai $k=N-1$ diperoleh
\[H_N -1 \leq \int_1^{N} \frac{1}{x} \, dx \leq H_{N-1} \Rightarrow \frac{1}{N} +\log N \leq H_N \leq 1+\log N \]

Sehingga kita peroleh estimasi (tidak kuat tapi cukup) $H_N = O(\log N)$. Jadi

\[ \lim_{N\rightarrow \infty} p_N = \lim_{N\rightarrow \infty}  \frac{2NO(\log N) + O(N)}{N^2} = \lim_{N\rightarrow \infty} 2 O\left(\frac{\log N}{ N}\right) + O\left(\frac{1}{N}\right) =0 \]

Jadi natural density $d(\mathcal{A})=0$, ini menjelaskan cerita awal saya, yaitu mengapa pasangan-pasangan yang demikian sangat jarang ditemukan pada bilangan-bilangan yang besar. Karena semakin besar bilangannya,  pertumbuhan pasangan-pasangan tersebut kalah telak dengan pertumbuhan $N \times N$.

Estimasi lengkap nya sebenarnya sebagai berikut,  banyak pasangan $(a,b)$ dengan $1 \leq a,b \leq N$ dan $a | b$ atau $b|a$ adalah seperti yang telah dihitung diatas

\[\sum_{k=1}^{N}2\left( \left\lfloor \frac{N}{k} \right\rfloor\right)- N \]

dapat dibuktikan $\sum_{k=1}^{N}\left( \left\lfloor \frac{N}{k} \right\rfloor\right) = \sum_{k=1}^n d(k)$ dimana $d(n)$ adalah banyak divisor positif dari $n$.  Lalu dengan estimasi Dirichlet kita peroleh

\[\sum_{k=1}^{N}2\left( \left\lfloor \frac{N}{k} \right\rfloor\right)- N = 2 N \log N + (4\gamma - 2)N + \Delta(N)\]

dimana $\gamma$ adalah Euler-Mascheroni Constant. Jadi apabila dibagi $N^2$ dan di limit diperoleh

\[\lim_{N \rightarrow \infty} 2 \frac{\log N}{N} + \frac{4 \gamma -2}{N} + \frac{\Delta(N)}{N} = 0.\]


No wonder, It is indeed rare :D

Continue Reading

Matriks tanpa kuli

Matriks tanpa kuli

04:13:00   Univ,

Melanjutkan post yang sebelum nya , berikut akan dibahas solusi dari soal awal

Kemarin memang saya salah mengetik soal (harusnya $AX-XA$ dan $AX+XA$), tapi tetap ada bukti bagus nya bahwa persamaan tidak ada solusi, saya akan post jawabannya disini

(FYI no student solved this :(  )

Saya menggunakan soal ini dikelas untuk membuka diskusi mengenai:

1. Review Sifat Diagonalizable, kasus khusus di Matriks Simetrik (Orthogonally Diagonalizable).
2. Orthogonal Basis.
3. Basis Eigenvector.
4. Sifat-Sifat Trace dan hubungannya dengan nilai eigen.

Saya pikir jika mereka mengerjakan soal ini dengan cara kuli, dan mengerti sebagaimana melelahkan cara tersebut. Mereka akan lebih mengapresiasi kegunaan teori-teori dalam mempermudah perhitungan :D .


Soal

Misalkan $X= \begin{pmatrix} 0 &1 &1 &1 \\ -1 &0 &1 &1 \\ -1 &-1 &0 &1 \\ -1 &-1 &-1 &0 \end{pmatrix}$.

Tentukan semua matriks real simetrik $A$ yang berukuran $4 \times 4$ dan memenuhi:

\[ (AX-XA) \begin{pmatrix} 1 \\ -1 \\ -1 \\ 1 \end{pmatrix} = \begin{pmatrix} -5 \\ 5 \\ 5 \\ -5 \end{pmatrix} \qquad (AX-XA) \begin{pmatrix} 1 \\ 1 \\ 1 \\ 1 \end{pmatrix} = \begin{pmatrix} 1 \\ 1 \\ 1 \\ 1 \end{pmatrix} \qquad (AX-XA) \begin{pmatrix} 1 \\ 0 \\ 0 \\ -1 \end{pmatrix} = \begin{pmatrix} 2 \\ 0 \\ 0 \\ -2 \end{pmatrix} \]


Solusi : 

Perhatikan bahwa $X^T=-X$, yakni $X$ skew-simetrik. Misalkan $B=AX-XA$, maka berlaku

\[B^T = (AX-XA)^T = (AX)^T - (XA)^T = X^T A^T - A^T X^T = -XA-(-AX) = AX-XA=B\]

Jadi $B$ adalah matriks simetrik.

Perhatikan juga bahwa vektor-vektor
\[\mathbf{v}_1 = \begin{pmatrix} 1 \\ -1 \\ -1 \\ 1 \end{pmatrix}, \qquad \mathbf{v}_2 = \begin{pmatrix} 1 \\ 1 \\ 1 \\ 1 \end{pmatrix}, \text{ dan } \mathbf{v}_3=\begin{pmatrix} 1 \\ 0 \\ 0 \\ -1 \end{pmatrix}\]

 adalah eigenvector dari $B$ yang saling orthogonal ($\langle v_i, v_j \rangle =0$ untuk $i \neq j$), dengan nilai eigen secara berturut-turut $-5$, $1$ dan $2$ .

Lalu karena $Trace(AX - XA) = 0$ dan $Trace$ adalah hasil penjumlahan dari nilai eigen, diperoleh $\lambda -5 + 1 + 2 = 0$, jadi nilai eigen yang satu lagi adalah $\lambda = 2$.

Karena $B$ adalah matriks simetrik maka $B$ dapat didiagonalkan secara orthogonal. Dengan kata lain terdapat matriks orthogonal $P$ (yakni matriks yang memenuhi $P^T = P^{-1}$)  sedemikian sehingga

\[P^T B P  = D= \begin{pmatrix} -5 &0 &0 &0 \\ 0 &1 &0 &0 \\ 0 &0 &2 &0 \\ 0 &0 &0 &2
\end{pmatrix} \]

Perhatikan bahwa kolom-kolom dari matriks $P$ adalah eigenvector $B$ sesuai dengan urutan nilai eigen di diagonal, dan karena $P^T P = P^{-1} P = I$, maka kolom-kolom dari $P$ adalah eigenvektor yang orthonormal .

Seperti yang telah disebutkan sebelum nya karena $B$ dapat didiagonalkan secara orthogonal, ini berarti eigenvector dari $B$ pasti membentuk basis orthonormal, yaitu vektor-vektor kolom dari matriks $P$. Kita akan menentukan vektor-vektor ini agar dapat membentuk matriks $P$.

Pada soal sudah diberikan $3$ buah eigenvector yang orthogonal, yakni $\mathbf{v}_1$, $\mathbf{v}_2$, dan $\mathbf{v}_3$.

Kita cukup membagi vektor-vektor ini dengan panjang mereka masing-masing sehingga diperoleh vektor orthonormal:

\[\mathbf{\tilde{v}}_1 = \begin{pmatrix} \frac{1}{2} \\ -\frac{1}{2} \\ -\frac{1}{2} \\ \frac{1}{2} \end{pmatrix}, \qquad \mathbf{\tilde{v}}_2 = \begin{pmatrix} \frac{1}{2} \\ \frac{1}{2} \\ \frac{1}{2} \\ \frac{1}{2} \end{pmatrix}, \text{ dan } \mathbf{\tilde{v}}_3=\begin{pmatrix} \frac{1}{\sqrt{2}} \\ 0 \\ 0 \\ -\frac{1}{\sqrt{2}} \end{pmatrix}\]

Satu vektor lagi yang orthogonal dengan $\mathbf{v}_1$, $\mathbf{v}_2$ dan $\mathbf{v}_3$ adalah

\[\mathbf{v}_4 = \begin{pmatrix} 0 \\ 1 \\ -1 \\ 0 \end{pmatrix}\]

vektor ini dapat diperoleh dengan mudah dari bentuk  $\mathbf{v}_1$, $\mathbf{v}_2$ dan $\mathbf{v}_3$  ( sebenarnya semua kelipatan dari $\mathbf{v}_4$ juga bisa).  Sehingga bentuk normalize nya adalah

\[\mathbf{\tilde{v}}_4 = \begin{pmatrix} 0 \\ \frac{1}{\sqrt{2}} \\ -\frac{1}{\sqrt{2}} \\ 0 \end{pmatrix}\]

Jadi kita telah memperoleh basis orthonormal eigenvector \[\{\mathbf{\tilde{v}}_1, \mathbf{\tilde{v}}_2, \mathbf{\tilde{v}}_3, \mathbf{\tilde{v}}_4 \}.\]

 Basis orthonormal eigenvector diatas tidaklah unik, karena apabila salah satu $\mathbf{\tilde{v}}_i$ diganti dengan $-\mathbf{\tilde{v}}_i$ kita juga memperoleh basis orthonormal lain. Tapi setiap basis orthonormal eigenvector pasti akan mendiagonalkan $B$, dan karena bentuk diagonal dari $B$ itu unik terhadap urutan nilai eigen di diagonal, maka setiap basis akan memperoleh matriks diagonal yang sama, tergantung urutan meletakkan eigenvektor pada kolom $P$. Disini kita akan meletakan $\mathbf{\tilde{v}}_i$ pada kolom ke-$i$ jadi diperoleh matriks

\[P= \begin{pmatrix}\frac{1}{2} & \frac{1}{2} & \frac{1}{2} \, \sqrt{2} & 0 \\-\frac{1}{2} & \frac{1}{2} & 0 & \frac{1}{2} \, \sqrt{2} \\-\frac{1}{2} & \frac{1}{2} & 0 & -\frac{1}{2} \, \sqrt{2} \\\frac{1}{2} & \frac{1}{2} & -\frac{1}{2} \, \sqrt{2} & 0 \end{pmatrix}\]

Dimana sifat orthonormal menyebabkan $P^{-1}  = P^T$. Jadi $P^T B P  = D$ mengakibatkan

\[AX-XA=B = PDP^T = \begin{pmatrix} 0 & \frac{3}{2} & \frac{3}{2} & -2 \\\frac{3}{2} & 0 & -2 & \frac{3}{2} \\\frac{3}{2} & -2 & 0 & \frac{3}{2} \\ -2 & \frac{3}{2} & \frac{3}{2} & 0 \end{pmatrix} \]
(Perhitungan $PD$ diatas tidak rumit karena $D$ memuat banyak $0$, dan pada perhitungan $(PD)P^T$ kita cukup menghitung entri dibawah diagonal dan di diagonal karena $B$ simetrik.)

Dengan operasi baris elementer bisa diperoleh bahwa inverse dari $X$ adalah

\[X^{-1} = \begin{pmatrix}0 & -1 & 1 & -1 \\1 & 0 & -1 & 1 \\-1 & 1 & 0 & -1 \\1 & -1 & 1 & 0 \end{pmatrix}\]

sehingga

\[AX-XA = B \Rightarrow  X^{-1}A - AX^{-1} = X^{-1}BX^{-1}=\begin{pmatrix}-4 & -\frac{3}{2} & \frac{11}{2} & -6 \\-\frac{3}{2} & 10 & -12 & \frac{11}{2} \\\frac{11}{2} & -12 & 10 & -\frac{3}{2} \\-6 & \frac{11}{2} & -\frac{3}{2} & -4\end{pmatrix}\]

Tapi ini tidak mungkin karena $Trace(X^{-1}A  - A X^{-1}) = 0$ sedangkan $Trace$ dari matriks di sisi kanan sama dengan $12$. Kontradiksi ini membuktikan bahwa tidak ada $A$ yang memenuhi kondisi soal.

Untuk soal yang menggunakan kondisi singular, cara nya serupa, kondisi $det(A) = 0$ hanya digunakan untuk menentukan bahwa ada nilai eigen yang nol.

Continue Reading

Soal ujian dan PR matriks.

Soal ujian dan PR matriks.

00:56:00   Univ,

Beberapa hari yang lalu, saya membuat soal ujian tentang matriks. Tujuan nya adalah memberikan "beberapa materi" yang terangkum pada satu soal.

Tapi ujung-ujung nya, karena sepertinya soalnya kesusahan, saya melakukan beberapa modifikasi agar soalnya bisa dikerjakan secara "manusiawi" dengan cara "kuli" ,  yang saya sebut soal iseng.

Berikut soal awal nya :

Soal 1

Misalkan $X= \begin{pmatrix} &0 &1 &1 &1 \\ &-1 &0 &1 &1 \\ &-1 &-1 &0 &1 \\ &-1 &-1 &-1 &0 \end{pmatrix}$.

Tentukan semua matriks real simetrik $4 \times 4$ , katakanlah $A$ yang memenuhi:

\[ (AX-XA) \begin{pmatrix} 1 \\ -1 \\ -1 \\ 1 \end{pmatrix} = \begin{pmatrix} -5 \\ 5 \\ 5 \\ -5 \end{pmatrix} \qquad (AX-XA) \begin{pmatrix} 1 \\ 1 \\ 1 \\ 1 \end{pmatrix} = \begin{pmatrix} 1 \\ 1 \\ 1 \\ 1 \end{pmatrix} \qquad (AX-XA) \begin{pmatrix} 1 \\ 0 \\ 0 \\ -1 \end{pmatrix} = \begin{pmatrix} 2 \\ 0 \\ 0 \\ -2 \end{pmatrix} \]

Soal 1 (Iseng version)

Misalkan $X= \begin{pmatrix} &0 &1 &1 &1 \\ &-1 &0 &1 &1 \\ &-1 &-1 &0 &1 \\ &-1 &-1 &-1 &0 \end{pmatrix}$.

Tentukan semua matriks real simetrik $4 \times 4$ , katakanlah $A$ yang memenuhi:

\[ (AX+XA) \begin{pmatrix} 1 \\ -1 \\ -1 \\ 1 \end{pmatrix} = \begin{pmatrix} -1 \\ 1 \\ 1 \\ -1 \end{pmatrix} \qquad (AX+XA) \begin{pmatrix} 1 \\ 1 \\ 1 \\ 1 \end{pmatrix} = \begin{pmatrix} 1 \\ 1 \\ 1 \\ 1 \end{pmatrix} \qquad (AX+XA) \begin{pmatrix} 1 \\ 0 \\ 0 \\ -1 \end{pmatrix} = \begin{pmatrix} 2 \\ 0 \\ 0 \\ -2 \end{pmatrix} \]


Edited: kedua soal tidak mempunyai solusi (buktinya akan ditulis nanti)

Tujuan saya mengubah soalnya menjadi bentuk iseng adalah agar mahasiwa tidak melakukan banyak perhitungan apabila mereka ingin menggunakan cara-cara kuli seperti sebagai berikut:

Yaitu menyatakan $B=AX+XA$ dan kemudian menyatakan

\[B = \begin{pmatrix} &a_{11} &a_{12} &a_{13} &a_{14} \\ &a_{21} &a_{22} &a_{23} &a_{24} \\ &a_{31} &a_{32} &a_{33} &a_{34} \\ &a_{41} &a_{42} &a_{43} &a_{44} \end{pmatrix} \]
Tapi ini berarti akan diperoleh persamaan linear 16 variabel dengan 12 buah persamaan (13 buah jika berhasil mengobservasi bahwa $trace(B)=0$). Lebih lagi setelah matriks $B$ ditemukan, untuk menemukan $A$, masih ada beberapa persamaan yang akan diselesaikan dari $AX+XA=B$ (Tentu saja cara ini tidak praktis).

Beberapa dari nya melakukan menganalisa lebih lanjut sebagai berikut:
Perhatikan bahwa $X$ adalah matriks skew-simetrik yaitu memenuhi $X^T = -X$. Jadi jika $A$ adalah matriks simetrik (i.e $A^T = A$) maka
\[(AX+XA)^T = (AX)^T +(XA)^T = X^T A^T +A^TX^T = -XA + (-AX) = - (AX+XA) \]
diperoleh $AX+XA$ adalah matriks skew-simetrik. Sehingga semua entri pada diagonal utama matriks $B$ adalah nol. Sehingga diperoleh

\[B = \begin{pmatrix} &0 &x &y &z \\ &-x &0 &p &q \\ &-y &-p &0 &r \\ &-z &-q &-r &0 \end{pmatrix}\]

Dengan begini, soal tereduksi menjadi $12$ persamaan dengan $6$ variabel. (Ya, ada mahasiswa yang menyelesaikan versi iseng dengan cara ini.)

Seperti yang saya bilang sebelumnya, soal versi iseng sebenarnya mereduksi banyak perhitungan, dan tidak perlu sampai $12$ persamaan. Cukup dilihat hasil persamaan dari baris pertama kita peroleh sistem persamaan
\[-x-y+z=-1 \qquad x+y+z=1 \qquad -z=2\]
yang berakibat persamaan tidak konsisten $x+y=3$ dan $x+y=-1$. Jadi tidak ada matriks $B$ yang memenuhi dan tidak matriks $A$ yang memenuhi.
(Iseng-nya sebenarnya pengen lihat apakah ada mahasiswa yang beneran mengerjakan semua 12 persamaan dan kemudian ujung-ujungnya mendapatkan bahwa jawabannya ternyata tidak ada :D )


Kembali lagi ke soal awal,  tidak bisa dibuat kontradiksi seperti diatas, dan apabila ada yang mengerjakan sistem persamaan $6$ variabel $12$ persamaan, maka solusi nya unik dan diperoleh bentuk $B$ yang komponen nya pecahan-pecahan (dengan diagonal entri nya semua nol), selanjutnya menyelesaikan persamaan $AX+XA=B$.

Solusi-nya akan saya post nanti (Besok adalah deadline untuk soal awal diatas, semoga dikerjain) bersamaan dengan soal versi lebih kejam (mirip soal yang diberi teman saya, dia kasi yang $3 \times 3$,  yang ini $4 \times 4$) :

Tentukan semua matriks real singular simetrik $4 \times 4$ , katakanlah $A$ yang memenuhi:

\[  A \begin{pmatrix} 1 \\ -1 \\ -1 \\ 1 \end{pmatrix} = \begin{pmatrix} -1 \\ 1 \\ 1 \\ -1 \end{pmatrix} \qquad A \begin{pmatrix} 1 \\ 1 \\ 1 \\ 1 \end{pmatrix} = \begin{pmatrix} 1 \\ 1 \\ 1 \\ 1 \end{pmatrix} \qquad A \begin{pmatrix} 1 \\ 0 \\ 0 \\ -1 \end{pmatrix} = \begin{pmatrix} 2 \\ 0 \\ 0 \\ -2 \end{pmatrix} \]

mengapa ini lebih kejam? karena tidak seperti soal awal dan soal iseng, yang semua kondisi nya adalah persamaan linear. Soal ini punya kondisi $det(A) =0$, yang melibatkan penjumlahan dari perkalian plus-minus. Still, ada cara bagus nya sebenarnya.

Continue Reading

Soal IMO 2015 Nomor 6

Soal IMO 2015 Nomor 6

23:04:00   Olimpiade Matematika,

IMO 2015, Soal 6

Diberikan barisan bilangan bulat $a_1, a_2, \cdots, a_n, \cdots$ yang memenuhi
i) $1 \leq a_j \leq s$ untuk setiap $j \geq 1$
ii)  $k+a_k \neq l+a_l$ untuk setiap $1 \leq k < l$.

Buktikan bahwa terdapat bilangan bulat $N$ dan $b$ sedemikian sehingga

\[ \left| \sum_{i=m+1}^{n} (a_i-b) \right| \leq \left(\frac{s-1}{2}\right)\]
untuk setiap $n> m \geq N$

Solusi:

Definisikan $b_i:= a_i + i$. Berdasarkan sifat ii)  $b_i$ adalah bilangan bulat yang berbeda satu sama lain dan dari sifat i) berlaku  \[i+1 \leq b_i \leq s+i.\]


Pertama-tama kita buktikan dulu lemma berikut.

Lemma 1
Terdapat himpunan $\mathcal{B} \subset \mathbb{N}$ yang memenuhi $|\mathcal{B}|=b \leq s$ sedemikian sehingga jika $x \in \mathbb{N}$ dan $x \neq b_j$ untuk setiap $j$ maka $x \in \mathcal{B}$.  Dengan kata lain, hanya ada berhingga banyaknya bilangan yang tidak berada pada himpunan $R=\{b_1, b_2,  b_3, \cdots, \}$.


Bukti Lemma:
Misalkan tidak demikian, maka ini berarti $R=\{b_1, b_2,  b_3, \cdots, \}=\mathbb{N}$ atau himpunan $\mathcal{B}$ yang demikian mempunyai banyak anggota lebih dari $s$ (bisa saja punya tak berhingga anggota).  Kemungkinan pertama $R=\mathbb{N}$ tidak mungkin karena $1< 1+i \leq a_i + i =b_i$.

Kemudian misalkan  kemungkinan kedua terjadi yaitu $\mathcal{B}$ mempunyai lebih dari $s$ anggota, ini berarti terdapat lebih dari $s$ buah bilangan yang tidak berada di $R$. Misalkan $1=r_1 <  r_2 <  \cdots < r_{s+1}$ adalah $s+1$ buah bilangan pertama yang tidak berada di $R$. Perhatikan bahwa

\[\begin{align*} 2 & \leq b_1 \leq s+1 \\
3 &\leq b_2 \leq s+2 \\
\,  &\,  \cdots \,  \,   \\
r_{s+1} +1 &\leq b_{r_{s+1}} \leq s+r_{s+1}\end{align*} \]

Ini berarti $b_1, b_2, \cdots, b_{r_{s+1}}$ adalah $r_{s+1}$ buah bilangan berbeda yang berada pada interval $[2,s+r_{s+1}]$,  sehingga terdapat $s+r_{s+1}-1 - (r_{s+1})=s-1$ buah bilangan lain yang berada pada interval tersebut,  $s-1$ buah bilangan yang tersisa ini bisa mungkin anggota $R$ bisa juga tidak,  ini berarti pada interval $[2,s+r_{s+1}]$ terdapat paling banyak $s-1$ buah bilangan yang bukan anggota $R$, akan tetapi $r_2, r_3 , \cdots, r_{s+1}$ semuanya juga berada di interval $[2, s+r_{s+1}]$ dan  merupakan $s$ buah bilangan yang juga bukan anggota $R$, kontradiksi. Lemma terbukti.



Sekarang kita akan mengestimasi nilai dari jumlah parsial

\[\sum_{j=m+1}^n b_j\]

untuk $m$ cukup besar.

Kita notasikan sebagai $\mathcal{N}_j = \{1,2, \cdots, j\}$ . Jelas bahwa $\mathcal{N}_i \subset \mathcal{N}_j$ untuk setiap $i < j$.

Berdasarkan Lemma 1, himpunan $\mathcal{B}$ adalah himpunan yang berhingga, yang mempunyai $b$ buah anggota dimana $b \leq s$. Jadi di himpunan $\mathcal{B}$ terdapat anggota yang paling besar di himpunan tersebut, sebutlah $N$. Dengan demikian, untuk setiap $x \in \mathcal{B}$ selalu berlaku $x \leq N$, sehingga $x \in \mathcal{N}_N$, diperoleh $\mathcal{B}\subseteq \mathcal{N}_N$.

Diperoleh, untuk setiap $n > m \geq N$ maka berlaku \[\mathcal{B} \subseteq \mathcal{N}_N \subseteq \mathcal{N}_m \subset \mathcal{N}_n\]


Lemma 2

Untuk sebarang $v>N$ berlaku
\[\mathcal{N}_{v+1} \setminus \mathcal{B} \subseteq \{b_1, b_2 , \cdots, b_v\}\subseteq \mathcal{N}_{v+s} \setminus \mathcal{B}.\]

Bukti Lemma: 
Misalkan terdapat $x \in \mathcal{N}_{v+1} \setminus \mathcal{B}$  dan $x \neq b_j$ untuk $1 \leq j \leq v$. Karena $x \not \in \mathcal{B}$, maka $x=b_k$ untuk suatu $k$ dan karena $x \neq b_j$ untuk $1\leq j \leq v$  maka haruslah $k>v$, kita simpulkan $x=b_{k}$ dimana $k \geq v+1$. Lalu karena $x \in \mathcal{N}_{v+1}$ diperoleh $x \leq v+1$, jadi
\[v+1 \geq x=b_k \geq k+1 \geq v+2 \]
kontradiksi, jadi terbukti $\mathcal{N}_{v+1} \setminus \mathcal{B} \subseteq \{b_1, b_2 , \cdots, b_v\}$.
Sekarang ambil sebarang $x \in  \{b_1, b_2 , \cdots, b_v\}$, maka $x \not \in \mathcal{B}$, dan $x=b_k$ untuk suatu $k \leq v$, diperoleh $x=b_k \leq k+s \leq v+s$, jadi $x \in \mathcal{N}_{v+s}$, bersama dengan $x \not \in \mathcal{B}$ dapat disimpulkan bahwa $x \in \mathcal{N}_{v+s}\setminus \mathcal{B}.$ Lemma terbukti.


Lemma 3
Untuk $m>N$ , terdapat tepat  $b-1$ buah bilangan di $\{m+2, m+3, \cdots, m+s\}$ yang merupakan anggota dari $\{b_1, b_2, \cdots, b_m\}$

Bukti Lemma :
Dari Lemma 2, karena $m>N$ berlaku $\mathcal{N}_{m+1} \setminus \mathcal{B} \subseteq \{b_1, b_2 , \cdots, b_m\}$, dan karena $|\mathcal{N}_{m+1} \setminus \mathcal{B}| = m+1-b$ dan $|\{b_1, b_2 , \cdots, b_m\}| = m$ maka terdapat tepat $m-(m+1-b)=b-1$ buah suku dari himpunan $\{b_1, b_2 , \cdots, b_m\}$ yang berada pada himpunan $\{m+2, m+3, \cdots, m+s\}$.

Kita akan menghitung nilai minimum dari $\sum_{j=m+1}^n b_j$. Jumlahan ini dapat ditulis

\[\sum_{j=1}^{n} b_j - \sum_{j=1}^{m} b_j\]

agar minimum, maka $\sum_{j=1}^{m} b_j$ harus sebesar-besarnya, dan dar Lemma terdapat $b-1$ buah suku pada $\{b_1, b_2, \cdots, b_{m}\}$ yang berada di $\{m+2, m+3, \cdots, m+s\}$, jadi agar  sebesar-besarnya, $b-1$ buah suku ini adalah $m+s , m+s-1, \cdots , m+s-b+2$.

Kemudian suku-suku pada $\{b_{m+1}, b_{m+2}, \cdots, b_n\}$ harus sekecil-kecilnya, dan karena untuk $j \geq m+1$ berlaku $b_{j} \geq j+1 \geq m+2$, maka yang terkecil adalah mulai dari $m+2, m+3, \cdots$ dan seterusnya, tapi perhatikan dari paragraf sebelumnya bahwa nilai $m+s-b+2, m+s-b+3, \cdots, m+s$ sudah terpakai untuk pada suku-suku di $\{b_1, b_2, \cdots, b_{m+1}\}$ (dan harus terpakai). Ini berarti pada himpunan $\{m+1, m+2, \cdots, m+s\}$ kita hanya boleh menggunakan

\[\{m+2 , m+2 , \cdots, m+s-b+1 \}\]

karena $\sum_{j=m+1}^n b_j$ memuat $n-m$ suku, dan kita baru memakai $|\{m+2 , m+2 , \cdots, m+s-b+1 \}| = s-b$ suku, maka masih harus ada $n-m-s-b$ buah suku lain, dan kemungkinan terkecil nya adalah setelah melangkahi $\{m+s-b+2, \cdots, m+s\}$ (karena sudah terpakai) yaitu

\[\{m+s+1, m+s+2, \cdots , n+b \}\]

Sehingga diperoleh
\[\begin{align*}\sum_{j=m+1}^{n} b_j &\geq \sum_{j=m+2}^{m+s-b+1} j + \sum_{j=m+s+1}^{n+b} j \\ &= \left( \frac{2m+s-b+3}{2} \right)(s-b) + \left(\frac{n+m+s+b+1}{2}\right) \left(n+b-m-s\right) \\ &= \left(\frac{s-b}{2}\right) (m-2b-n+2) +(n-m)\left( \frac{n+m+s++b+1}{2}\right) \\ &= (n-m) \left(\frac{n+m+2b+1}{2}\right) -(b-1)(s-b) \end{align*}\]

Jadi
\[\begin{align*}\sum_{j=m+1}^n (a_j - b) &= \sum_{j=m+1}^n (b_j-j-b) \\ &= \sum_{j=m+1}^n b_j -\sum_{j=m+1}^n j - (n-m)b \\ &\geq (n-m) \left(\frac{n+m+2b+1}{2}\right) -(b-1)(s-b) - \sum_{j=m+1}^n j - (n-m) b \\ &= -(b-1)(s-b)\end{align*}\]

Diperoleh
\[\sum_{j=m+1}^n (a_j - b) \geq -(b-1)(s-b) \qquad (1)\]

Sekarang akan di estimasi nilai maksimum dari $\sum_{j=m+1}^n b_j$.  Berdasarkan Lemma 3, karena $n > N$, maka terdapat tepat $b-1$ buah anggota $\{n+2, n+3, \cdots, n+s\}$ yang juga anggota $\{b_1, b_2, \cdots, b_n\}$. Jadi agar maksimum, $b-1$ buah anggota-anggota ini haruslah yang sebesar-besarnya yaitu $n+s-b + 2, n+s-b+3, \cdots, n+s$.

Karena $\sum_{j=m+1}^n b_j$ mempunyai $n-m$ suku, maka yang perlu dibatasi masih $n-m-b+1$ buah suku lagi dan mereka harus berasal dari himpunan $\{1,2 ,\cdots, n+1\}$ (jika tidak demikian maka $\{n+2, \cdots, n+s\}$ memuat lebih dari $b-1$ buah suku), dan agar maksimum dipilih $n-m-b+1$ buah anggota terbesar di $\{1,2, \cdots, n+1\}$ yaitu $n+1, n, \cdots,  m + b +1$.

Diperoleh
\[\begin{align*}\sum_{j=m+1}^n b_j &\leq \sum_{j=n+s-b+2}^{n+s} j + \sum_{j=m+b+1}^{n+1} j \\  &= \left(\frac{2n+2s-b+2}{2} \right)\left(b-1\right) + \left(\frac{n+m+b+2}{2}\right) \left(n-m-b+1\right) \\ &= \left(\frac{n-m+2s-2b}{2} \right)(b-1)+ \left(\frac{n+m+b+2}{2}\right) \left(n-m\right) \\ &=(b-1)(s-b) + (n-m) \left(\frac{n+m+2b+1}{2}\right)
\end{align*}\]

Sehingga
\[\begin{align*}\sum_{j=m+1}^n (a_j - b) &= \sum_{j=m+1}^n (b_j-j-b) \\ &= \sum_{j=m+1}^n b_j -\sum_{j=m+1}^n j - (n-m)b \\ &\leq (n-m) \left(\frac{n+m+2b+1}{2}\right) +(b-1)(s-b) - \sum_{j=m+1}^n j - (n-m) b \\ &= (b-1)(s-b)\end{align*}\]

Digabungkan dengan ketaksamaan (1) diperoleh

\[-(b-1)(s-b) \leq \sum_{j=m+1}^n (a_j - b) \leq (b-1)(s-b) \Rightarrow \left| \sum_{j=m+1}^n (a_j - b) \right| \leq (b-1)(s-b) \]

Dengan menggunakan AM-GM diperoleh $(b-1)(s-b) \leq \left(\frac{b-1+s-b}{2}\right)^2 = \left(\frac{s-1}{2}\right)^2$. Sehingga

\[\left| \sum_{j=m+1}^n (a_j - b) \right| \leq \left(\frac{s-1}{2}\right)^2. \]

Q.E.D

Continue Reading

Exercise on Maximal Group

Exercise on Maximal Group

12:30:00   Algebraic,

Well, this one is actually an old random stuff I did when I was undergraduate, I found it on my old harddrive and would like to test what happen if I post it. This is actually an exercise in Martin Isaac Book, and I always forget how to do  this problem properly (I mean really solve it concretely). In fact, I post it here again because I always forget how to solve it. This is a really detailed proof.


Without using Cauchy Theorem or Sylow Theorem prove that If $G$ is a finite group with unique maximal subgroup then $|G|=p^{\alpha}$, for some prime $p$.

We begin with some lemmas, and all the following lemmas assume that $G$ is finite.

Lemma 1
Let $A$ be a nonempty subset of $G$ such that $\langle A \rangle \neq G$ and for any $x\in G \backslash A$ we have $\langle A \cup \{x\} \rangle=G$ then $\langle A \rangle$ is a maximal subgroup.

Proof:
Let $H$ be a subgroup of $G$ such that $\langle A \rangle \subseteq H \subseteq G$, suppose for contrary that $H \neq \langle A \rangle $ and $H \neq G$,  since $\langle A\rangle \neq G$ there exists $x \in H$ with $x \not \in \langle A \rangle $, therefore $x\not \in A$ thus $A \cup \{x\} \subseteq \langle A \rangle \cup \{x\} \subseteq H$ and hence $\langle A \cup \{x\} \rangle \subseteq H$, but by the hypothesis this means $G \subseteq H$, and we have $H=G$, a contradiction.  Therefore either $H=\langle A \rangle$ or $H=G$, which implies $\langle A \rangle$ is maximal subgroup.


Lemma 2
Let $A$ and $B$ are subgroup of $G$. If $G = A \cup B$ then $A=G$ or $B=G$.

Proof:
Let $|G|=n$, $|A|=d_1$, $|B|=d_2$, and $|A\cap B| = d_3$. First we assume that $d_1 \geq d_2$, by Langrange theorem we have $d_1 \lvert n$ and $d_2 \lvert n$, also since $e \in A\cap B$ we have $d_3 \geq 1$. Observe that
\[n=|G|=|A\cup B| = |A| + |B| - |A \cap B| \leq d_1+d_1 -1 = 2d_1-1.\]
If $d_1= n$, then $|A|=|G|$, but since $A \subseteq G$, we have $A=G$, the assertion is proved. Now for $d_1 < n$ since by Langrange $d_1 | n$, we have $n=k d_1$ for a positive integer $k$, but $n \leq 2d_1-1$, thus $k \leq 2- \frac{1}{d_1}$, and we have $k \leq 1$, this leads to $n=d_1$ again. Similarly If we instead assume $d_2 \geq d_1$ then $B=G$.


Lemma 3
If $G$ has a unique maximal subgroup then $G$ is a cyclic group.

Proof:
Let $M$ be the unique maximal subgroup of $G$, let $C(M)=\langle G\backslash M \rangle$, then we have $G = M \cup C(M)$ thus by Lemma 2  we have  $M=G$ or $C(M)=G$, but $M\neq G$ therefore we must have $C(M)=G$.


Define
\[\begin{eqnarray*}&\mathcal{T}_i := \{A \, \lvert A \subseteq G\backslash M \mbox{ and } \lvert A \rvert=i \mbox{ and } i \geq 1 \} \\ &\mathfrak{L} := \{i \, \lvert \, \langle A \rangle = G \mbox{ for all } A \in \mathcal{T}_i\}
\end{eqnarray*}\]

Let $\lvert G \backslash M \rvert = \lambda$, we have \[\mathcal{T}_{\lambda} = \{A \, \lvert A \subseteq G \backslash M \mbox{ and } |A|=\lambda=\lvert G \backslash M \rvert\}=\{ G \backslash M\}\]


Since $\langle G \backslash M \rangle = G$, this means that for every $A \in \mathcal{T}_{\lambda}=\{G \backslash M\}$ we have $\langle A \rangle= \langle  G \backslash M \rangle =G$, therefore $\lambda \in \mathfrak{L}$, in particular $\mathfrak{L} \neq \emptyset$.


Since $\mathfrak{L}$ is nonempty, by the Well-Ordering Principle there exists a smallest elemet $t \in \mathfrak{L}$. If $t=1$, since $1=t \in \mathfrak{L}$, for every $A \in \mathcal{T}_1$ we have $\langle A \rangle =G$ , in particular if we take $A=\{g\}$ where $g\in G\backslash M$, we see that $A \subset G\backslash M$ and $\lvert A \rvert = 1=t$. This means $A\in \mathcal{T}_1$, so that $\langle g\rangle = \langle A \rangle =G$, thus $G$ is cyclic, and the lemma is proved whenever $t=1$.


Next we will prove that $t > 1$ would eventually end with a contradiction. If $t>1$, then $t-1$ is the largest positive integers which fails to be included on $\mathfrak{L}$, equivalently there exists $S \in \mathcal{T}_{t-1}$ with $\langle S \rangle  \neq G$, notice that $|S|=t-1 >0$ thus $S\neq \emptyset$. Define
\[\begin{eqnarray*}&\mathcal{U}_i := \{ B \, \lvert  B \subseteq M \mbox{ and } |B|=i \mbox{ and } i \geq 1 \} \\ &\mathfrak{P} := \{i \, \lvert \, \langle S \cup B \rangle = G \mbox{ for all } B \in \mathcal{U}_i\}
\end{eqnarray*}\]

Observe that $M \subset S \cup M \subseteq \langle S \cup M \rangle \subset G$, since $M$ is maximal we have either $M=\langle S \cup M \rangle$ or $\langle S \cup M \rangle = G$, but $M=\langle S \cup M \rangle$ would implies $S \subset \langle S \cup M \rangle = M$ this is impossible since $S\in \mathcal{T}_1$ which means $S \subset G \backslash M$, thus the only possibility is $\langle S \cup M \rangle=G$. Let $\lvert M \rvert=\mu$, we have
\[\mathcal{U}_{\mu} = \{B \, \lvert B \subseteq M \mbox{ and } \lvert  B \rvert = \mu = \lvert M \rvert\} = \{ M\}\]


Since $\langle S \cup M \rangle=G$,  this means that for every $ B \in \mathcal{U}_{\mu}=\{M\}$ we have $\langle S \cup B \rangle= \langle  S \cup M \rangle =G$, therefore $\mu \in \mathfrak{P}$, in particular $\mathfrak{P} \neq \emptyset$. Since $\mathfrak{P}$ is nonempty, by Well-Ordering Principle there exists a smallest element $l \in \mathfrak{P}$.


 Before we proceed, we will recall what we have so far :
 \[S \subset G \backslash M \qquad S \in \mathcal{T}_{t-1} \qquad  \langle S \rangle \neq G\]
Also  $t\in \mathfrak{L}$ and satisfies
\[\text{for all $A \in \mathcal{T}_t$ we have $\langle A \rangle = G$}\]
and $l\in \mathfrak{P}$ and satisfies
\[\text{for all $B \in \mathcal{U}_l$ we have $\langle S \cup B \rangle = G$}\]


 Now we continue the proof, if $l=1$, since $1=l \in \mathfrak{P}$ we have $\langle S \cup B \rangle =G$ for every $ B \in \mathcal{U}_1$, we will prove that this would implies $\langle S \rangle $ is maximal subgroup. Indeed, take any $x\in G \backslash S$, which implies $x\not \in S$, we divide into two cases:

 i) If $x\in M$ then $\{x\} \subset M$, thus $ \{x\} \in \mathcal{U}_1$ and hence $\langle S \cup \{x\}\rangle =G$.

ii) If $x \not \in M$ then $\{x\}\subset G \backslash M$, thus $S \cup \{x\} \subset G \backslash M$, also since $x\not \in S$ we have $S \cap \{x\} = \emptyset$, together with $S \in \mathcal{T}_{t-1}$ we have $\lvert S \cup \{x\}\rvert = \lvert S \rvert + 1 = t-1+1=t$, therefore $S \cup \{x\} \in \mathcal{T}_t$. Since $t\in \mathfrak{L}$ every $A \in \mathcal{T}_t$ satisfies $\langle A \rangle =G$ thus in particular $S \cup \{x\} \in \mathcal{T}_t$ implies $\langle S \cup \{x\} \rangle = G$.


In summary for every $x\in G \backslash S$, we have $\langle S \cup \{x\} \rangle = G$, by Lemma 1 this means $\langle S\rangle $ is maximal subgroup, and since $M$ is the only maximal subgroup we have $\langle S\rangle=M$, but then $S \subset M $ also we have $S\subset G \backslash M$, thus $S=\emptyset$, contradiction,
, hence $l \neq1$.


If $l>1$, then $l-1$ is the largest positive integers which fails to be included on $\mathfrak{P}$, equivalently there exists $V \in \mathcal{U}_{l-1}$ with $\langle S \cup V \rangle \neq G$. We will prove that $\langle S \cup V \rangle$ is maximal subgroup. Indeed, take any $x \in G \backslash \left(S \cup V\right) = G\backslash S \cap G \backslash V$, which implies $x\not \in S$ and $s \not \in V$
we divide into two cases:

i)  If $x\in M$, note that $V \in \mathcal{U}_{l-1}$ means that $V \subset M$ and $\lvert V \rvert = l-1$,  therefore $V \cup \{x\} \subset M$. And since $x \not \in V$ we have $V \cap \{x\}=\emptyset$, thus $\lvert V \cup \{x\}\rvert = \lvert V \rvert + 1 = l-1+1=l$, therefore $V \cup \{x\} \in \mathcal{U}_{l}$, since $l \in \mathfrak{P}$ we have $\langle S \cup V \cup \{x\}\rangle= G$.

ii)  If $x\not \in M$ then $x \in G \backslash M$, note that $S \in \mathcal{T}_{t-1}$ means that $S \subset G\backslash M$ and $\lvert S \rvert = t-1$, therefore $S \cup \{x\} \subset G\backslash M$. And since $x \not \in S$ we have $S \cap \{x\}=\emptyset$, thus $\lvert S\cup \{x\} \rvert=\lvert S \rvert + 1=t-1+1=t$, therefore $S \cup \{x\} \in \mathcal{T}_t$, since $t\in \mathfrak{P}$ we have $\langle S \cup \{x\} \rangle =G$. Furthermore we have $G=\langle S \cup \{x\} \rangle \subset \langle S \cup V \cup \{x\} \rangle$, which implies $\langle S \cup V \cup \{x\}\rangle= G$.


In summary, for every $x \in G \backslash \left(S \cup V\right)$, we have $\langle S \cup V \cup \{x\}\rangle= G$, by Lemma 1 this means $\langle S \cup V \rangle $ is maximal subgroup, and since $M$ is the only maximal subgroup we have $\langle S \cup V \rangle=M$, but then $S \subset \langle S \cup V \rangle  =  M$, by the fact that $S\subset G \backslash M$, we would have $S=\emptyset$, contradiction. And the proof is completed.

Now we have $G=\langle g \rangle$  by Lemma 3, let $|G|=n=p_1^{\alpha_1} \cdots p_j^{\alpha_j}$, where $p_1,\cdots,p_j$ are all prime numbers. Consider
\[H_{p_k} = \langle g^{p_k} \rangle\]
We will prove that $H_{p_k}$ is maximal subgroup for every $k$. Indeed, if S is a subgroup with $S \neq G$ and $S \neq H_{p_k}$ satisfies $H_{p_k} \subseteq S \subseteq G$, then $d_k=|H_{p_k}|$ divides $|S| \leq  |G|$, but $|H_{p_k}|=\frac{n}{p_k}$, therefore
\[\frac{n}{p_k} \leq  |S| \leq  n \qquad \text{and} \qquad \text{$\frac{n}{p_k}$ divides $\lvert S\rvert$ divides $n$}\]

So that there exist $u, v\in \mathbb{N}$ such that $n= v  |S|$ and  $|S|=u \left( \frac{n}{p_k}\right)$, thus $n= (u)\, (v) \left(\frac{n}{p_k}\right)$, which implies $p_k = u  v$, since $p_k$ is prime we should have $u=1$ or $v=1$, but then $|H_{p_k}|=|S|$ or $|S|=|G|$ which together with $H_{p_k} \subseteq S \subseteq G$ would result to $H_{p_k}=S$ or $S=G$, thus $H_{p_k}$ is a maximal subgroup for every $k$.

Since $G$ has only one maximal subgroup that is $M$, we should have $H_{p_k} =M= H_{p_l}$ for all $k$ and $l$, therefore $\frac{n}{p_k}=|H_{p_k}|=|H_{p_l}|=\frac{n}{p_l}$ so that $p_k=p_l$ for all $k$ and $l$, thus $|G|$ actually has only one prime factor and we conclude that $|G|=p^{\alpha}$.

Continue Reading

23:02:00   Olimpiade Matematika,

I solved IMO problem 5 with the "density" style,  this is not that precise actual density from the topology course. High School students usually view 'dense' as "always getting somewhere in between". Note that (until this post got published) this proof is quite different from the proofs given in Mathlinks.

IMO 2013 Problem 5
Find all function $f: \mathbb{Q}_+\rightarrow \mathbb{R}$ which satisfies:
a) $f(x+y) \geq f(x)+f(y)$ for all $x, y \in \mathbb{Q}_+$.
b) $f(x)f(y) \geq f(xy)$ for all $x, y \in \mathbb{Q}_+$.
c) There exists $a\in \mathbb{Q}_+$ and $a> 1$ such that $f(a)=a$.

Solution: 

We first prove the following lemma:

Lemma: The set $A:=\left\{\frac{a^k}{n} \lvert k, n \in \mathbb{N}\right\}$ is "dense" in $\mathbb{Q}_+$. That is for any $x, y \in \mathbb{Q}_+$ there exists $\theta \in A$ such that $x < \theta < y$.

Proof: 
Given $x, y \in \mathbb{Q}_+$ with $y> x$, since $a> 1$ we can choose $k$ large enough so that $\frac{a^k}{x}-\frac{a^k}{y}=a^k \left(\frac{y-x}{xy}\right)> 1$. Therefore there exists an integer $N$ in the interval $\left(\frac{a^k}{y},\frac{a^k}{x}\right)$. Thus

\[\frac{a^k}{y} < N < \frac{a^k}{x}\]

This means $x < \frac{a^k}{N} < y$. $\blacksquare$.

From condition 3, we have $f(a)=a >  0$, thus $f(1)a=f(1)f\left(a\right) \geq f\left(a\right) = a$. Therefore $f(1) \geq 1$.

Next we will prove that $f(n)\geq n$ for all $n \in \mathbb{N}$.
Obviously, we have $f(x_1+x_2+\cdots+x_n)\geq f(x_1)+f(x_2)+\cdots+f(x_n)$. 
Thus $f(n)\geq f(1)n \geq n$.

Next we will prove that $f(x) > 0$ for all $x \in \mathbb{Q}_+$. Suppose that there exists a positive rational number $t$ such that $f(t) \leq 0 $ choose a positive integer $s$ such that $st$ is an integer. Hence since $f(s)\geq s > 0$ we have $st\leq f(st) \leq f(s) f(t) \leq 0$, a contradiction.

Then we prove that $f$ is monotonely increasing, for any positive rational numbers $y > x$, then $y=x+ t$ for some positive rational number $t$. Thus $f(y)= f(x+t)\geq f(x)+f(t) > f(x)$.

We have $f(a^k)\leq f(a)^k = a^k$ thus for any integers $m$ and $k$ we have $m f\left(\frac{a^k}{m}\right) \leq f(a^k) \leq a^k$ which implies
\[f\left(\frac{a^k}{m}\right)\leq \frac{a^k}{m} \qquad \text{for any integers $k,  m$}\]

We will prove that $f(r)\leq r$ for all $r \in \mathbb{Q}_+$. Suppose that there exists a  positive rational number $r$ such that $f(r) > r$, fix a natural number $k$ , then $v:=\frac{a^{k+1}}{f(r)-r}$ is a defined positive number. Thus we can take an integer $m$ greater than $v$.

But, by our lemma, between $r+\frac{a^k}{m}$ and $r+\frac{a^{k+1}}{m}$ there exists a rational number of the form $\frac{a^l}{u}$, hence by the monotonity we have

\[f(r) < f\left(r+\frac{a^k}{m}\right) < f\left(\frac{a^l}{u}\right) \leq \frac{a^l}{u} < r+\frac{a^{k+1}}{m} \]

But then $m < \frac{a^{k+1}}{f(r)-r} =v$ a contradiction. Thus for all positive rational numbers $r$ we have $f(r)\leq  r$ , in particular $f(n)\leq n$ for all natural numbers, since we also have $f(n)\geq n$ we conclude that $f(n)=n$ for all natural numbers $n$.

For any rational numbers $\frac{b}{c}$ where $b$ and $c$ are positive integers we have $f\left(\frac{b}{c}\right) \geq \frac{f(b)}{f(c)}=\frac{b}{c}$, therefore $f(r)\geq r$ for all $r\in \mathbb{Q}_+$, since $f(r)\leq r$ as well, we conclude that $f(r)=r$. It is easy to check that this function satisfies the given conditions. 

Continue Reading