Thursday 26 December 2013

Christmas songs

I joined a few musical events before the end of 2013 which include the nutcracker performance (for those who follow don't shoot the pianist, you will know that Nov and Dec are always the time for such performance lol) but I also spent some time on reviewing old and new Christmas songs. By chance I found the game BGM Christmas in the 13th month which is a wonderful piece after all. Now I'm enjoying a succeeder of the song, dancing Christmas in the 13th month's remix from sync. art (I guess it's well known for their touhou remixes) so I hope that you will enjoy them too. Well the above one isn't from sync. art but the best performance among all clips in my opinion that the smooth sound from the viola greatly enhance the dancing that mixes well with the lively going background.

Merry Christmas.

Thursday 19 December 2013

A rare diary

It's long since my last diary written here but this is an important one. As some sort of researcher in the field of computational complexity, I ought to dig the SIMC problem out and make an in depth analysis on it, in particular the complexity classification, and algorithm solving them.

Allow me to brief the problem here.

In the graph, assume every edge has weight 1 that the distance can be calculated accordingly. We also define the distance between edges and vertices. For $e = (u,v) \in E$, $d(e,w) = 0.5 + min(d(u,w), d(v,w))$ and the distance between edges immediately follows. It is clear that the distance measurement is metric. (why?)

For a graph $G = (V,E)$ with two disjoint sets of vertices $V_s, V_c$, define score to be the number of edges closer to $V_c$. i.e. $d(e, V_c) \leq d(e, V_s)$. If the distances are equal it counts as 0.5.

Let's have a function to describe the score: $f(G, V_s, V_c) =~score$.

