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

Burnside's Lemma and coloring graph (first insight)

Burnside's Lemma and coloring graph (first insight)

03:45:00   Algebraic Combinatorics,

Months ago, while helping my junior working his skripsi, I learned about a theorem in algebraic combinatorics called Polya's Enumeration Theorem. Actually I already known this handy theorem before, but haven't give it much thought before.

Before explaining about Polya's Enumeration Theorem, it is cultural to explain first about Burnside Lemma, which is a theorem in a Group Theory..

As some of undergraduate student learn about permutation group. Denote $S_n$ as the permuation group of $n$ elements. It's particularly useful to think the $S_n$ as the set of all bijective functions $p:\{1,2,\cdots,n\} \rightarrow \{1,2,\cdots,n\}$.


Recall that any elements of $S_n$ can be represented by its cycle decomposition. For example in $S_8$, the function $p$ s.t $p(1)=1$, $p(2)=4$, $p(3)=2$, $p(4)=3 $, $p(5)=7$, $p(6)=5$, $p(7)=8$, $p(8)=6$ can be rewritten as $(1)(2 4 3)(5 7 8 6)$. In this case we say $f$ is decomposed into three cycles:


$(1)$ has length one


$(2 4 3)$ has length three


$(5 7 8 6)$ has length four.


Some books usually remove the cycle of length one, so then the permutations above are simply written as


$(2 4 3)(5 7 8 6)$, with no danger of confusion.


Orbit = Equivalence Class

Given a subgroup $D \subset S_n$, we define the relation $\sim_D$ on the set $\{1,2,\cdots, n\}$ as follow

$x \sim_D y$ if and only if there exists $p \in D$ such that $p(x)=y$.


It is easy to see that the above relation is an equivalence relation and so this relation partitions the set $\{1,2,\cdots, n\}$ into some disjoint classes by the rule of the subgroup $D$. We call these equivalence classes as the orbits of $D$ . When the notation comes into play , the orbit of $D$ which contains $x$ is usually denoted by $O_x$ and clearly since the identity function is always in the subgroup we have $O_x=\{p(x) | p \in D\}$.


Two elements $x$ and $y$ are contained in the same orbit of $D$ if and only if $x \sim_D y$ if and only if there exists $p \in D$ such that $p(x)=y$ if and only if by some rule of permutation in $D$, $x$ can be placed in the position that is previously occupied by $y$, and vice versa.


To count how many different orbits of $D$ are there we can use the following lemma, known as Burnside's Lemma

\[t=\frac{1}{|D|} \sum_{p \in D} F(p)\]

where $F(p)$ is the number of the fix points of permutation $p$.


Permuting The Graph


Suppose that the graph $G$ has $n$ vertices, each vertices are numbered by numbers from $1$ to $n$. Since for any $p \in S_n$, $p$ permutes $1,2, \cdots, n$ then $p$ also permutes the vertices of $G$ without changing its edging rule, that's the resulting graph is isomorphic to the permuted graph.


For example doing the permutation $(1 2 3)$ to a triangle graph (vertices are numbered 1,2, and 3 clockwise from the top ) is equivalent to rotating the triangle.

Coloring Graph

Suppose that we want to color a graph $n$ vertices $G$ , with the set of Color $V:=\{c_1,c_2, \cdots. c_m\}$. Each coloring can be uniquely represented by the function $c: \{1,2, \cdots, n\} \rightarrow V$, by mean that $c(k)=c_3$ means that the vertex with number $k$ is colored by $c_3$ color (one can specify $c_3$ as blue, red, white etc.). The function ruling the assignment of the colors into each vertex. The set of all functions $c: \{1,2, \cdots, n\} \rightarrow V$ is denoted by $C_{n,m}$.


Given a permutation $p \in S_n$, for any coloring function $c \in C_{n,m}$ consider the function $\bar{p}: C_{n,m} \rightarrow C_{n,m}$


\[\bar{p}(c) := c \circ p^{-1}\].

We can prove that $\bar{p}$ is a bijective from $C_{n,m}$ to itself.


What does the $\bar{p}$ actually mean?


As we already know that $p$ permutes the vertices of the graph. And after the graph has been colored, we know that permuting the vertices also permuting the color attached on each of it and hence resulting the other coloring, OR in other words resulting another element of $C_{n,m}$. For example $\bar{p}(c_1)=c_2$ means that the coloring $c_2$ is obtained by permuting the vertices of the graph which are already been colored by using coloring $c_1$, and the permutation used is permutation $p$.


The set $\bar{S_n}=\{\bar{p}: p \in S_n\}$ is a group. In fact, it consists the permutation of the color-function. That is we can view it as the permuation group $S_{|C_{n,m}|}$. It is easy to see that $|C(n,m)|=m^n$ and hence $|S_{|C_{n,m}|}|=(m^n)!$


Given a subgroup $H$, then we can define $\bar{H}=\{\bar{p}: p \in H\}$. It is not hard to prove that $\bar{H}$ is a subgroup of $\bar{S_n}$.


A question then arise:

What are the orbits of $\bar{H}$ in $S_{|C{m,n}|}$ ?

They should be the subsets of $C_{n,m}$. Observe that, two elements $c_1,c_2 \in C_{n,m}$ are in the same orbit of $\bar{H}$ if and only if there exists $\bar{p} \in \bar{H}$ such that $p(c_1)=c_2$.


That is any coloring contained in the same orbit of $\bar{H}$ is just the permutation of each other using permutation in $H$ (not necessarily $\bar{H}$).


