Riemann Hypothesis for Dummies?

Riemann Hypothesis for Dummies?

05:23:00   Analytic Number Theory,

First, i'm sorry if the title is a little bit offensive. I just wonder if there's such a thing as "Riemann Hypothesis For Dummies", while the original statement of the conjecture itself would require at least advance undergraduate complex analysis, and (no math undergraduate is dummy right?).  I'm going to write down some analysis preliminary that will lead us to understand the statement of Riemann Hypothesis.

Recall that the Initial Riemann zeta function is defined via the Dirichlet series by

\[\zeta(s)=\sum_{n=1}^{\infty} \frac{1}{n^s}\qquad\Re(s)>1\]

Note that the function is clearly analytic on $\Re(s)>1$.

The statement of Riemann Hypothesis is (it is not the most simple form, perhaps the most simple form i know is the thing related to Liouville's Lambda Function )

[Riemann Hypothesis] All nontrivial zeros of the Riemann Zeta Function  lie on the critical line $\Re(s)=\frac{1}{2}$.


The question immediately arises here, isn't the series diverges for $\Re(s) \leq 1$? Then why does it
mention $\Re(s)=\frac{1}{2}$? Also what is the nontrivial zero?

First we resolve the problem on defining the Riemann Zeta Function (without initial), we will use Riemann's Argument, since so far this function only defined for $\Re(s)>1$.  How could we reach (read:define) it on $\Re(s)\leq 1$, that is to define it for all complex plane? Moreover, since the function is already analytic on $\Re(s) >1$, we want the function to be also analytic on the other region $\Re(s) \leq 1$.
One tool we can use here is the analytic continuation, for which we can fill the the value of the function outside its analytic domain resulting the other analytic function with a larger domain,  this can be done if  we can find another analytic function $F(s)$ such that the restriction of $F$ on $Re(s)>1$ is $\zeta(s)$ itself.  Unfortunately, there is no hope for  $s=1$, we will see this later, now we focus on finding an analytic function $F$ such that $F(s)=\zeta(s)$, for $\Re(s)>1$, this function must be analytic on the domain larger than just $\Re(s)>1$.

To find the extended function, we start with what we only have, for $\Re(s)>1$ we have

\[\begin{align*}\zeta(s)=\sum_{n=1}^{\infty} \frac{1}{n^s}&=\sum_{n=0}^{\infty}\frac{1}{(n+1)^s} \\ &=\sum_{n=1}^{\infty} \frac{1}{(n+1)^s}+1\\ &=\sum_{n=1}^{\infty}\frac{1}{(n+1)^s} + \sum_{n=1}^{\infty} \left(\frac{1}{n^{s-1}} - \frac{1}{(n+1)^{s-1}}\right)\\ &=\sum_{n=1}^{\infty}\left(\frac{1}{(n+1)^s}-\frac{n+1}{(n+1)^s}+\frac{n}{n^{s}}\right)\\ &=\sum_{n=1}^{\infty}n\left(\frac{1}{n^s}-\frac{1}{(n+1)^s}\right)\\ &=\sum_{n=1}^{\infty} n s\int_{n}^{n+1} x^{-s-1}\,dx\end{align*}\]

Since $\lfloor x \rfloor = n$ when $x \in [n,n+1)$, we have $\int_{n}^{n+1}\lfloor x \rfloor x^{-s-1}\,dx=n\int_{n}^{n+1} x^{-s-1}\,dx$. We have

\[\begin{align*}\zeta(s)&=s\sum_{n=1}^{\infty} n \int_{n}^{n+1} x^{-s-1}\,dx\\ &=s\sum_{n=1}^{\infty}\int_{n}^{n+1}\lfloor x \rfloor x^{-s-1}\,dx\\ &=s\int_1^{\infty}\lfloor x \rfloor x^{-s-1}\,dx\end{align*}\]

Write $\lfloor x \rfloor = x - \{x\}$ where $\{x\}$ is fractional part of $x$. We have

\[\begin{align*}\zeta(s)&=s \int_1^{\infty} x^{-s-1}\lfloor x \rfloor \,dx\\ &=s \int_1^{\infty}(x-\{x\})x^{-s-1}\,dx\\ &=s \int_1^{\infty} x^{-s}\, dx - s\int_1^{\infty} x^{-s-1}\{x\}\, dx\end{align*}\]

Since $s \int_1^{\infty} x^{-s} \,dx = s \frac{-x^{-s+1}}{-s+1}\mid_1^{\infty}=\frac{s}{s-1}$, we have

\[\zeta(s)=\frac{s}{s-1} - \int_1^{\infty}\{x\}x^{-s-1}\,dx\]

Via this representation of $\zeta(s)$,  we see that $\zeta(s)$ has simple pole for $s=1$, and also since $\{x\} \in [0,1)$ the integral $\int_1^{\infty}\{x\}x^{-s-1}\,dx$ converges for $\Re(s)>0$, by comparison test with $\int_1^{\infty} x^{-\Re(s)-1} \, dx$. Thus, on this representation, $\zeta(s)$ is defined for $\Re(s)>0$. We actually have extend the domain of $\zeta(s)$ (applying analytic continuation) from $\Re(s)>1$ to $\Re(s)>0$, and resulting the simple pole in $s=1$ with residue 1. Still, our works to define $\zeta(s)$ for the whole complex plane, not finish yet.

To continue, we borrow a function from Advanced Calculus Course (in Universitas Indonesia we call it Calculus IV), Gamma Function.

Gamma function, initially defined by $\Gamma(s)=\int_0^{\infty}t^{s-1}e^{-t}\,dt$ for $s$ is real positive, since the integral also converges whenever $s$ is a complex number with $\Re(s)>0$, therefore the Gamma function is defined as a complex function, this function is analytic on where it is defined that is $\Re(s)>0$. However using this definition, we can't go anywhere other than $\Re(s)>0$, but luckily, using also analytic continuation, the Gamma Function can also extendable to an analytic function in the whole complex plane except for $s=0, -1,-2, \cdots, -n, \cdots$ (see the link above)

Using it then, Gamma Function is extendable to $\mathbb{C}/\{0,-1,-2,\cdots\}$.  In the relation between $\zeta$ and $\Gamma$, consider

\[\Gamma\left(\frac{s}{2}\right)=\int_0^{\infty}t^{s/2-1}e^{-t}\, dt\]

Substitue $t=n^2\pi u$ we have

\[\Gamma\left(\frac{s}{2}\right)=\int_0^{\infty}\pi^{\frac{s-2}{2}} n^{s-2} u^{\frac{s-2}{2}} e^{-n^2 \pi u} (n^2 \pi)\,du=n^s \pi^{\frac{s}{/2}}\int_0^{\infty} u^{\frac{s}{2}-1} e^{-n^2 \pi u} \, du\]

Equivalent to

\[\pi^{-\frac{s}{2}}\Gamma\left(\frac{s}{2}\right)\left(\frac{1}{n^s}\right)=\int_0^{\infty} u^{\frac{s}{2}-1} e^{-n^2 \pi u} \, du\]



Taking the summation from $n=1$ to $\infty$ and since the integral on the left converges uniformly, we can exchange the integral and summation thus resulting

\[\pi^{-\frac{s}{2}}\Gamma\left(\frac{s}{2}\right) \zeta(s) = \int_0^{\infty} u^{\frac{s}{2}-1} \left(\sum_{n=1}^{\infty}e^{-n^2 \pi u}\right) \, du\]

We borrow again a function from advanced calculus,  Jacobi-Theta Function, defined by $\theta(t)=\sum_{n=-\infty}^{\infty} e^{n^2 i\pi t}$. Therefore $\theta(it)=\sum_{n=-\infty}^{\infty} e^{-n^2 \pi t}$. Since "$\sum_{n=-\infty}^{0} e^{-n^2 \pi t} = \sum_{n=0}^{\infty} e^{-n^2\pi t}$", using this we have

\[\theta(it)=\sum_{n=0}^{\infty} e^{-n^2 \pi t}+ \sum_{n=1}^{\infty}e^{-n^2 \pi t}=2 \sum_{n=1}^{\infty} e^{-n^2 \pi t}+1.\]

Thus $\sum_{n=1}^{\infty}e^{-n^2 \pi t} = \frac{\theta(it)-1}{2}$. Therefore the zeta function is represented as

\[\zeta(s)=\frac{\pi^{\frac{s}{2}}}{\Gamma\left(\frac{s}{2}\right)}\int_0^{\infty} u^{\frac{s}{2}-1} \left(\frac{\theta(ui)-1}{2}\right)\, du\]

From this point we shall use the functional equation for $\theta$, that is $(-ix)^{\frac{1}{2}}\theta(x)=\theta\left(-\frac{1}{x}\right)$,  which is quite hard to prove, this functional equation can be obtained from modular transform of theta function. Usually given as Jacobi Identities for theta function (See the Link above, but no proof there).  Substituing $x \mapsto ix$ to the functional equation we have $x^{\frac{1}{2}} \theta(ix)=\theta\left(\frac{-1}{ix}\right)=\theta\left(\frac{i}{x}\right)$.

\[\begin{align*}&\int_0^{\infty}x^{s/2-1}\left(\frac{\theta(xi)-1}{2}\right)\,dx=\\ &\int_0^{1}x^{s/2-1}\left(\frac{\theta(xi)-1}{2}\right)\,dx+\int_1^{\infty}x^{s/2-1}\left(\frac{\theta(xi)-1}{2}\right)\,dx\end{align*}\]

Using substitution $x \mapsto \frac{1}{x}$ on the first integral, we have

\[\begin{align*}\int_0^1x^{s/2-1}\left(\frac{\theta(xi)-1}{2}\right)\, dx&= \int_{\infty}^{1}x^{-s/2+1}\left(\frac{\theta\left(\frac{i}{x}\right)-1}{2}\right)\left(\frac{-1}{x^2}\right)\, dx \\ &= \int_1^{\infty} x^{-s/2-1}\left(\frac{x^{1/2}\theta(ix)-1}{2}\right)\\ &= \int_1^{\infty} \frac{x^{-s/2-1/2}\theta(ix)-x^{-s/2-1/2}}{2}\\ &+ \int_1^{\infty} \frac{x^{-s/2-1/2}-x^{-s/2-1}}{2} \, dx\\ &=\int_1^{\infty} \frac{x^{-s/2-1/2}\theta(ix)-x^{-s/2-1/2}}{2}+\frac{1}{s(s-1)}\end{align*}\]

Thus we have

\[\int_0^{\infty}x^{s/2-1}\left(\frac{\theta(xi)-1}{2}\right)\,dx\]
\[=\frac{1}{s(s-1)}+\int_1^{\infty}(x^{-s/2-1/2}+x^{s/2-1})\left(\frac{\theta(xi)-1}{2}\right)\,dx\]

Hence the Riemann Zeta Function would takes form

\[\zeta(s)=\frac{\pi^{\frac{s}{2}}}{\Gamma\left(\frac{s}{2}\right)}\left(\frac{1}{s(s-1)}+\int_1^{\infty}(x^{-s/2-1/2}+x^{s/2-1})\left(\frac{\theta(xi)-1}{2}\right)\,dx\right)\]

Note that Gamma function has simple pole on $s=0$, thus $\frac{1}{\Gamma\left(\frac{s}{2}\right)}$ cancel the simple pole also at $s=0$ obtained from $\frac{1}{s(s-1)}$.
Since $\theta(xi)$ has exponential order, the above integral converges for every $s\in \mathbb{C}$, therefore the expression on the right performs an analytic function for all $s \in \mathbb{C}$ except for $s=1$ (in which the denominator is zero) and $s=-2,-4,-6, \cdots$ (in which $\Gamma\left(\frac{s}{2}\right)$ is not analytic) thus we have extend the zeta function to an analytic function defined on $\mathbb{C}/\{1,-2,-4,\cdots,-2k,\cdots\}$.

We actually have any other question to resolve, that is a nontrivial zeros of $\zeta(s)$, to make it short, we call $s$ the zero is trivial zero iff $s$ is a pole from the $\Gamma\left(\frac{s}{2}\right)$, that is $s=0,-2,-4,\cdots$. The other zeros is known to be located on $0\leq \Re(z) \leq 1$, are called nontrivial zeros.  Therefore we have got the idea now, that the Riemann Hypothesis asks wether these nontrivial zeros always located on the $\Re(s)=\frac{1}{2}$.

It is known that more than billion of the first nontrivial zeros are all agree with the hypothesis, which seems likely the hypothesis to be true. But, as the problem is complicated enough to describe, the proof challenges many greatest minds in the world(s), as the most difficult problem in Number Theory.

Writing this post remind me with the quote from Albert Einstein, which is put on the wall of the seminar room in our university :D  , "If you can't explain it simply, you don't understand it well enough" ,  well maybe I don't really understand this very well,  because even to describe it, the miscellaneous properties of the other special functions are being used.

Continue Reading

[ALGAE IV] Rational Curve and Rational Function.

[ALGAE IV] Rational Curve and Rational Function.

22:41:00   Algebraic Geometry,

It has been months, and i actually has got quite far reading algebraic geometry, but i don't spare a time to share it here. Let's continue the previous posts (and to remind me more about what i have learned).

As we already learn that any irreducible rational curve $f(x,y)=0$ can be parameterized by $x=\varphi(t)$ and $y=\psi(t)$. Lets take a look this parameterization deeper,  Example in the [AlGAE II] is the place to look, the parameter $t$ help us to correspond a point in the curve to the point in the line $x=-1$, by a mapping (recall that $y=tx$)

\[(x,y) \mapsto (-1,-t) = \left(-1, -\frac{y}{x}\right)\]

For $x=0$ which also implies $y=0$, this map is undefined, and this is where the denominator of $\varphi(t)$ and $\psi(t)$ vanish. Ignoring these points, the map seems fine, and defines a bijection from the point in the curve to the line. In fact, there can be only finitely many points in the curve such that the parameter fails to represent (like our $(0,0)$ just know), those are actually the common roots of the denominator of $\varphi(t)$ and $\psi(t)$.

Let include the result obtained on [ALGAE III], where we can find the isomorphic map from $\mathbb{F}(X)$ to $\mathbb{F}(t)$, given that $X$ is a rational curve.
Let's see wether this result is vice versa, that is whenever $\mathbb{F}(X)\cong \mathbb{F}(t)$ then $X$ is rational.
Since $x, y \in \mathbb{F}(X)$,  they have a correspondence image in $\mathbb{F}(t)$, let say $x$ to $\varphi(t)$ and $y$ to $\psi(t)$. By isomorphism, the element $f(x,y)=0 \in \mathbb{F}(X)$ goes to the element $f(\varphi(t),\psi(t))=0$ (since $x$ and $y$ is related by an algebraic relation, note that this is not a mere substitution $x =\varphi(t)$ and $y =\psi(t)$). Therefore, such parametrization so that $f(\varphi(t),\psi(t))=0$ exists, and $X$ is rational.

Moreover, as for any $t_0 \in \mathbb{F}$ we should have $f(\varphi(t_0),\psi(t_0))=0$, but this can be failed for which $t_0$ is a common root of the denominator of $\varphi(t)$ and $\psi(t)$. Excluding these points  we can easily see that $x=\varphi(t)$ and $y=\psi(t)$ define a parameterization the point on a curve $X$.

Our goal is to represent any point $(x,y) \in X$ as $(x,y)=(\varphi(t),\psi(t))$ for some $t$, and conversely producing $(x,y) \in X$, for any given $t$ by using parametrization $x=\varphi(t)$ and $\psi(t)$. Unfortunately, this is so much a dream, as we can see our parametrization in [ALGAE II] failed to include/produce some points in $X$. We will resolve this as close as possible to our goal.

Let $\tau(x,y)$ is a function in $\mathbb{F}(x)$ which is mapped to the function $t \in \mathbb{F}(t)$ via the isomorphism $\mathbb{F}(X) \rightarrow \mathbb{F}(t)$.  Consider the map $s(t) \mapsto s(\tau(x,y))$, this map takes $t$ to $\tau(x,y)$,  also it is a isomorphism, thus the map defines an isomorphism $\mathbb{F}(t) \rightarrow \mathbb{F}(X)$.
Recall that $x\mapsto\varphi(t)$ and $y\mapsto\psi(t)$,  by using the field isomorphism properties we have $\tau(x,y) \mapsto \tau(\varphi(t),\psi(t))$, also by the same map $\tau(x,y) \mapsto t$, and we conclude that

\[t=\tau(\varphi(t),\psi(t))\]

Similarly, $t \mapsto \tau(x,y)$ implies $\varphi(t) \mapsto \varphi(\tau(x,y))$, and also by the same map $\varphi(t) \mapsto x$, thus we conclude that (with similar argument for $y \mapsto \psi(t)$ )

\[\varphi(\tau(x,y))=x \qquad \text{and} \qquad \psi(\tau(x,y))=y\]

for any points in the curve. But the thing is not so smooth here, suppose that $\tau(x,y)=\frac{p(x,y)}{q(x,y)}$, then for in any points $(x_0,y_0)$ such that $q(x_0,x_0)=0$, we can't find such $t_0$ we want.  Luckily, there is only finitely many points  $(x_0,y_0) \in X$, such that $q(x_0,y_0)=0$, since $q(x,y)$ is not divisible by $f(x,y)$. The value of $t$ for which the parametrization fails are all $t_0$ that is the common root of the denominator $\varphi(t)$ and $\psi(t)$ , thus when $t_0=\tau(x_0,y_0)$ is the common root  of the denominator of  $\varphi(t)$ and $\psi(t)$, we have $\frac{p(x_0,y_0)}{q(x_0,y_0)}=t_0$, we assert that there can be only finite points $(x_0,y_0)\in X$ such that this can happen. Suppose that $p(x,y)-t_0 q(x_y)=0$ for infinitely many points on $X$, thus $f(x,y) | p(x,y)-t_0 q(x,y)$, which implies $\tau(x,y)=t_0$ up to the equality on $\mathbb{F}(X)$, which is absurd.

Therefore we conclude that

Except for some finite points in $X$, any point $(x_0,y_0) \in X$ can be represented as parameterization $x_0 = \varphi(t_0)$ and $y_0=\psi(t_0)$ and also for any $t_0 \in\mathbb{F}$, but some finitely many points, we can produce the point  $(\varphi(t_0),\psi(t_0)) \in X$.


Actually we've got something more, from $t=\tau(\varphi(t),\psi(t))$ , we see that the point $t_0$ is uniquely determined by the point $(x_0,y_0) \in X$, therefore our representation is unique. Continue Reading

OSN 2010 hari kedua

OSN 2010 hari kedua

03:41:00   Olimpiade Matematika,

Soal hari kedua sedikit lebih susah dari hari pertama, ini adalah solusi untuk soal-soal hari kedua (keuali soal no 8, dengan alasan yang sama). Untuk solusi untuk soal no 5,  ide awal nya (invariant principle) bukan ide saya sepenuh nya (at the beginning I even didn't understand the problem ^^)


Soal 5. (Hendrata Darmawan) 
Sebanyak $m$ orang anak laki-laki dan $n$ orang anak perempuan $(m> n)$ duduk mengelilingi meja bundar diawasi oleh seorang guru, dan mereka melakukan sebuah permainan sebagai berikut. Mula-mula sang guru menunjuk seorang anak laki-laki untuk memulai permainan. Anak laki-laki tersebut meletakkan sekeping uang logam di atas meja. Kemudian bergiliran searah jarum jam, setiap anak melakukan gilirannya masing-masing. Jika anak tersebut laki-laki, ia menambahkan sekeping uang logam ke tumpukan di atas meja, dan jika anak tersebut perempuan, ia mengambil sekeping uang logam dari tumpukan tersebut. Jika tumpukan di atas meja habis, maka permainan berakhir saat itu juga. Perhatikan bahwa tergantung siapa yang ditunjuk oleh sang guru untuk memulai langkah pertama, maka permainan tersebut bisa  cepat berakhir, atau bisa saja berlangsung paling sedikit $1$ putaran penuh. Jika sang guru menginginkan agar permainan tersebut berlangsung paling sedikit $1$ putaran penuh, ada berapa pilihan anak laki-laki yang dapat beliau tunjuk untuk memulai?

Solusi:

Sebut anak laki-laki pada permainan tersebut jack jika dan hanya jika apabila permainan dimulai dari anak tersebut, maka permainan akan berlangsung setidaknya satu putaran. Anak laki-laki yang tidak demikian disebut non-jack.

Pertama-tama kita pahami maksud soal ini lebih baik, sebanyak $m+n$ orang anak sudah duduk di meja bundar, dan sang guru harus memilih satu orang jack, diantara $m$ orang anak laki-laki tersebut,  yang akan dicari adalah ada beberapa banyak pilihan jack dari $m$ orang anak laki-laki yang ada.

Ambil sebarang jack, kita tinjau apa yang terjadi apabila permainan sudah berlangsung satu putaran, misalkan pada saat putaran terjadi, terdapat $x$ koin di meja. Pada saat itu, $n$ orang anak perempuan telah ikut bermain. Untuk mencari berapa kemungkinan jack yang mungkin, kita lakukan langkah berikut:
Untuk tiap-tiap satu anak perempuan pada permainan, kita keluarkan dari permainan, diikuti dengan tepat satu pemain laki-laki, yang bukan jack  yang memulai permainan.
Hal ini tidak mengubah banyak koin yang ada di meja, dan karena ada $n$ anak perempuan dan $m>n$, maka prosedur ini dapat terus dilakukan hingga tersisa $m-n$ orang anak laki-laki.

Apabila permainan dimulai dari salah satu dari $m-n$ orang anak laki-laki ini, dengan memasukan kembali semua anak perempuan dan anak laki-laki yang telah di keluarkan pada prosedur sebelumnya ke tempatnya semula, kita peroleh bahwa $m-n$ orang anak laki-laki tersebut adalah jack.


Jadi jawaban nya adalah $m-n$.


Soal 6. (Raja Oktovin)
Cari semua bilangan asli $n>1$ demikian sehingga

\[\tau(n)+\varphi(n)=n+1.\]

Dalam hal ini, $\tau(n)$ menyatakan banyaknya bilangan asli yang habis membagi $n$ dan $\varphi(n)$ menyatakan banyaknya bilangan asli yang kurang dari $n$ dan relatif prima terhadap $n$.

Solusi:

Misalkan \[X_n:=\{d \in \mathbb{N} : d | n\}\qquad Y_n:=\{m \in \mathbb{N} : \text{FPB}(m,n)=1\}.\]
Maka $\tau(n)=|X_n|$ dan $\varphi(n)=|Y_n|$, dan kita harus mencari $n$ sehingga $|X_n|+|Y_n|=n+1$. Perhatikan juga bahwa $X_n \cap Y_n = \{1\}$, sehingga $|X_n \cup Y_n|=|X_n|+|Y_n|-1$, dan Jika $n$ adalah bilangan yang memenuhi syarat pada soal maka haruslah \[|X_n \cup Y_n| = n\]

Karena untuk setiap $x\in X_n$ berlaku $1\leq x \leq n$ dan $X_n \subset N_n$ dan $Y_n \subset N_n$ dimana $N_n=\{1,2,\cdots,n\}$. Jadi $X_n \cup Y_n \subset N_n$ dan karena $|X_n \cup Y_n|=n= |N_n|$ maka $X_n \cup Y_n = N_n$.

Misalkan $p$ adalah faktor prima terkecil dari $n$, dan $\alpha$ adalah bilangan asli sehingga $p^{\alpha} | n$ dan $p^{\alpha+1} \not | n$. Jika $p^{\alpha+1}\leq n$ maka $p^{\alpha+1} \in N_n$ sehingga $p^{\alpha+1} \in X_n \cup Y_n$, namun $\text{FPB}(p^{\alpha+1},n) \neq 1$ dan $p^{\alpha+1} \not | n$, jadi tidak mungkin $p^{\alpha+1} \leq n$. Kita peroleh $p^{\alpha+1}>n$, dan karena $p$ adalah bilangan prima terkecil yang membagi $n$, maka haruslah $n=p^{\alpha}$, karena jika ada bilangan prima lain katakanlah $q\neq p$ sedemikian sehingga $q | n$, maka $p^{\alpha}q | n$ mengakibatkan $p^{\alpha}{q}<n<p^{\alpha+1}$, kontradiksi dengan $p$ adalah faktor prima terkecil. Dari $n=p^{\alpha}$ kita peroleh $\tau(n)=\alpha+1$, semua bilangan yang tidak relatif prima dengan $p^{\alpha}$ pasti berbentuk $kp$ dimana $k=1,2,\cdots,p^{\alpha-1}$, jadi ada $p^{\alpha}-p^{\alpha-1}$ bilangan diantara $1$ sampai $p^{\alpha}$ yang relatif prima dengan $p^{\alpha}$, diperoleh $\varphi(n)=p^{\alpha}-p^{\alpha-1}$, dan syarat pada soal menjadi
\[(\alpha+1)+p^{\alpha}-p^{\alpha-1}=p^{\alpha}+1 \Longleftrightarrow \alpha=p^{\alpha-1}\]  
Jadi sekarang akan dicari semua pasangan bilangan $(\alpha,p)$ yang memenuhi $\alpha=p^{\alpha-1}$ dimana $p$ bilangan prima.

Perhatikan bahwa untuk sebarang prima $p$ dan $\alpha=1$, maka persamaan diatas selalu benar, jadi jika $n$ bilangan prima maka persamaan $\tau(n)+\varphi(n)=n+1$ terpenuhi.  Sekarang akan dicari solusi yang bukan bilangan prima.

Jika $\alpha=2$ maka diperoleh $2=p$ sehingga $n=4$, dapat dicek bahwa $\tau(4)+\varphi(4)=5=4+1$. Sekarang misalkan $\alpha \geq 3$, berdasarkan ketaksamaan bernoulli (atau dengan teorema binomial) diperoleh
\[\begin{align*}\alpha&=p^{\alpha-1}\\ &=(1+p-1)^{\alpha-1}\\ &\geq 1+(p-1)(\alpha-1)\\ &=1+(p-1)\alpha-(p-1)\\ &=2+(p-1)\alpha-p\end{align*}\]

dengan tanda samadengan terjadi jika dan hanya jika $\alpha-1=1$ atau $p-1=0$, dimana untuk kasus ini tidak mungkin terjadi. Jadi kita peroleh $\alpha=p^{\alpha-1}$ mengakibatkan $\alpha>2+(p-1)\alpha -p$ yang setara dengan $\alpha(p-2)>\alpha(p-2)$, kontradiksi. Jadi tidak ada solusi untuk $\alpha\geq 3$.

Sehingga bilangan asli $n>1$ yang memenuhi adalah $n=4$ dan $n$ bilangan prima.


Soal 7. (Raja Oktovin)
Misalkan $a$ dan $b$ bilangan real positif. Diberikan polinom $F(x)=x^{2}+ax+b$ dan $G(x)=x^{2}+bx+a$ sehingga semua akar dari polinom $F(G(x))$ dan $G(F(x))$ adalah bilangan real. Buktikan bahwa $a$ dan $b$ lebih dari $6$.

Solusi: 

Dengan memfaktorkan $F(x)$ kita peroleh

\[F(x)=\left[x-\left(\frac{-a+\sqrt{a^2-4b}}{2}\right)\right]\left[x-\left(\frac{-a-\sqrt{a^2+4b}}{2}\right)\right].\]

Jadi

\[F(G(x))=\left[G(x)+\left(\frac{a-\sqrt{a^2-4b}}{2}\right)\right]\left[G(x)+\left(\frac{a+\sqrt{a^2-4b}}{2}\right)\right].\]

Karena $F(G(x))$ harus mempunyai akar real maka $G(x)+\left(\frac{a-\sqrt{a^2-4b}}{2}\right)$ dan $G(x)+\left(\frac{a+\sqrt{a^2-4b}}{2}\right)$ juga harus punya akar real, jadi mempunyai kedua diskriminant persamaan kuadrat diatas harus tak-negatif. Sehingga diperoleh
\[b^2-4\left(\frac{3a}{2}-\frac{\sqrt{a^2-4b}}{2}\right)\geq 0\qquad b^2-4\left(\frac{3a}{2}+\frac{\sqrt{a^2-4b}}{2}\right)\geq 0\]
Tambahkan kedua ketaksamaan diatas kita peroleh
\[b^2\geq 6a\]
Secara similar, dengan menukar peran $a$ dan $b$, dan karena $G(F(x))$ mempunyai akar real diperoleh
\[a^2\geq 6b\]
Jadi $b^4\geq 36a^2 \geq 6b \Rightarrow b^3\geq b \Rightarrow b\geq 6$, secara similar $a^4\geq 36b^2 \Rightarrow a\geq 6.$

Jika $a=6$, karena $a^2 \geq 6b$ diperoleh $36\geq 6b$ jadi kita peroleh $b \leq 6$, sehingga $b=6$. Begitu juga jika $b=6$ maka $a=6$. Namun untuk $a=b=6$, maka $F(G(x))=G(F(x))$ pandang lagi ketaksamaan diskriminant
\[b^2-4\left(\frac{3a}{2}+\frac{\sqrt{a^2-4b}}{2}\right)\geq 0\]
Jika $a=b=6$ maka ketaksamaan diatas setara dengan $-\sqrt{12}\geq 0$ yang jelas salah, jadi diskriminant tidak positif, untuk $a=b=6$, dan disimpulkan $a>6$ dan $b>6$.


Soal 8. (Raja Oktovin)
Diberikan segitiga lancip $ABC$ dengan titik pusat lingkaran luar $O$ dan titik tinggi $H$. Misalkan $K$ sebarang titik di dalam segitiga $ABC$ yang tidak sama dengan $O$ maupun $H$. Titik $L$ dan $M$ terletak di luar segitiga $ABC$ sedemikian sehingga $AKCL$ dan $AKBM$ jajaran genjang. Terakhir, misalkan $BL$ dan $CM$ berpotongan di titik $N$ dan misalkan juga $J$ adalah titik tengah $HK$. Buktikan bahwa bahwa $KONJ$ jajaran genjang.

Solusi:

Continue Reading

OSN 2010 hari pertama

OSN 2010 hari pertama

21:19:00   Olimpiade Matematika, soal-soal,

Sedikit rileks, dengan soal-soal SMA, yang tidak mudah dan lumayan menarik. OSN tahun ini diadakan di Medan. Berikut adalah soal-soal beserta solusi nya (kecuali soal no 2, karena saya kurang begitu paham geometri). Solusi saya tulis sedetil mungkin, agar (menurut pendapat saya) mendapat nilai penuh di OSN untuk masing-masing soal.

Soal 1 (Fajar Yuliawan)
Misalkan $a,b,c$ adalah bilangan asli yang berbeda. Buktikan bahwa barisan \[a+b+c, ab+ac+bc, 3abc\]
tidak mungkin membentuk barisan geometri maupun aritmatika.

Solusi:
Misalkan barisan diatas membentuk barisan geometri, maka berlaku \[3abc(a+b+c)=(ab+ac+bc)^2\]
Misalkan $x=ab$, $y=bc$ dan $z=ac$ maka diperoleh

\[3(xy+yz+xz)=(x+y+z)^2 \Longleftrightarrow \frac{(x-y)^2+(y-z)^2+(x-z)^2}{2} =0.\]

Jadi diperoleh $x=y=z$, atau $ab=bc=ac$, dan karena $a,b,c \neq 0$, diperoleh $a=b=c$, kontradiksi.

Misalkan barisan tersebut membentuk barisan aritmatika, maka

\[a+b+c+3abc=2(ab+ac+bc)\]

persamaan diatas setara dengan

\[b(a-1)(1-c)+c(b-1)(1-a)+a(c-1)(1-b)=0.\]

Perhatikan bahwa karena $a,b,c$ bilangan asli maka

\[k=b(a-1)(1-c) \leq 0 \qquad l=c(b-1)(1-a) \leq 0\] \[m=a(c-1)(1-b) \leq 0.\]

Salah satu dari $k,l$ atau $m$ harus samadengan $0$, karena jika tidak demikian, $0=k+l+m<0+0+0=0$, kontradiksi.

Tanpa mengurangi keumuman, misalkan $k=0$, atau $b(a-1)(1-c)=0$, karena $b \neq 0$, maka $a=1$ atau $c=1$. Jika $a=1$ maka $l=0$ yaitu $k=l=0$, dan jika $c=1$ maka $m=0$ yaitu $k=m=0$ Jadi dapat kita simpulkan setidaknya dua buah  dari variabel $k,l$ atau $m$ samadengan $0$, dan karena $k+l+m=0$ maka $k=l=m=0$. Ini mengakibatkan

 \[b(a-1)(1-c)=0 \qquad a(c-1)(1-b)=0 \qquad c(b-1)(1-a)=0\]

Perhatikan $b(a-1)(1-c)=0$ dan $a(c-1)(1-b)=0$, jika $c\neq 1$ maka diperoleh $a=1$ dan $b=1$ kontradiksi karena $a$ dan $b$ berbeda,  jadi haruslah $c=1$, akan tetapi hal ini menyebabkan $0=c(b-1)(1-a)=(b-1)(1-a)$ yang setara dengan $a=1$ atau $b=1$, atau dengan kata lain salah satu dari $a$ atau $b$ samadengan $c$, kontradikisi karena $a,b$ dan $c$ semua berbeda.

Soal 2 (Fajar Yuliawan)
 Diberikan segitiga lancip $ABC$ dengan $AC>BC$ dan titik pusat lingkaran luar $O$ . Garis tinggi segitiga $ABC$ dari  $C$ memotong  $AB$ dan lingkaran luar segitiga  $ABC$ lagi berturut-turut di titik $D$ dan $E$. Garis melalui $O$ sejajar $AB$ memotong garis  $AC$ di titik $F$. Buktikan bahwa garis $CO$, garis melalui  $F$ tegak lurus $AC$, dan  garis melalui $E$  sejajar  $DO$ bertemu di satu titik.

Solusi:

Soal 3 (Raymond Christoper Sitorus)
Suatu kompetisi matematika diikuti oleh $120$ peserta dari beberapa kontingen. Pada acara penutupan, setiap peserta memberikan $1$ souvenir pada setiap peserta dari kontingen yang sama dan $1$ souvenir pada salah seorang peserta dari tiap kontingen lainnya. Di akhir acara, diketahui terdapat $3840$ souvenir yang dipertukarkan.
Berapa banyak kontingen maksimal sehingga kondisi di atas dapat terpenuhi?


Solusi:
Misalkan banyaknya kontingen adalah $n$, dimana kontingen ke-$i$ mempunyai $x_i$ orang peserta. Kita akan menghitung banyaknya souvenir yang dipertukarkan. Pertama-tama, setiap dua peserta pada satu kontingen pasti melakukan transaksi, dengan demikian pada tiap-tiap  kontingen ke-$i$ terjadi ${x_i\choose 2}$ transaksi.   Jika $a$ memberikan souvenir ke $b$ maka $b$ juga memberikan souvenir pada $a$, jadi setiap transaksi melibatkan dua buah souvenir. Jadi untuk masing-masing kontingen ke-$i$, banyaknya souvenir yang dipertukarkan di dalam satu kontingen adalah $2{x_i\choose 2}=x_i(x_i-1)$, untuk $i=1,2,\cdots,n$. Secara total banyaknya souvenir yang ditukarkan sesama peserta satu kontingen adalah

\[\sum_{i=1}^n x_i(x_i-1)\]

Selanjutnya akan dihitung jumlah souvenir yang ditukarkan antar kontingen. Setiap satu peserta pada kompetisi tersebut memberikan tepat satu souvenir pada tepat satu orang dari tiap kontingen yang lain, dan karena ada $n-1$ buah kontingen yang lain, maka tiap satu peserta memberikan $n-1$ buah souvenir. Karena ada $120$ peserta maka, total souvenir yang ditukarkan keluar kontingen adalah

\[120(n-1)\]

Jadi total souvenir yang dipertukarkan adalah

\[\sum_{i=1}^n x_i(x_i-1)+120(n-1)=3840.\]

Karena $\sum_{i=1}^n x_i =120$ maka

\[\sum_{i=1}^n x_i^2 +120(n-2)=3840 \Longleftrightarrow \sum_{i=1}^n x_i^2 +120n=4080\]

Perhatikan bahwa dengan RMS-AM diperoleh $\sqrt{\frac{\sum_{i=1}^nx_i^2}{n}}\geq \frac{\sum_{i=1}^n x_i}{n}=\frac{120}{n}$, jadi $\sum_{i=1}^n x_i^2 \geq \frac{120^2}{n}$. Diperoleh

\[4080\geq 120n +\frac{120^2}{n} \Longrightarrow 34 \geq n + \frac{120}{n} \Longrightarrow (n-30)(n-4)\leq 0 \] sehingga \[ 4\leq n \leq 30\]

Jadi $n$ maksimal adalah 30.

Sekarang akan ditunjukan bahwa , $n=30$, tercapai. Misalkan $a_{ij}$ menyatakan peserta ke-$i$ dari kontingen ke-$j$.  Jika kontingen dinyatakan sebagai $k_1, k_2, \cdots, k_{30}$, mak $k_i=\{a_{i1},a_{i2},a_{i3},a_{i4}\}$, sehingga $|k_i|=4$. Diperoleh banyak pertukaran souvenir adalah $30 \times 4(4-1)+120(29)=3840$.

Soal 4 (Nanang Susyanto)
Diketahui bahwa  $m $ dan $n$ adalah bilangan-bilangan asli dengan sifat

\[(mn)|(m^{2010}+n^{2010}+n)\]

Buktikan bahwa terdapat bilangan asli  $k$ sehingga $n=k^{2010}$.

Solusi:
Misalkan $d=\text{FPB}(m,n)$. Pertama-tama akan dibuktikan bahwa $d^{2010}|n$. Perhatikan bahwa $m=k d$ untuk suatu $k \in \mathbb{Z}$ dan $n=l d$ untuk suatu $l \in \mathbb{Z}$, jadi

\[d^{2010} k^{2010} + d^{2010} l^{2010} + n =x  kl d^2\]

atau setara dengan
\[\frac{n}{d^2}=x kl-d^{2008}k^{2010}-d^{2008}l^{2010} \in \mathbb{Z}\]

dengan kata lain $d^2 | n$. Apabila benar bahwa $d^i | n$, dimana $2\leq i\leq 2009$, diperoleh $n=l_id^i$ untuk suatu $l_i \in \mathbb{Z}$, sehingga

\[\begin{align*}d^{2010} k^{2010} + d^{2010} l^{2010} + n &= x kl_i d^{i+1} \Leftrightarrow \\ \frac{n}{d^{i+1}} &= x kl_i-d^{2009-i} k^{2010}-d^{2009-i}k^{2010} \in \mathbb{Z}.\end{align*}\]

Dengan demikian $d^i | n \Rightarrow d^{i+1} | n$ untuk $i=2,3,\cdots, 2009$, dan karena diketahui $d^2 | n$ maka $d^3 | n , d^4 | n, \cdots d^{2010} | n$, sehingga diperoleh $d^{2010} | n$.

Misalkan $n=s d^{2010}$, untuk suatu $s \in \mathbb{Z}$. Akan dibuktikan bahwa $s=1$. Kita peroleh

\[\begin{align*}d^{2010} k^{2010} + d^{2010^2} s^{2010} + s d^{2010} &= x m s d^{2010} \Longrightarrow \\ k^{2010}+d^{2009\cdot 2010}s^{2010}+s&=x ms\end{align*}\]

sehingga diperoleh $s | k^{2010}$. Jika $s \neq 1$, maka ada bilangan prima $p$ sehingga $p | s$, dan karena $s | k^{2010}$, maka $p|k^{2010}$, mengakibatkan $p | k$. Ini berarti $m=kd=(pu)d = (pd) u$, untuk suatu $u \in \mathbb{Z}$ dan $n=sd^{2010}=(pv)d^{2010}=(pd)vd^{2009}$ untuk suatu $v \in \mathbb{Z}$, mengakibatkan  $pd | m$ dan $pd | n$, kontradiksi karena $pd>d = \text{FPB}(m,n)$.

Jadi $n=d^{2010}$.

Continue Reading

17th IMC Day 1. [part 1] Problem 1, Problem 2, Problem 3.

17th IMC Day 1. [part 1] Problem 1, Problem 2, Problem 3.

04:21:00  

In this part 1, i'll give some solution of the previous IMC 2010 problems. The problems are relatively easy compared to the last year.

 Problem 1.  Let $a\leq b$ where $a$ is a positive real number
\[\int_a^b(x^2+1)e^{-x^2}dx\geq e^{-a^2}-e^{-b^2}.\]

Solution: Okay, this is too easy for IMC, first we prove that $(x^2+1)e^{-x^2}\geq 2xe^{-x^2}$ for all $x\in [a,b]$, this would mean $x^2+1 \geq x \Longleftrightarrow (x-1)^2\geq 0$ which is obvious. Since $\int_a^b 2xe^{-x^2} \, dx = \int_{a}^{b} e^{-x^2} \, d\left(x^2\right)=-e^{-b^2}+e^{-a^2}.$

comment: This can be one of the easiest problem along with problem 1 day 1 in IMC 2007. No trick, quickly recognized and less trouble.

Problem 2. Compute the sum of the series
\[\sum_{k=0}^{\infty} \frac1{(4k+1)(4k+2)(4k+3)(4k+4)}=\frac{1}{1\cdot 2 \cdot 3 \cdot 4} +\frac{1}{5\cdot 6 \cdot 7 \cdot 8} +\dots .\]

Solution: There you go, so many ideas for this one.. I you have enough mental to do some tedeous computation, you can start with
\[\int_0^1 \int_0^t \int_0^u \int_v \sum_{k=0}^{\infty} x^{4k} \, dx \, dv \, du \, dt=\int_0^1 \int_0^t \int_0^u \int_0^v \frac{1}{1-x^4} \, dx \, dv \, du \, dt\].

For $0\leq x \leq v \leq u \leq t <1 $, the power series converges uniformly (by abel's test).
Notice that

\[\begin{align*}\int_0^v \frac{1}{1-x^4} \, dx &= \int_0^v \frac{1}{2}\left( \frac{1}{1-x^2} + \frac{1}{1+x^2}\right)\\ &=\int_0^v \frac{1}{4}\left( \frac{1}{1+x} + \frac{1}{1-x}\right) +\frac{1}{2}\arctan v \\ &= \frac{1}{4}\ln \left|\frac{1+v}{1-v}\right|+\frac{1}{2}\arctan v \end{align*}\]

Now for the second integral, first by partial integration we have $\int_0^u \ln |1-v| \, dv = (u-1)\ln |1-u|-u$ and similarly $\int_0^u \ln |1+v| \, dv = (u+1) \ln |u+1|-u$. Also, by partial integration we have
$\int_0^u \arctan v \, dv = u \arctan u - \int_0^u \frac{u}{1+u^2}= u \arctan u - \frac{1}{2} \ln |1+u^2|$

Yes, that is just second..  Now we can add them altogether yields

\[\frac{u}{4} \ln \left|\frac{1+u}{1-u}\right| + \frac{1}{4} \ln \left|\frac{1-u^2}{1+u^2}\right|+\frac{u}{2}\arctan u\]

First we compute

\[\int_0^t \frac{u}{2} \arctan u=\frac{1}{4} t^2 \arctan t -\frac{1}{4}\int_0^t \left(\frac{u^2}{1+u^2}\right)=\frac{1}{4}\left( (t^2 +1) \arctan t -t \right)\]

just finish it $\int_0^1\frac{1}{4}\left( (t^2 +1) \arctan t -t \right) dt$

$=\frac{1}{4} \left.\left(\frac{t^3}{3}+t\right) \arctan t \right \lvert_0^1 - \left(\int_0^1 \frac{t^3+t}{12(t^2+1)}+ \frac{2t}{12(t^2+1)}dt\right) - \frac{1}{8}$

$=\frac{\pi}{12}-\frac{1}{24}+\frac{1}{12}\int_0^1 \frac{2t}{t^2+1}-\frac{1}{8} = \frac{\pi}{12}-\frac{1}{6}-\frac{1}{12} \ln 2.$

Then we compute
\[\int_0^t\frac{u}{4}\ln\left(\frac{1+u}{1-u}\right)\, dt=\frac{t^2}{8}\ln\left(\frac{1+t}{1-t}\right)-\left(\int_0^t\frac{u^2}{4}\left(\frac{1}{1-u^2}\right)\, dt\right)\]
\[=\frac{t^2}{8}\ln\left(\frac{1+t}{1-t}\right)+\frac{1}{4}\int_0^t 1-\frac{1}{1-u^2}\, dt\]
\[=\frac{t^2}{8}\ln\left(\frac{1+t}{1-t}\right)+\frac{t}{4}-\frac{1}{8}\ln\left(\frac{1+t}{1-t}\right)\]


and so $\int \left(\frac{t^2-1}{8}\right)\ln\left(\frac{1+t}{1-t}\right)+\frac{t}{4}\, dt=$
$\frac{1}{8}\left(\frac{t^3}{3}-t\right)\ln\left(\frac{1+t}{1-t}\right)- \frac{1}{4}\int\left(\frac{\left(t^3-t\right)}{3(1-t^2)}-\frac{2t}{3(1-t^2)}\right)\, dt+\frac{t^2}{8}$
$=\frac{1}{8}\left(\frac{t^3}{3}-t\right)\ln\left(\frac{1+t}{1-t}\right)+\frac{t^2}{24}+\frac{1}{12}\int \left(\frac{2t}{(1-t^2)}\right)\, dt +\frac{t^2}{8}$
$=\frac{1}{8}\left(\frac{t^3}{3}-t\right)\ln\left(\frac{1+t}{1-t}\right)+\frac{t^2}{24}-\frac{\ln(1-t^2)}{12} +\frac{t^2}{8}$
$\left(\frac{t^3}{24}-\frac{t}{8}-\frac{1}{12}\right)\ln(1+t)+\left(-\frac{t^3}{24}+\frac{t}{8}-\frac{1}{12}\right)\ln(1-t)+\frac{t^2}{6}.$
Therefore

\[\int_0^1 \left(\frac{t^2-1}{8}\right)\ln\left(\frac{1+t}{1-t}\right)+\frac{t}{4}\, dt=\frac{1-\ln 2}{6}\]

Lastly, we compute $\int_0^1\int_0^t \frac{1}{4} \ln \left(\frac{1-u^2}{1+u^2}\right)\,du\, dt$.

By partial integration
\[\frac{1}{4}\int_0^t \ln(1+u^2)\,du=\frac{1}{4}\left(u\ln(1+u^2)|_0^t-\int_0^t \frac{2u^2}{1+u^2}\right)\]
\[=\frac{t}{4}\ln(1+t^2)-\frac{t}{2}+\frac{\arctan t}{2}\]

Also by partial integration
\[\frac{1}{4}\int_0^t \ln(1-u^2)\,du=\frac{1}{4}\left(u\ln(1-u^2)|_0^t+\int_0^t \frac{2u^2}{1-u^2}\right)\]
\[=\frac{t}{4}\ln(1-t^2)-\frac{t}{2}+\frac{1}{4}\ln\left|\frac{1+t}{1-t}\right|\]

Therefore \[\frac{1}{4}\int_0^t \ln\left|\frac{1-u^2}{1+u^2}\right|\,dt=\frac{t}{4}\ln\left|\frac{1-t^2}{1+t^2}\right|+\frac{1}{4}\ln\left|\frac{1+t}{1-t}\right|-\frac{\arctan t}{2}\]

By previous computation $\int_0^1 \frac{\arctan t}{2}\,dt=\frac{t\arctan t}{2}-\frac{\ln(1+t^2)}{4}|_0^1=\frac{\pi}{8}-\frac{\ln 2}{4}$ and
$\frac{1}{4}\int_0^1 \ln\left|\frac{1+t}{1-t}\right|\,dt=\frac{(t+1)\ln(1+t)+(1-t)\ln(1-t)}{4}_0^1=\frac{\ln 2}{2}$ and
$\int_0^1\frac{t}{4}\ln\left|\frac{1-t^2}{1+t^2}\right|\,dt=\frac{-1}{2}\left(\frac{1}{4}\int_0^1\ln\left|\frac{1+t^2}{1-t^2}\right|\,d(t^2)\right)=\frac{-1}{2}\left(\frac{\ln 2}{2}\right)=\frac{-\ln 2}{4}$

Adding all numerical values we have the answer is
\[\frac{\ln(2)}{2}-\frac{\ln 2}{4}-\frac{\pi}{8}+\frac{\ln 2}{4}+\frac{\pi}{12}-\frac{1}{6}-\frac{\ln 2}{12}+\left(\frac{1-\ln 2}{6}\right)=\frac{\ln 2}{4}-\frac{\pi}{24}.\]

comment: This is a sudden-death problem, if you miscalculate the integral somewhere in the middle, you've wasted your valuable time nor you get a false answer. From the first minute i see the problem, i have so many ideas, but the surely one is the above. One possible idea is to use the Beta integral, or euler reflection formula. It is similar to the problem I solved in College Mathematical Journal years ago and the problem can be generalized to the following: Calculate
\[\sum_{k=1}^{\infty}\frac{m!}{\binom{mk}{m}} \qquad m\in \mathbb{Z} \qquad m>0\]
where in this problem $m=4$.


Problem 3. Define the sequence $x_1,x_2,\dots$ inductively by $x_1=\sqrt{5}$ and $x_{n+1}=x^2_n-2$ for each $n\geq 1.$ Compute
\[\lim_{n\to \infty} \frac{x_1\cdot x_2\cdots x_3\dots x_n}{x_{n+1}}.\]

Solution:  We have $x_{n+2}=x_{n+1}^2-2$ thus $x_{n+2}-2=x_{n+1}^2-4=(x_{n+1}-2)(x_{n+1}+2)$.The function $f(x)=x^2-2$ is increasing for positive $x$, and since $x_2 >x_1$ by induction the sequence is increasing, also $x_1>1$ inductively implies $x_n>n$, and hence $x_n$ is unbounded increasing positive sequence. Thus $\lim \frac{1}{x_n}=0$.
and related to $x_2=3>2$, we have $x_n > 2$ for all $n$, or in particular $x_n \neq 2$ for all $n$. Thus
\[x_{n+1}+2 = \frac{x_{n+2}-2}{x_{n+1}-2}\]
and since $x_n=\sqrt{x_{n+1}+2}$ we have
\[x_n =\sqrt{\frac{x_{n+2}-2}{x_{n+1}-2}}.\]
Now taking the product and telescoping we have
\[x_1 x_2 \cdots x_n =\sqrt{\frac{x_{n+2}-2}{x_2-2}}=\sqrt{x_{n+2}-2}=\sqrt{x_{n+1}^2-4}\]
and we wish to calculate
\[\lim_{n\to \infty} \frac{x_1\cdot x_2\cdots x_3\dots x_n}{x_{n+1}}=\lim_{n\rightarrow \infty} \sqrt{1-\frac{4}{x_{n+1}^2}}=1.\]

comment:  As usual problem 3 is tricky, i spent quite a lot of time to figure it out, after the unsuccessful trigonometric substitution, hyperbolic estimation, i finally arrive to the telescoping relation. I believe there should be a nice trigonometric substitution for this problem.

Next part is problem 4 and problem 5.. I couldn't solve them if i was given only 5 hours. The post is still in the draft, since i only can solve problem 5 for the moment.. :) Continue Reading

[ALGE III] The Field Of Rational Function of The Irreducible Variety

[ALGE III] The Field Of Rational Function of The Irreducible Variety

00:33:00   Algebraic Geometry,

Let $X$ be an irreducible curve given by $f(x,y)=0$ in the algebraic closed field $\mathbb{F}$, then we define the set
\[\mathbb{F}(X)=\left\{\left.\frac{p(x,y)}{q(x,y)} \right\lvert p,q \in \mathbb{F}[x,y] \mbox{ and } f(x,y)\not | q(x,y) \right\}\]
 Then $\mathbb{F}(X)$ contains the rational functions of two variables $x$ and $y$. We say two elements of $\mathbb{F}(X)$, $\frac{p_1(x,y)}{q_1(x,y)}$ and $\frac{p_2(x,y)}{q_2(x,y)}$ are equal in $X$ if and only if

\[f(x,y) | (p_1(x,y)q_2(x,y)-p_2(x,y)q_1(x,y))\]

It is easy to see that, along with this equality, $\mathbb{F}(X)$ is a field. We call $\mathbb{F}(X)$ is a Field of Rational Function on $X$ (or funcion field of algebraic variety $X$).
Before we proceed, we should aware that, the denominator of the rational function $\frac{p(x,y)}{q(x,y)} \in \mathbb{F}(X)$ can be zero only for finitely many points of $X$, that is $q(x,y)=0$ in a finite subset of $X$. This can be proved easily by using the Lemma in my first post [ALGE I]. It also can happen that, a rational function can be represented in two different expression $u=\frac{p(x,y)}{q(x,y)}$ and $\frac{p_1(x,y)}{q_1(x,y)}$ where $q(x,y)=0$ but $q_1(x,y) \neq 0$.  If $u$ has the exspresion $\frac{p(x,y)}{q(x,y)}$ where $q(P) \neq 0$, then we say $u$ is regular at $P$.

Now suppose that $X$ is rational curve, then by using the parametrization of $X$, we can substitue $x=\varphi(t)$ and $y=\psi(t)$ to the rational function $u=\frac{p}{q} \in \mathbb{F}(X)$. The substitution takes any element of $\mathbb{F}(X)$ to the rational function of one variable in $t$.  Notice that, the denominator $q(\varphi(t),\psi(t))$ can only equals zero in a finitely many times, by the same reason from the previous paragraph. Suppose that $u_1=\frac{p_1}{q_1}$ and $u_2=\frac{p_2}{q_2}$ are equals on $X$, then

\[p_1(x,y)q_2(x,y)- p_2(x,y) q_1(x,y) = \lambda(x,y) f(x,y)\]

substitute $x=\varphi(t)$ and $y=\psi(t)$, since $f(\varphi(t),\psi(t)) \equiv 0$ we have

\[\frac{p_1(\varphi(t),\psi(t))}{q_1(\varphi(t),\psi(t))}=\frac{p_2(\varphi(t),\psi(t))}{q_2(\varphi(t),\psi(t))}\]

thus, the substitution exhibit the map from $\mathbb{F}(X)$ to the $\mathbb{F}[t]$ (the field of rational function in $t$). This map is also an isomophism from $\mathbb{F}(X)$ to some subfield of $\mathbb{F}[t]$.
Now we can use Lüroth's Theorem to extend this property, that is it is indeed true that $\mathbb{F}(X)$ is isomorphic to $\mathbb{F}[t]$.

Continue Reading

[ALGE II] Rational Parametrization of Algebraic Curve

[ALGE II] Rational Parametrization of Algebraic Curve

07:52:00   Algebraic Geometry,

From the previous post, we know that any algebraic curve in the algebraic closed field can be decomposed into irreducible curves, which is a unique representation. So, it would be natural to look deeper on the irreducible curve. Recall that an algebraic curve $X$ defined by the equation $f(x,y)=0$, with irreducible polynomial $f(x,y) \in \mathbb{F}[x,y]$, where $\mathbb{F}$ is an algebraic closed field

We say an irreducible algebraic curve $X$ is  a rational curve, whenever there exist rational functions $\varphi$ and $\psi$ at least one is non-constant, such that \[f(\varphi(t), \psi(t)) \equiv 0.\]
$\varphi$ and $\psi$ are rational parametrization of $f$.

It is not hard to prove that every degree two irreducible curves $X$ (a conic) are rational curves, take a point $(x_0,y_0) \in X$ then substitute $y=t(x-x_0)+y_0$ to the equation $f(x,y)=0$, solving for $x$ we will find $x=\varphi(t)$ and substituting back to  $y=t(x-x_0)+y_0$ we will find $y=\psi(t)$.

Example: The Folium of Descartes is an algebraic curve $X$ defined by \[x^3+y^3-3axy=0\]
for the real number $a$.
Since $(0,0) \in X$, to get the rational parametrization we can try to substitute $y=tx$ yields
\[(t^3+1)x^3 - 3atx^2=0\]
 for the points other than $(0,0)$  we have from the above equation the parametrization
\[x=\varphi(t)=\frac{3at}{t^3+1}\qquad\text{and}\qquad y=tx=\psi(t)=\frac{3at^2}{t^3+1}\]
 
The geometric interpretation is also obvious. As we can see in the picture below, we can draw a line not contain the point $(0,0)$. and for any point $P \in X$ we project it to the line $x=-1$ by making the line joining $(0,0)$ and $P$. Hence, each point of the curve (other than $(0,0)$) produce a unique point on the line $x=-1$, and each point on the line $x=-1$ produce a unique point (correspondence with the origin) on the curve.

here the points on the line $x=-1$ act like $t$ in the parametrization, the parameter $t$ is the slope of the produced lines. So that the point $(-1,1)$ (which means $t=-1$) does not produce any point of the curve except $(0,0)$. This also can be seen in the parametrization $\varphi(t)$  and $\psi(t)$, where when $t=-1$, the denominator of both is zero.

We have seen that, the parametrization is important on determining the point on the curve. When the curve $X$ satisfy some criterion, for a suitable choice of $\varphi(t)$ and $\psi(t)$, we can get a one-to-one correspondence map $t \rightarrow (\varphi(t),\psi(t))$, by excluding some finite points of the curve. This is really interesting, one possible application is to the theory of indeterminte equation.  Suppose that $f(x,y)=0$ has rational coefficient, and suppose that the parametrization $\varphi(t)$ and $\psi(t)$ also have rational coefficient. If both $\varphi(t)$ and $\psi(t)$ are a bijection, we can list all the rational points of the curve, given we know only one point (for example, in the previous example we were given $(0,0)$ on the folium).

In the number theory, The Fermat Last Theorem, can be viewed as proving that a rational point of the of the curve $x^n+y^n-1=0$ does not exist.

Thus the problem whether a curve have a rational parametrization is essentially important.
Our next realm is to determine when a given curve is a rational curve?
 

Continue Reading

[ ALGE I ] Introduction to the Plane Algebraic Curve

[ ALGE I ] Introduction to the Plane Algebraic Curve

22:24:00   Algebraic Geometry,

Well i'm going to retell what i've  studied from the algebraic geometry books so far.. one of my favorite book is the Basic Algebraic Geometry: Varieties in Projective Space  By Shafarevich.

Let $\mathbb{F}$ be an algebraic closed field. An algebraic curve $X$ is the set of points $(x.y)$ defined by the equation \[f(x,y)=0\]
where $f(x,y) \in \mathbb{F}[x,y]$.
When  $f(x,y)$ is an irreducible polynomial, we say $X$ is an algebraic irreducible curve.
The degree of $X$ is equal to $\text{deg}f$. The condition that $\mathbb{F}$ must be an algebraic closed field is necessary for the uniqueness of the degree of $X$.
For example the curve $(0,0)$ in the field of real numbers is defined by infinitely many equations that is $x^{2n}+y^{2n}=0$ for any positive integers $n$. For even $n$ the curve is irreducible, while whenever $n$ is odd, the curve is reducible.This confusion doesn't happen when $\mathbb{F}$ is an algebraic closed field. As we can prove it by the following very useful lemma:

 Lemma:  Let $\mathbb{F}$ be a field, given an irreducible polynomial $f \in \mathbb{F}[x,y]$. Then for any polynomial $g \in \mathbb{F}[x,y]$ which is not divisible by $f$,  the system of equations $f(x,y)=g(x,y)=0$ has only finitely many solutions.


Proof:  We view $f$ and $g$ as the element of $u[y]$, where $u$ is the field of rational function of $x$ with coefficient in $\mathbb{F}$. By Gauss Lemma, it is easy to see that $f$ remains irreducible in $u[x]$  and also $f$ and $g$ are still relatively prime in $u[y]$. Thus there exists $\lambda, \mu \in u[y]$ such that
 \[f \lambda + g \mu =1\]
Multiplying by the common denominator $a(y) \in \mathbb{F}[y]$ we will get
\[f(x,y) \lambda(x,y) + g(x,y) \mu(x,y) = a(y)\]
If $(\alpha, \beta)$ is the solution of the system of equations. Then $a(\beta)=0$, and there are only finitely many possibility of such $\beta$. Thus $\alpha$ is the root of equation $f(x, \beta)=0$, and there are also a finitely many value of them. The result follows.

Applying the lemma, let $X$ be an irreducible algebraic curve in an algebraic closed field. If there are two such equations which define  $X$ say $f(x,y)=0$ and $g(x,y)=0$, since $f(x,y)=0$ has infinitely many solution in the algebraic closed field then the systems of equations $f(x,y)=g(x,y)=0$ also has infinitely many solutions. Hence the lemma says that $f(x,y)=c g(x,y)$. Thus the two equations are essentially the same.

The same is true for arbitrary curve $X$. Suppose that its equation is $h(x,y)=0$. Since $\mathbb{F}[x,y]$ is a Unique Factorization Domain,  therefore
\[h=f_1^{k_1} f_2^{k_2} \cdots f_n^{k_n}\]
for irreducible polynomial $f_i \in \mathbb{F}[x,y]$. The points such that $h(x,y)=0$ are also such points so that $f_i(x,y)=0$ for some $i$. Let $X_i$ be a curve defined by $f_i (x,y)=0$, then we have \[X= \bigcup_{i=1}^n X_i \]
where $X_i$ is an irreducible curves.
This decomposition is called the irreducible components decomposition. Since the equation of each $X_i$ is irreducible and defined by the equation which only may differ by constant multiple, so any other equation of $X$ is also differ from $h$ by the constant multiple. Continue Reading

Just an exam problem

Just an exam problem

11:12:00   soal-soal,

Soal

Misalkan \[A={\underbrace{(999 \cdots 9)}_{\mbox{2008 buah}}}^{2009} \qquad \mbox{dan} \qquad B={\underbrace{(999 \cdots 9)}_{\mbox{2005 buah}}}^{2009}\]

Tunjukan bahwa digit dari

B dapat diperoleh dari A dengan cara menghapus beberapa buah digit

nya.

Solusi:

Untuk $0\leq m \leq 2009$ misalkan

\[A_m=\sum_{k=0}^{m} \binom{2009}{k} 10^{2008k} (-1)^{k+1} \qquad B_m= \sum_{k=0}^{m} \binom{2009}{k} 10^{2005k} (-1)^{k+1}\]

Jadi $A_{2009}=A$ dan $B_{2009}=B$.

Pertama-tama ditunjukan bahwa $2005$ buah digit terakhir dari $A$ dan $B$ sama. Karena $2005<2008$  maka $A \pmod {10^{2005}} = -1$ dan $B \pmod {10^{2005}} = -1$. Jadi $2005$ buah digit terakhir $A$ dan $B$ sama.

Berikutnya akan ditunjukan bahwa aturan pencoretan dari digit-digit $A$ untuk memperoleh digit-digit $B$ adalah dengan  sebagai berikut:

Mulai dari digit paling kanan, dimana telah dibuktikan $2005$ buah digit paling kanan $A$ sama dengan $B$. Kemudian hapus $3$ digit seterusnya (digit ke $2006$ sampai digit ke $2008$ dari kanan)

kemudian $2005$ digit berikutnya dari $A$ akan sama dengan digit ke $2006$ sampai $2(2005)$ digit $B$ dari kanan, dan seterusnya.

\[A=\underbrace{c_1 c_2 c_3}_{\mbox{dicoret}} d_1 d_2 \cdots d_{2005}\underbrace{e_1 e_2 e_3}_{\mbox{dicoret}}\cdots\cdots\underbrace{f_1 f_2 f_3}_{\mbox{dicoret}} g_1 g_2 \cdots g_{2005} \]

\[B= b_1 b_2 \cdots b_{2005} \cdots \cdots d_1 d_2 \cdots d_{2005} \cdots \cdots g_1 g_2 \cdots g_{2005}\]

Untuk membuktikan hal ini, pertama-tama kita buktikan beberapa lemma berikut:

Lemma 1

 Untuk $0\leq m \leq 2009$ berlaku 

\[|A_m|<10^{2008m+1005} \qquad \text{dan} \qquad |B_m|<10^{2005m+1005}\]

bukti:

 Berdasarkan sifat koefisien binomial $\binom{2009}{k} < \binom{2009}{1004} = \frac{(2009)(2008)\cdots (1006)}{(1004)(1003)\cdots (1)}<10^{1004}$. Dengan ketaksamaan segitiga

\[\begin{align*}\left|\sum_{k=0}^{m} \binom{2009}{k} (-1)^{k+1} 10^{2008k}\right| &\leq \sum_{k=0}^m \left|\binom{2009}{k} 10^{2008k}\right|\\ &<\binom{2009}{1004} \sum_{k=0}^{m} 10^{2008k}\\ &= \binom{2009}{1004} \left(\frac{10^{2008m+2008}}{10^{2008}-1}\right)\\ &< 10^{1004} \left(\frac{10^{2008m+2008}-1}{10^{2008}-1}\right) \\ &< 10^{1004} \left(\frac{10^{2008m+2008}}{ 10^{2007}}\right)\\ &< 10^{2008m+1005}\end{align*}\]

Ketaksamaan yang kedua dapat dibuktikan secara similar.

Lemma 2

 Jika $m$ ganjil maka $A_m >0$ dan $B_m>0$, sebaliknya jika $m$ genap maka $A_m<0$ dan $B_m<0$.

Bukti:

Berdasarkan Lemma 1,
\[-10^{2008m}< A_{m-1} <10^{2008m}.\]

Untuk $m$ ganjil berlaku $10^{2008m}<\binom{2009}{m} (-1)^{m+1} 10^{2008m}$. Sehingga diperoleh

\[0<-10^{2008m}+\binom{2009}{m} (-1)^{m+1} 10^{2008m}< A_m \Longrightarrow A_m>0.\]

Untuk $m$ genap berlaku $10^{2008m}<\binom{2009}{m} (-1)^{m} 10^{2008m}$, kalikan ketaksamaan ini dengan $-1$ diperoleh \\ $\binom{2009}{n} (-1)^{n+1} 10^{2008n}<-10^{2008n}$. Sehingga diperoleh

\[A_m < \binom{2009}{m} (-1)^{m+1} 10^{2008m}+10^{2008m} < 0 \Longrightarrow A_m<0.\]

Pembuktian untuk $B_m$ dapat dilakukan dengan similar.

Sekarang akan dibuktikan pernyataan yang diklaim diawal. Misalkan $n$ adalah bilangan bulat yang terletak pada interval $(0,2009)$.

perhatikan bahwa hasil dari $A \mod {10^{2008n+2005}}$ menyatakan $2008n+2005$ digit terakhir dari $A$ (dengan menambahkan beberapa buah 0 dikiri apabila diperlukan). Karena $10^p \mod 10^q=0$ untuk $p \geq q$ maka

\[\begin{align*}A \mod 10^{2008n+2005} &=\left[\sum_{k=0}^{2009} \binom{2009}{k} 10^{2008k} (-1)^{k+1}\right] \mod 10^{2008n+2005}\\ &=A_n +a10^{2008n+2005}\end{align*}\]

Berdasarkan Lemma 1 , $|A_n|<10^{2008n+1005}<10^{2008n+2005}$,  jadi hasil modulo diatas tidak lebih dari $10^{2008n+2005}$ sehingga apabila $A_n$ positif maka nilai $A_n$ samadengan $2008n+2005$ digit terakhir dari $A$, dan apabila $A_n$ negatif maka $2008n+2005$ digit terakhir dari $A$ adalah $10^{2008n+2005}+A_n$. Dengan kata lain, menggunakan Lemma 2 diperoleh

\[a=\begin{cases}1\quad & \mbox{$n$ genap}\\ 0 \quad & \mbox{$n$ ganjil}\end{cases}\]

Kemudian $2008n$ digit terakhir dari $A$ adalah

\[\begin{align*}A \mod {10^{2008n}}&=\left[\sum_{k=0}^{2009} \binom{2009}{k} 10^{2008k} (-1)^{k+1}\right] \mod 10^{2008n}\\ &\equiv\sum_{k=0}^{n-1} \binom{2009}{k} 10^{2008k} (-1)^{k+1}\\ &=A_{n-1}+b10^{2008n}\end{align*}\]

Berdasarkan Lemma 1 , $|A_{n-1}|<10^{2008(n-1)+1005}<10^{2008n}$,  jadi hasil modulo diatas tidak lebih dari $10^{2008n}$ sehingga apabila $A_{n-1}$ positif maka nilai $A_{n-1}$ samadengan $2008n$ digit terakhir dari $A$, dan apabila $A_{n-1}$ negatif maka $2008n$ digit terakhir dari $A$ adalah $10^{2008n}+A_{n-1}$.  Dengan kata lain, menggunakan Lemma 2 diperoleh

\[b=\begin{cases}1 \quad & \mbox{$n-1$ genap}\\ 0 \quad & \mbox{$n-1$ ganjil}\end{cases}\]

Hal ini berarti $a \neq b$, atau $|a-b|=1$.

Dengan penalaran yang sama

\[\begin{align*}B \mod {10^{2005n}} &=\left[\sum_{k=0}^{2009} \binom{2009}{k}10^{2008k}(-1)^{k+1}\right]\mod 10^{2005n}\\ &\equiv\sum_{k=0}^{n-1} \binom{2009}{k} 10^{2005k} (-1)^{k+1} \\ &=B_{n-1}+c10^{2005n}\end{align*}\]

dimana $c=b$.

\[\begin{align*}B\mod{10^{2005(n+1)}}&=\left[\sum_{k=0}^{2009} \binom{2009}{k} 10^{2008k} (-1)^{k+1}\right] \mod 10^{2005(n+1)}\\ &\equiv\sum_{k=0}^{n} \binom{2009}{k} 10^{2005k} (-1)^{k+1}\\ &=B_{n}+d10^{2005(n+1)}\end{align*}\]

dimana $d=a$.

Akan dibuktikan

 \[\begin{align}\left(\frac{A \mod {10^{2008n+2005}} - A \mod {10^{2008n}}}{10^{3n}}\right)+ B \mod {10^{2005n}} = \\ B \mod {10^{2005(n+1)}}\end{align}\]

yang berarti bagian digit $2008n+1$ sampai $2008n+2005$ dari $A$  samadengan bagian digit ke $2005n+1$ sampai $2005(n+1)$ dari $B$. Persamaan (1) setara dengan

\[\begin{aligned}\frac{A_n +a10^{2008n+2005}-A_{n-1}-b10^{2008n}}{10^{3n}} +B_{n-1}+c10^{2005n} =B_{n}+d10^{2005(n+1)}\end{aligned}\]

Dari persamaan-persamaan yang diperoleh sebelumnya diperoleh

\[\begin{align*}A_n +a10^{2008n+2005}-A_{n-1}-b10^{2008n} =\\ \binom{2009}{n}10^{2008n} (-1)^n + a10^{2008n+2005} -b10^{2008n} \end{align*}\]

Jadi

\[\begin{align*}\frac{A_n +a10^{2008n+2005}-A_{n-1}-b10^{2008n}}{10^{3n}} +B_{n-1}+c10^{2005n} = \\ B_n + a10^{2005(n+1)} -b10^{2005n}+ c10^{2005n} \end{align*}\]

Karena  $c=b$ dan $a=d$ diperoleh

\[B_n + a10^{2005(n+1)} -b10^{2005n}+ c10^{2005n} =B_n + a10^{2005(n+1)} = B_n + d10^{2005(n+1)}\]

seperti yang diharapkan.

Continue Reading