On permutation

Let x_1, x_2, \dots, x_k be vectors of m – dimensional Euclidean space such that x_1+x_2+\cdots+x_k=0. Prove that there exists a permutation \pi of the integers \{1, 2, \dots,k\} such that

    \[\left \| \sum_{i=1}^{n} x_{\pi(i)} \right \|\leq\left ( \sum_{i=1}^{k} \left \| x_i \right \|^2 \right )^{1/2}\]

for each n=1,2, \dots, k.

Solution

We define \pi inductively. Set \pi(1)=1.Assume \pi is defined for i=1, 2, \dots, n and also

(1)   \begin{equation*} \left \| \sum_{i=1}^{n} x_{\pi(i)} \right \|^2 \leq \sum_{i=1}^{n} \left \| x_{\pi(i)} \right \|^2 \end{equation*}

Note that (1) is true for n=1. We choose \pi(n+1) in a way that (1) is fulfilled for n+1 instead of n. Set y=\sum \limits_{i=1}^{n} x_{\pi(i)} and A=\{1,2, \dots, k\} \setminus \{\pi(i) : i=1,2, \dots, n\}. Assume that (y, x_r)>0 for all r \in A.  Then \left ( y , \sum \limits_{r \in A} x_r \right )>0 and in view of y + \sum \limits_{r \in A} x_r =0 ones gets -(y, y)>0 which is impossible. Hence , there is r\in A such that

(2)   \begin{equation*} (y, x_r)\leq 0\end{equation*}

Put \pi(n+1) = r . Then using (2) and (1) we have

    \begin{align*} \left \| \sum_{i=1}^{n+1} x_{\pi(i)} \right \|^2 &= \left \| y + x_r \right \|^2 \\ &=\left \| y \right \|^2 + 2\left ( y, x_r \right ) + \left \| x_r \right \|^2 \\ &\leq \left \| y \right \|^2 + \left \| x_r \right \|^2 \\ &\leq \sum_{i=1}^{n} \left \| x_{\pi(i)} \right \|^2 + \left \| x_r \right \|^2\\ &= \sum_{i=1}^{n+1} \left \| x_{\pi(i)} \right \|^2 \end{align*}

which verifies (1) for n+1. Thus we define \pi for every n=1, 2, \dots, k. Finally from (1) we get

    \[\left \| \sum_{i=1}^{n} x_{\pi(i)} \right \|^2 \leq \sum_{i=1}^{n} \left \| x_{\pi(i)} \right \|^2 \leq \sum_{i=1}^{k} \left \| x_i \right \|^2\]

Read more

Irreducible fraction

Find all positive integers \alpha such that it holds that

(1)   \begin{equation*} \frac{1}{\alpha} = 0.\bar{\alpha} \end{equation*}

where \overline{ \cdot } stands for the period.

Solution

Well,

    \begin{align*} \frac{1}{\alpha} = 0.\bar{\alpha} &\Leftrightarrow \frac{1}{\alpha} = 0.\alpha \alpha \alpha \dots \\ &\Leftrightarrow \frac{1}{\alpha} = \frac{\alpha}{10} \sum_{i=0}^{\infty} \frac{1}{10^i} \\ &\Leftrightarrow \frac{1}{\alpha} = \frac{\alpha}{9}\\ &\!\!\!\!\!\!\!\overset{\alpha>0}{\Leftarrow \! =\! =\! \Rightarrow } \alpha = 3 \end{align*}

Read more

Divisibility

Prove that the product of n consecutive positive integers divides n!.

Solution

The number of different combinations of N+n over N is of course an integer and equals to

    \[\begin{pmatrix} N+n\\ N \end{pmatrix} = \frac{(N+1)(N+2)...(N+n)}{n!}\]

and the result follows.

Any questions?

Read more

gcd and subgroup

Let H be a non trivial subgroup and a_1, a_2, \dots , a_n \in H. Prove that

    \[\gcd (a_1 , a_2 , \dots, a_n ) \mathbb{Z} \subseteq H\]

Solution

It is enough to prove it for the n=2 case since we can then reduce it by using the fact that

\gcd(a_1, a_2, \dots, a_n) = \gcd(a_1, a_2, \dots, a_{n-2}, \gcd(a_{n-1}, a_n))

We have that xa_1 + y a_2 \in H for any integers x and y. But by Bezout’s lemma we can find x , y such that

    \[x a_1 + y a_2 = \gcd(a_1, a_2)\]

and hence \gcd(a_1, a_2)\mathbb{Z} \subseteq H.

Read more

On a transcedental number

Prove that the number \arctan \left( \frac{1}{2} \right) is transcedental.

Solution

Let \arctan \left( \frac{1}{2} \right) = \alpha. Then

    \[e^{i \alpha} = \frac{2+i}{\sqrt{5}}\]

which is algebraic.  Hence it follows from Weierstrass РLindemann theorem  that i \alpha , as algebraic, must be transcedental.

The exercise can also be found at mathematica.gr .

Read more