Let $(a_n)_{n\geq 1}$ be a sequence for real numbers given by $a_1=1/2$ and for each positive integer $n$ \[ a_{n+1}=\frac{a_n^2}{a_n^2-a_n+1}. \] Prove that for every positive integer $n$ we have $a_1+a_2+\cdots + a_n<1$.

Click for solution Define $b_n = \frac{1}{a_n}$. Then $b_{n + 1} = b_n^2 - b_n + 1$ or \[\frac{b_{n + 1} - 1}{b_n - 1} = b_n.\] Multiplying these relations (the whole thing telescopes) we get \[b_{n + 1} = b_n\cdots b_2b_1 + 1 \Leftrightarrow \frac{1}{b_n} = \frac{1}{b_1b_2\cdots b_{n - 1}} - \frac{1}{b_1b_2\cdots b_{n}}.\] Telescoping again we get \[\frac{1}{b_1} + \frac{1}{b_2} + \cdots + \frac{1}{b_n} = 1 - \frac{1}{b_1b_2\cdots b_n}\] and we are done.

Let $ABC$ be a triangle with $\angle BAC=60^\circ$. Consider a point $P$ inside the triangle having $PA=1$, $PB=2$ and $PC=3$. Find the maximum possible area of the triangle $ABC$.

Let $n,k$ be positive integers such that $n^k>(k+1)!$ and consider the set \[ M=\{(x_1,x_2,\ldots,x_n)\dvd x_i\in\{1,2,\ldots,n\},\ i=\overline{1,k}\}. \] Prove that if $A\subset M$ has $(k+1)!+1$ elements, then there are two elements $\{\alpha,\beta\}\subset A$, $\alpha=(\alpha_1,\alpha_2,\ldots,\alpha_n)$, $\beta=(\beta_1,\beta_2,\ldots,\beta_n)$ such that \[ (k+1)! \left| (\beta_1-\alpha_1)(\beta_2-\alpha_2)\cdots (\beta_k-\alpha_k) \right. .\]

Prove that among the elements of the sequence $\left\{ \left\lfloor n\sqrt{2003} \right\rfloor \right\}_{n\geq 1}$ one can find a geometric progression having any number of terms, and having the ratio bigger than $k$, where $k$ can be any positive integer. Radu Gologan

Click for solution Fix two positive integers $k,m>1$. Now take some $n$ for which $\{n\sqrt{2003}\}<\frac 1{k^m}$. Now, for each $i\in\overline{1,m-1}$, we have $\lfloor k^{i-1}n\sqrt{2003}\rfloor\le\frac{k^in\sqrt{2003}}k<\lfloor k^{i-1}n\sqrt{2003}\rfloor+\frac 1k$, which, after multiplication with $k$, gives $k\lfloor k^{i-1}n\sqrt{2003}\rfloor\le k^in\sqrt{2003}<k\lfloor k^{i-1}n\sqrt{2003}\rfloor+1\Rightarrow\lfloor k^in\sqrt{2003}\rfloor=k\lfloor k^{i-1}n\sqrt{2003}\rfloor$. This means that the numbers $\lfloor k^in\sqrt{2003}\rfloor,\ i\in\overline{0,m-1}$ are $m$ numbers in geometric progression with ratio $k$.

Let $f\in\mathbb{Z}[X]$ be an irreducible polynomial over the ring of integer polynomials, such that $|f(0)|$ is not a perfect square. Prove that if the leading coefficient of $f$ is 1 (the coefficient of the term having the highest degree in $f$) then $f(X^2)$ is also irreducible in the ring of integer polynomials. Mihai Piticari