For simplicity, let assume that $G=R_4$ is a rectangle and $V=\{red,blue,green\}$. In this case $R_4$ has four vertices denoted by the number $1,2,3$ and $4$, numbered clockwise starting from the top-left vertex (actually the rule of numbering isn't really a big deal, one can use different numbering for initial graph as long as he/she keep it consistent).

To make it shorter, we will refer a coloring as a string with four letters, where the $i$-th letter denote the initial of the color assigned to vertex $i$, that is the coloring $rbrg$is understood to br$c(1)=red$, $c(2)=blue$, $c(3)=red$ and $c(4)=green$.


Now, imagine an already colored rectangular graph as a rectangular toy. Then the toys obtained from the coloring $rbrg$, $grbr$, $rgrb$, and $brgr$ are the same toy, up to a rotation (several rotations $90^\circ$ clockwise by the center of rectangle). And the toys obtained from the coloring $rbrg$ and $brgr$ are also the same (obtained by flipping the toy).


Therefore to enumerate all different toys, we need to count the toy and its corresponded toys obtained by rotation or flip as one.


[for those who are not familiar with symmetric group]


In $R_4$, initially we have the numbered vertices in order 1-2-3-4. After rotating the graph 90 degree clockwise, the position previously occupied by 1 is now being occupied by 4, the 2's position is now being occupied by 1, the 3's position is now being occupied by 2, and the 4's position is now being occupied by 3. Therefore we have done the permutation $\rho(1)=4$, $\rho(2)=1$, $\rho(3)=2$, $\rho(4)=3$ or $(1 4 3 2)$. Similarly, the flip permutation is simply $(1 2)(3 4)$. And all possible combination of permutation of the $R_4$ obtained from flipping or rotating are contained in

\[\begin{align*}D_4 =\{& (1)(2)(3)(4), (1)(2 4)(3), (1 2)(3 4), (1 2 3 4), (1 3)(2)(4), \\ &(1 3)(2 4), (1 4 3 2), (1,4)(2,3)\}\end{align*}\]

that is our Dihedral Group.


[Don't Forget Our $\bar{H}$ ]


As, we already seen before, the orbits of $\bar{H}$ are the subsets of $C_{n,m}$. And two elements (colorings) $c_1,c_2 \in C_{n,m}$ are in the same orbit, if there exists $\overar{p} \in \bar{H}$ such that $\bar{p}(c_1)=c_2$.


Therefore, in the Toy Factory example, if we set $H=D_4$, we see that the Toys contained in the same orbit of $\bar{H}$ in $S_{|C_{n,m}|}$ are same. Thus the number of different orbits of $overbar{H}$ in $S_{|C_{n,m}|}$ is equal to the number of different Toys. The Burnside Lemma now becomes very handful.


In general, for any subgroup $H \subset S_n$, the number of different Orbits of $\bar{H}$ in $\bar{S_{n}}$ tells us the number of nonequivalent coloring of the $n$ vertices graph (up to subgroup $H$).

So then, how can we apply Burnside Lemma here? It should be

\[\frac{1}{|\bar{H}|} \sum_{ \bar{p} \in \bar{H} } F(\bar{p})\]


well, clearly $|\bar{H}|=|H|$, and also it doesn't really matter if we replace $\sum_{\bar{p} \in \bar{H}}$ with $\sum_{p \in H}$, since for each $p \in H$ we have $\bar{p} \in \bar{H}$ and vice-versa. Now it remains to find $F(\bar{p})$.


$F(\bar{p})$ counts how many elements of $C_{n,m}$ which is sent to itself by $\bar{p}$ (i.e the fixed-point of $\bar{p}$). That is how many $k$ such that $\bar{p}(f_k)=f_k$. Recall that $\bar{p}(f_k)= f_k \circ p^{-1}$, thus $\bar{p}(f_k)=f_k$ is equivalent to $f_k \circ p^{-1} = f_k$ and so $f_k = f_k \circ p$. If we set $p$ to be identity map $id_n$, then all $f_k \in C_{n,m}$ satisfy $f_k = f_k \circ p$, thus $F(\bar{id_n})= |C_{n,m}|=m^n$.


Consider the cycle composition of $p$, say

\[p=(a_{j_1} a_{j_1+1} \cdots a_{j_2 -1})(a_{j_2} \cdots a_{j_3 -1}) \cdots (a_{j_i} \cdots a_{j_{i+1}-1}) \cdots (a_{j_l} \cdots a_n)\]

that is $p$ is composed into $l$ cycles.

A routine calculation shows that $f_k = f_k \circ p$ implies

\[f_k(a_{j_1})=f_k(a_{j_1+1}) = \cdots = f_k(a_{j_2 -1}).\]

And similarly

\[f_k(a_{j_i })= f_k(a_{j_i + 1}) \cdots = f_k(a_{j_{i + 1}-1}).\]

An indication that the number of the cycles of $p$ is involved in the $F(\bar{p})$, so we denote it by $c(p)$, where in above $c(p)=l$. In fact, to determine $f_k$, we only need to know the value of $f_k(a_{j_i})$ for $i=1,2,\cdots,l$. So the number of such $f_k$ is equal to the number of function $f: \{a_{j_1}, \cdots, a_{j_l} \} \rightarrow \{c_1, c_2, \cdots, c_m\}$ which is easily computed to be $m^{l}$. Thus we have $F(\bar{p})= m^{c(p)}$. (it is consistent with our earlier observation when $p$ is identity map.)

And we get the formula for the number of nonequivalent colorings (up to symmetric group $H$) of graph $G$ with $n$ vertices is

\[\frac{1}{|H|} \sum_{p \in H} m^{c(p)}\]

where $m$ is the number of colors used and $c(p)$ is the number of cycles in the cycle decomposition of $p$.

The application of this theorem will be reviewed on the next post.

Continue Reading