Instance: $G = (V,E)$ and two disjoint sets of vertices $V_s, V_c \subseteq V$, with some further constraint specified upon the challenge.
Output: Another set $V_{c'}\subseteq V$ that is mutually disjoint with $V_s, V_c$.
Goal: Maximize $f(G,V_s, V_c \cup V_{c'})$.

Maybe you have already heard it before, that Greedy algorithm works really well for this problem. Is it the best solution? It is clear that the greedy algorithm is a polynomial time algorithm. Then is this problem in P? Is it NP? This will be an exciting review of the old problem.

Sunday 15 December 2013

GCD and exponents

LCM (least common multiple) and GCD (greatest common divisor) (for integers as a integral domain) is a relatively easy field that indicates similar behavior for some numbers. In the previous entry I have constructed some related identities using prime factorization, and here I would like to introduce a few related problems that we use the properties of GCD and LCM to solve it.

Definition. For natural numbers $a_1, ..., a_n$, let $[a_1,...,a_n]$ be their LCM and $(a_1,...,a_n)$ be their GCD.

Theorem. For $m,n\in \mathbb{N}$, $mn = [m,n](m,n)$.

Q1. (Korea MO 2013, Day2 Q1) Find all $f: \mathbb{N}\rightarrow \mathbb{N}$ so that $f(mn) = [m,n](f(m), f(n))$.

When you see the above theorem a very natural solution is that $f(m) = m$ but we are asked to find all of them. Is this possible?

Substitute $(m,n) = (1,k)$, we have $f(k) = k(f(1),f(k)) = [1,k](f(1),k(f(1),f(k)))$. Let $(f(1),f(k)) = m$ then $f(k) = k(f(1),km) = km$. It is clear that $m \mid f(1)$ so that $f(k) = k(f(1),km) = kmp$ where $p\in \mathbb{N}$. Clearly, $p=1$ so that $(f(1), k) = 1$. Since $k\in \mathbb{N}$ is arbitrary, we have $f(1) = 1$, and $f(k) = k(f(1),km) = k$.

Here we should notice a fact:

Fact 1. $[a_1,...,a_n] \geq max(a_1,...,a_n)$ and $(a_1,..,a_n) \leq min (a_1,...,a_n)$

GCD is something that decrease when you repetitively take it, and if you can take it arbitrarily that gives the same result, the number is probably 1.

In this question, we put the expansion of $f(k)$ to get a looped GCD brackets, but it can be taken alternatively:

Fact 2. For $m,n\in \mathbb{N}$, $(m,n) = (m,(m,n))$.

The next question is about GCD identity on more variables.

Q2. Find all $(a,b,c) \in \mathbb{N} ^3$ so that $[a,b,c](a,b,c) = abc$

We use the proven identities from the last entry:

Theorem. For $a,b,c\in \mathbb{N}$, $[a,b,c]^2 \prod _{cyc} (a,b) = (a,b,c)^2 \prod _{cyc} [a,b]$.

Now $[a,b,c]^2(a,b,c)^2 = (a,b,c)^4 \prod _{cyc} [a,b]/(a,b) = (a,b,c)^4 \prod _{cyc} (ab/(a,b)^2) = (abc)^2 (a,b,c)^4/ \prod _{cyc} (a,b)^2 $ and we have

$[a,b,c](a,b,c) = abc (a,b,c)^2/ \prod_{cyc} (a,b)$

To make the last term 1 it is clear that all numbers must be relatively prime. To see why simply note that $(a,b)^2 \geq (a,b) \geq (a,b,c)$ and equality holds iff $(a,b) = 1$ so that we need $(a,b) = (b,c) = (c,a) = 1$, then $(a,b,c) = 1$.

Clearly all relatively prime triplets satisfies the question.

Sometimes the GCD and LCM notation takes all prime factors into account, but what if we want to consider a particular prime? We can prove the case for a certain prime and by enumerate through the primes we get the desired result as every natural numbers (which is finite) can be factorized into (finite) primes.

Definition. (Highest exponent) For $n\in \mathbb{N}$ and prime $p\in \mathbb{P}$ denote $v_p(n) = k$ if $p^k \mid n$ but $p^{k+1}\nmid n$. If $p\nmid n$ then $v_p(n) = 0$. (In some texts we don't allow 0 but here we just let it be)

Then we can prove GCD results in terms of prime exponents, and the proof is naturally completed by the FTOArithmetic.

Example 1. $v_p([a,b]) = max(v_p(a), v_p(b))$ and $v_p((a,b)) = min (v_p(a), v_p(b))$.

Example 2. Since $max(a,b) + min(a,b) = a+b$, we have $v_p([a,b](a,b)) = v_p([a,b])+v_p((a,b)) = a+b$, which proves the identity $(a,b)[a,b] = ab$.

Example 3. When there are more variables and the equation of interest is cyclic we can WLOG assume the order, here let $v_p(a) =x$, $v_p(b) = y$ and $v_p(c) = z$ and WLOG let $x\geq y\geq z$. Then

$v_p([a,b,c]^2\prod (a,b)) = v_p((a,b,c)^2 \prod [a,b]) = 2x+y+2z$

Here we have an alternate prove for Q2, from mathlinks, using the exponent notation:

Let $v_p(a) =x$, $v_p(b) = y$ and $v_p(c) = z$ and WLOG let $x\geq y\geq z$. The question is equivalent to $x+z = x+y+z$ so that $y = 0 \geq z = 0$, so that $(a,b) = (b,c) = (c,a) = 1$ due to cyclic assumption. Then $(a,b,c) = 1$ and $[a,b,c] = abc$.

Q3. Find all triplets $(a,b,c) \in \mathbb{N}^3$ so that $a+b = (a,b)^2$ in cyclic manner.

We always get trouble when addition steps into questions on GCD. To do this notice that for prime $p\geq 3$, it is impossible that $v_p(a+b) \geq v_p ((a,b))+1$ for all $(a,b) \leftarrow (a,b), (b,c),(c,a)$ (why?) Then we have $(a,b)$ equals to 1 or 4, which allow us to enumerate all cases.

Using the exponent notation we can have a very powerful theorem called the lifting the exponent lemma, that allows us to use the exponent notation to find the highest power of some complicated forms. These can be easily searched so I will not cover it here. It is actually frequently used in current Olympic tournaments!

Three little problems:

1) (Russian MO 1999) Find all bounded sequence $\left\{ a_n \right\} \subseteq \mathbb{N}$ where for all $n\geq 3$, $n\in \mathbb{N}$, $a_n = (a_{n-1}+a_{n-2})/(a_{n-1},a_{n-2})$.

2) (A classical lemma) For $a,m,n\in \mathbb{N}$ and $a\geq 2$ show that $(a^m -1, a^n - 1) = a^{(m,n)}-1$.

3) Describe all the triples $(a,b,c)\in \mathbb{N}^3$ so that $[a,b,c](a,b,c) = \sqrt{abc}$.