Click for solution Let $f(x)=(x-a_1^2)(x-a_2^2)\ldots(x-a_n^2)$, where $a_i$ are complex numbers ($a_i^2$ are all distinct, since they are the roots of an irreducible polynomial). Now assume that $f(x^2)=g_1(x)\cdot\ldots\cdot g_k(x),\ k\ge 2$ is a decomposition of $f(x^2)$ into $>1$ irreducible monic integral polynomials. If for some $i$ there is a $j$ s.t. both $a_j,-a_j$ are roots of $g_i$, then for any $p$ s.t. $a_p$ is a root of $g_i,\ -a_p$ will also be a root of $g_i$. This is because $a_p$ has both $a_j,-a_j$ as conjugates, which means that $-a_p$ also has them as conjugates, so $-a_p$ can't appear as a root in any $g$ except for $g_i$. This means that $g$ is a product of expressions of the form $x^2-a_i^2$, which makes it a factor of $f$, so we get a contradiction. The above implies that if $a_j$ is a root of $g_i$, then $-a_j$ is not. Now, if $g_i$ has the distinct roots $a_{i_1},\ldots,a_{i_t}$, then there is another $g_{i'}$ which has roots $-a_{i_1},\ldots,-a_{i_t}$. The $g$'s thus come in pairs, each two members of the same pair having the same absolute value of the free term. When we multiply all these free terms together, we find that the absolute value of the free term of $f$ is a square, thus getting another contradiction.

At a math contest there are $2n$ students participating. Each of them submits a problem to the jury, which thereafter gives each students one of the $2n$ problems submitted. One says that the contest is fair is there are $n$ participants which receive their problems from the other $n$ participants. Prove that the number of distributions of the problems in order to obtain a fair contest is a perfect square.

Find all integers $a,b,m,n$, with $m>n>1$, for which the polynomial $f(X)=X^n+aX+b$ divides the polynomial $g(X)=X^m+aX+b$. Laurentiu Panaitopol

Two circles $\omega_1$ and $\omega_2$ with radii $r_1$ and $r_2$, $r_2>r_1$, are externally tangent. The line $t_1$ is tangent to the circles $\omega_1$ and $\omega_2$ at points $A$ and $D$ respectively. The parallel line $t_2$ to the line $t_1$ is tangent to the circle $\omega_1$ and intersects the circle $\omega_2$ at points $E$ and $F$. The line $t_3$ passing through $D$ intersects the line $t_2$ and the circle $\omega_2$ in $B$ and $C$ respectively, both different of $E$ and $F$ respectively. Prove that the circumcircle of the triangle $ABC$ is tangent to the line $t_1$. Dinu Serbanescu

Let $n\geq 3$ be a positive integer. Inside a $n\times n$ array there are placed $n^2$ positive numbers with sum $n^3$. Prove that we can find a square $2\times 2$ of 4 elements of the array, having the sides parallel with the sides of the array, and for which the sum of the elements in the square is greater than $3n$. Radu Gologan

Let $\mathcal{P}$ be the set of all primes, and let $M$ be a subset of $\mathcal{P}$, having at least three elements, and such that for any proper subset $A$ of $M$ all of the prime factors of the number $ -1+\prod_{p\in A}p$ are found in $M$. Prove that $M= \mathcal{P}$. Valentin Vornicu

Click for solution If $2\not \in M$, then $A=\{p\}$, with $p\in M$. Because $p-1$ is an even number, it follows that $2\in M$, contradiction, thus $2\in M$. First let us suppose that $M$ is finite. Then let $M$ be $\{2,p_2,\ldots,p_k\}$, $k\geq 3$. Let $A$ be $\{2,p_3,\ldots,p_k\}$, and denote by $P$ the product of all the elements of $M$. Then we have: \[ 2p_3\cdots p_k-1=\frac {P}p_2 -1 = p_2^\alpha \Rightarrow P=p_2^{\alpha+1}+p_2 \ \ \eqno (1) \] and if we consider $A=\{p_3,\ldots,p_k\}$ then we obtain: \[ p_3\cdots p_k-1 = \frac {P}{2p_2} -1 = 2^\beta p_2^\gamma \Rightarrow P=2p_2(2^\beta p_2^\gamma+1) \ \ \eqno (2) \] From $(1)$ and $(2)$ it follows that \[ p_2^{\alpha+1}+p_2 = 2p_2(2^\beta p_2^\gamma+1) \Rightarrow p_2^\alpha +1 = 2^{\beta+1}p_2^\gamma + 2 \Rightarrow 1\equiv 2 \pmod{p_2} \] contradiction, thus indeed $M$ has an infinite number of elements. Suppose now that there is a prime $q$ such that $q\not \in M$. Let $M=\{2,p_2,p_3,\ldots,p_k,\ldots\}$. From the Pigeonhole Principle it follows that from the numbers $2-1,2\cdot p_2-1,\ldots, 2p_2\cdots p_{q+1}-1$ at least two of them have the same residue modulo $q$, let them be $2\cdots p_i-1\equiv 2\cdots p_j-1$, $1\leq i< j\leq q+1$. But then we have \[ 2\cdots p_i(p_{i+1}\cdots p_j-1)\equiv 0 \pmod q \Rightarrow p_{i+1}\cdots p_j-1\equiv 0 \pmod q \Rightarrow q\in M\] which is a contradiction, therefore the supposition was false and $M$ is the set of all primes.

In a square of side 6 the points $A,B,C,D$ are given such that the distance between any two of the four points is at least 5. Prove that $A,B,C,D$ form a convex quadrilateral and its area is greater than 21. Laurentiu Panaitopol

Click for solution First of all we observe that no angle formed with 3 of the 4 points can be greater of equal with $120^\circ$, because otherwise if we suppose that WLOG $\angle ABC\geq 120^\circ$, then from $AB\geq 5$ and $BC\geq 5$ we deduce $AC\geq 5\sqrt 3 >6\sqrt 2$ contradiction. Therefore if the quadrilateral $ABCD$ is not convex, then one of the 4 points lies inside the triangle formed by the other 3. Suppose WLOG that $D\in$int$[ABC]$. But then one of the angles $\angle ADB$, $\angle BDC$ and $\angle CDA$ would be, by the Pigeonhole Principle, greater or equal than $120^\circ$, contradiction. Thus $ABCD$ is a convex quadrilateral. Now because each angle of the triangle $ABC$ is smaller than $120^\circ$ and there is at least one angle, say $\angle ABC$, which is greater than $60^\circ$ it follows that \[ \sin \angle ABC \geq \frac {\sqrt 3}2 \Rightarrow \] \[ \sigma[ABC]=\frac 12 AB\cdot BC\cdot \sin \angle ABC \geq \frac {\sqrt3}4 \cdot 25 > \frac {21}2 \Leftrightarrow 625 > 12 \cdot 49 = 588 \] Analogously one can prove that $\displaystyle \sigma[ACD]\geq \frac {21}2$, and thus $\sigma[ABCD]>21$.

A word is a sequence of n letters of the alphabet {a, b, c, d}. A word is said to be complicated if it contains two consecutive groups of identic letters. The words caab, baba and cababdc, for example, are complicated words, while bacba and dcbdc are not. A word that is not complicated is a simple word. Prove that the numbers of simple words with n letters is greater than $2^n$, if n is a positive integer.

Click for solution Let us denote by $S(n)$ the set of simple words with $n$ letters and by $s_n$ the number of elements in $S(n)$. If we put a letter at the end of each of the simple words from $S(n)$ we obtain a set $T(n+1)$ of $t_{n+1}$ words of length $n+1$, their number being $t_{n+1}=4s_n$. Obviously $S(n+1) \subset T(n+1)$, $S(n+1)\neq T(n+1)$. Let $T_1(n+1)$ be the set of those words from $T(n+1)$ which have the last two letters the same, $T_k(n+1)$ the set of $T(n+1)$ which end in two consecutive identical groups of $k$ letters, for each $k\in\{1,2,\ldots,m\}$, where $m=\displaystyle \left\lfloor \frac { n+1 } 2 \right\rfloor$. Obviously \[ f(n+1)\geq t_{n+1}-|T_1(n+1)|-|T_2(n+1)|-\cdots - |T_m(n+1)|\] We have $t_{n+1}=4f(n)$, $|T_1(n+1)|=f(n)$, and furthermore $|T_k(n+1)|\leq f(n+1-k)$, because of the fact that the mapping of $S(n+1-k)$ into $T_k(n+1)$ given by adding to a simple word of $n+1-k$ letters its own last $k$ letters is obviously surjective. We have $f(1)=4$, $f(2)=12>4$. By induction we want to prove $f(k+1)>2f(k)$. We have \[ f(n+1)\geq 4f(n)-f(n)-\frac 12 f(n) - \frac 14 f(n)- \cdots > 2 f(n) \] from which the conclusion follows.

A parliament has $n$ senators. The senators form 10 parties and 10 committees, such that any senator belongs to exactly one party and one committee. Find the least possible $n$ for which it is possible to label the parties and the committees with numbers from 1 to 10, such that there are at least 11 senators for which the numbers of the corresponding party and committee are equal.

Given is a rhombus $ABCD$ of side 1. On the sides $BC$ and $CD$ we are given the points $M$ and $N$ respectively, such that $MC+CN+MN=2$ and $2\angle MAN = \angle BAD$. Find the measures of the angles of the rhombus. Cristinel Mortici

In a plane we choose a cartesian system of coordinates. A point $A(x,y)$ in the plane is called an integer point if and only if both $x$ and $y$ are integers. An integer point $A$ is called invisible if on the segment $(OA)$ there is at least one integer point. Prove that for each positive integer $n$ there exists a square of side $n$ in which all the interior integer points are invisible.

Click for solution We will prove that for each integer $L > 0$ there exists a square of side-length $L$ with side parallel to the axes of ccordinates such that any point in the interior of the square or on its boundary is invisible. This will lead to the desired result since, for any given $R$, we may choose $L$ sufficientely large so that the square covers a disk with radius $R$. Clearly, the lattice point $M(a,b)$ is invisible if and only if $\gcd (a,b) > 1$. Now, let $L > 0$ be given. Let $p_{i,j}$ be pairwise distinct primes for $i=0, \cdots, L$ and $j = 0 , \cdots , L$. From the chinese remainders theorem, we know that there exists $x,y > 0$ such that $x =- i$ modmath=inline]$p_{i,j}$[/math and $y=-j$ modmath=inline]$p_{i,j}$[/math, for all $i,j$. Then we choose the point $M(x,y)$ to be the lower left corner of our desired square, and wed are done.

Let $ABCDEF$ be a convex hexagon and denote by $A',B',C',D',E',F'$ the middle points of the sides $AB$, $BC$, $CD$, $DE$, $EF$ and $FA$ respectively. Given are the areas of the triangles $ABC'$, $BCD'$, $CDE'$, $DEF'$, $EFA'$ and $FAB'$. Find the area of the hexagon. Kvant Magazine

A permutation $\sigma: \{1,2,\ldots,n\}\to\{1,2,\ldots,n\}$ is called straight if and only if for each integer $k$, $1\leq k\leq n-1$ the following inequality is fulfilled \[ |\sigma(k)-\sigma(k+1)|\leq 2. \] Find the smallest positive integer $n$ for which there exist at least 2003 straight permutations. Valentin Vornicu

Click for solution The main ideea is to look where $n$ is positioned. In that idea let us denote by $x_n$ the number of all the straight permutations and by $a_n$ the number of straight permutations having $n$ on the first or on the last position, i.e. $\sigma(1)=n$ or $\sigma(n)=n$. Also let us denote by $b_n$ the difference $x_n-a_n$ and by $a_n'$ the number of permutations having $n$ on the first position, and by $a_n''$ the number of permutations having $n$ on the last position. From symmetry we have that $2a_n'=2a_n''=a_n'+a_n''=a_n$, for all $n$-s. Therefore finding a recurrence relationship for $\{a_n\}_n$ is equivalent with finding one for $\{a_n'\}_n$. One can simply compute: $a_2'=1$, $a_3'=2$, $a_4'=4$. Suppose that $n\geq 5$. We have two possibilities for the second position: if $\sigma(2)=n-1$ then we must complete the remaining positions with $3,4,\ldots,n$ thus the number of ways in which we can do that is $a_{n-1}'$ (because the permutation $\sigma': \{1,2,\ldots, n-1\}\to\{1,2,\ldots,n-1\}$, $\sigma'(k)=\sigma(k+1)$, for all $k$, $1\leq k\leq n-1$, is also a straight permutation). If on the second position we have $n-2$, $\sigma(2)=n-2$, then $n-1$ can only be in the last position of the permutation or on the third position, i.e. $\sigma(3)=n-1$ or $\sigma(n)=n-1$. If $\sigma(n)=n-1$, then we can only have $\sigma(n-1)=n-3$ thus $\sigma(3)=n-4$ and so on, thus there is only one permutation of this kind. On the other hand, if $\sigma(3)=n-1$ then it follows that $\sigma(4)=n-3$ and now we can complete the permutation in $a_{n-3}'$ ways (because the permutation $\sigma': \{1,2,\ldots, n-3\}\to\{1,2,\ldots,n-3\}$, $\sigma'(k)=\sigma(k+3)$, for all $k$, $1\leq k\leq n-3$, is also a straight permutation). Summing all up we get the recurrence: \[ a_n'=a_{n-1}'+1+a_{n-3}' \Rightarrow a_n=a_{n-1}+a_{n-3}+2,\ \forall \ n\geq 5. \eqno(1) \] The recurrence relationship for $\{b_n\}$ can be obtained by observing that for each straight permutation \break $\tau: \{1,2,\ldots,n+1\}\to\{1,2,\ldots,n+1\}$ for which $2\leq \tau^{-1}(n+1)\leq n$ we can obtain a straight permutation $\sigma: \{1,2,\ldots,n\}\to\{1,2,\ldots,n\}$ by removing $n+1$. Indeed $n+1$ is "surrounded" by $n$ and $n-1$, so by removing it, $n$ and $n-1$ become neighbors, and thus the newly formed permutation is indeed straight. Now, if $\tau^{-1}n\in\{1,n+1\}$ then the newly formed permutation $\sigma$ was counted as one of the $a_{n}$-s, minus the two special cases in which $n$ and $n-1$ are on the first and last positions, and also minus the permutations which begin or end with a sequence of the form $n..n-2..n-1..n-3...$ thus $n$ and $n-1$ not being neighbors. If $\tau^{-1}(n)\nin\{1,n+1\}$ then certainly $\sigma$ was counted with the $b_n$-s. Also, from any straight permutation of $n$ elements, not having $n$ and $n-1$ in the first and last position, thus $n$ certainly being neighbor with $n-1$, we can make a straight $n+1$-element permutation by inserting $n+1$ between $n$ and $n-1$. Therefore we have obtained the following relationship: \[ b_{n+1} = a_n - 2-a_{n-3} +b_n = a_{n-1}+b_n ,\ \forall \ n\geq 4 \ \Rightarrow \] \[ b_n= a_{n-2}+a_{n-3}+\cdots + a_2 + b_3 \Rightarrow x_n = a_n + a_{n-2}+a_{n-3}+\ldots + a_2 + b_3, \ \forall \ n\geq4. \] It is obvious that $\{x_n\}_n$ is a "fast" increasing sequence, so it is easy to compute the first terms using the relationships obtained above, which will prove that the number that we are looking for is $n=16$.

For every positive integer $n$ we denote by $d(n)$ the sum of its digits in the decimal representation. Prove that for each positive integer $k$ there exists a positive integer $m$ such that the equation $x+d(x)=m$ has exactly $k$ solutions in the set of positive integers.