### Archive

Archive for the ‘Algebra’ Category

## SEEMOUS 2018 – Problems

Problem 1. Let ${f:[0,1] \rightarrow (0,1)}$ be a Riemann integrable function. Show that

$\displaystyle \frac{\displaystyle 2\int_0^1 xf^2(x) dx }{\displaystyle \int_0^1 (f^2(x)+1)dx }< \frac{\displaystyle \int_0^1 f^2(x) dx}{\displaystyle \int_0^1 f(x)dx}.$

Problem 2. Let ${m,n,p,q \geq 1}$ and let the matrices ${A \in \mathcal M_{m,n}(\Bbb{R})}$, ${B \in \mathcal M_{n,p}(\Bbb{R})}$, ${C \in \mathcal M_{p,q}(\Bbb{R})}$, ${D \in \mathcal M_{q,m}(\Bbb{R})}$ be such that

$\displaystyle A^t = BCD,\ B^t = CDA,\ C^t = DAB,\ D^t = ABC.$

Prove that ${(ABCD)^2 = ABCD}$.

Problem 3. Let ${A,B \in \mathcal M_{2018}(\Bbb{R})}$ such that ${AB = BA}$ and ${A^{2018} = B^{2018} = I}$, where ${I}$ is the identity matrix. Prove that if ${\text{tr}(AB) = 2018}$ then ${\text{tr}(A) = \text{tr}(B)}$.

Problem 4. (a) Let ${f: \Bbb{R} \rightarrow \Bbb{R}}$ be a polynomial function. Prove that

$\displaystyle \int_0^\infty e^{-x} f(x) dx = f(0)+f'(0)+f''(0)+...$

(b) Let ${f}$ be a function which has a Taylor series expansion at ${0}$ with radius of convergence ${R=\infty}$. Prove that if ${\displaystyle \sum_{n=0}^\infty f^{(n)}(0)}$ converges absolutely then ${\displaystyle \int_0^{\infty} e^{-x} f(x)dx}$ converges and

$\displaystyle \sum_{n=0}^\infty f^{(n)}(0) = \int_0^\infty e^{-x} f(x).$

Hints: 1. Just use $2f(x) \leq f^2(x)+1$ and $xf^2(x) < f^2(x)$. The strict inequality comes from the fact that the Riemann integral of strictly positive function cannot be equal to zero. This problem was too simple…

2. Use the fact that $ABCD = AA^t$, therefore $ABCD$ is symmetric and positive definite. Next, notice that $(ABCD)^3 = ABCDABCDABCD = D^tC^tB^tA^t = (ABCD)^t = ABCD$. Notice that $ABCD$ is diagonalizable and has eigenvalues among $-1,0,1$. Since it is also positive definite, $-1$ cannot be an eigenvalue. This allows to conclude.

3. First note that the commutativity allows us to diagonalize $A,B$ using the same basis. Next, note that $A,B$ both have eigenvalues of modulus one. Then the trace of $AB$ is simply the sum $\sum \lambda_i\mu_i$ where $\lambda_i,\mu_i$ are eigenvalues of $A$ and $B$, respectively. The fact that the trace equals $2018$ and the triangle inequality shows that eigenvalues of $A$ are a multiple of eigenvalues of $B$. Finish by observing that they have the same eigenvalues.

4. (a) Integrate by parts and use a recurrence. (b) Use (a) and the approximation of a continuous function by polynomials on compacts to conclude.

I’m not sure about what others think, but the problems of this year seemed a bit too straightforward.

## Putnam 2017 A2 – Solution

Problem A2. We have the following recurrence relation

$\displaystyle Q_n = \frac{Q_{n-1}^2-1}{Q_{n-2}},$

for ${n \geq 2}$, given ${Q_0=1}$ and ${Q_1=x}$. In order to prove that ${Q_n}$ is always a polynomial with integer coefficients we should prove that ${Q_{n-2}}$ divides ${Q_{n-1}^2-1}$ somehow. Recurrence does not seem to work very well. Also, root based arguments might work, but you need to take good care in the computation.

A simpler idea, which is classic in this context, is to try and linearize the recurrence relation. In order to do this, let’s write two consecutive recurrence relations

$\displaystyle Q_nQ_{n-2} +1 = Q_{n-1}^2$

$\displaystyle Q_n^2 = Q_{n+1}Q_{n-1}+1$

We add them and we obtain the following relation

$\displaystyle \frac{Q_n}{Q_{n-1}} = \frac{Q_{n+1}+Q_{n-1}}{Q_n+Q_{n-2}},$

which leads straightforward to a telescoping argument. Finally, we are left with a simple linear recurrence with integer coefficient polynomials, and the result follows immediately.

## Balkan Mathematical Olympiad 2017 – Problems

Problem 1. Find all ordered pairs of positive integers ${ (x, y)}$ such that:

$\displaystyle x^3+y^3=x^2+42xy+y^2.$

Problem 2. Consider an acute-angled triangle ${ABC}$ with ${AB and let ${\omega}$ be its circumscribed circle. Let ${t_B}$ and ${t_C}$ be the tangents to the circle ${\omega}$ at points ${B}$ and ${C}$, respectively, and let ${L}$ be their intersection. The straight line passing through the point ${B}$ and parallel to ${AC}$ intersects ${t_C}$ in point ${D}$. The straight line passing through the point ${C}$ and parallel to ${AB}$ intersects ${t_B}$ in point ${E}$. The circumcircle of the triangle ${BDC}$ intersects ${AC}$ in ${T}$, where ${T}$ is located between ${A}$ and ${C}$. The circumcircle of the triangle ${BEC}$ intersects the line ${AB}$ (or its extension) in ${S}$, where ${B}$ is located between ${S}$ and ${A}$.

Prove that ${ST}$, ${AL}$, and ${BC}$ are concurrent.

Problem 3. Let ${\mathbb{N}}$ denote the set of positive integers. Find all functions ${f:\mathbb{N}\longrightarrow\mathbb{N}}$ such that

$\displaystyle n+f(m)\mid f(n)+nf(m)$

for all ${m,n\in \mathbb{N}}$

Problem 4. On a circular table sit ${\displaystyle {n> 2}}$ students. First, each student has just one candy. At each step, each student chooses one of the following actions:

• (A) Gives a candy to the student sitting on his left or to the student sitting on his right.
• (B) Separates all its candies in two, possibly empty, sets and gives one set to the student sitting on his left and the other to the student sitting on his right.

At each step, students perform the actions they have chosen at the same time. A distribution of candy is called legitimate if it can occur after a finite number of steps. Find the number of legitimate distributions.

(Two distributions are different if there is a student who has a different number of candy in each of these distributions.)

Source: AoPS

## IMC 2016 – Day 2 – Problem 8

Problem 8. Let ${n}$ be a positive integer and denote by ${\Bbb{Z}_n}$ the ring of integers modulo ${n}$. Suppose that there exists a function ${f:\Bbb{Z}_n \rightarrow \Bbb{Z}_n}$ satisfying the following three properties:

• (i) ${f(x) \neq x}$,
• (ii) ${x = f(f(x))}$,
• (iii) ${f(f(f(x+1)+1)+1) = x}$ for all ${x \in \Bbb{Z}_n}$.

Prove that ${n \equiv 2}$ modulo ${4}$.

## IMC 2016 – Day 1 – Problem 2

Problem 2. Let ${k}$ and ${n}$ be positive integers. A sequence ${(A_1,...,A_k)}$ of ${n\times n}$ matrices is preferred by Ivan the Confessor if ${A_i^2 \neq 0}$ for ${1\leq i \leq k}$, but ${A_iA_j = 0}$ for ${1\leq i,j \leq k}$ with ${i \neq j}$. Show that if ${k \leq n}$ in al preferred sequences and give an example of a preferred sequence with ${k=n}$ for each ${n}$.

## Balkan Mathematical Olympiad – 2016 Problems

Problem 1. Find all injective functions ${f: \mathbb R \rightarrow \mathbb R}$ such that for every real number ${x}$ and every positive integer ${n}$,

$\displaystyle \left|\sum_{i=1}^n i\left(f(x+i+1)-f(f(x+i))\right)\right|<2016$

Problem 2. Let ${ABCD}$ be a cyclic quadrilateral with ${AB. The diagonals intersect at the point ${F}$ and lines ${AD}$ and ${BC}$ intersect at the point ${E}$. Let ${K}$ and ${L}$ be the orthogonal projections of ${F}$ onto lines ${AD}$ and ${BC}$ respectively, and let ${M}$, ${S}$ and ${T}$ be the midpoints of ${EF}$, ${CF}$ and ${DF}$ respectively. Prove that the second intersection point of the circumcircles of triangles ${MKT}$ and ${MLS}$ lies on the segment ${CD}$.

Problem 3. Find all monic polynomials ${f}$ with integer coefficients satisfying the following condition: there exists a positive integer ${N}$ such that ${p}$ divides ${2(f(p)!)+1}$ for every prime ${p>N}$ for which ${f(p)}$ is a positive integer.

Problem 4. The plane is divided into squares by two sets of parallel lines, forming an infinite grid. Each unit square is coloured with one of ${1201}$ colours so that no rectangle with perimeter ${100}$ contains two squares of the same colour. Show that no rectangle of size ${1\times1201}$ or ${1201\times1}$ contains two squares of the same colour.

## SEEMOUS 2016 – Problems

Problem 1. Let ${f}$ be a continuous and decreasing real valued function defined on ${[0,\pi/2]}$. Prove that

$\displaystyle \int_{\pi/2-1}^{\pi/2} f(x)dx \leq \int_0^{\pi/2} f(x)\cos x dx \leq \int_0^1 f(x) dx.$

When do we have equality?

Problem 2. a) Prove that for every matrix ${X \in \mathcal{M}_2(\Bbb{C})}$ there exists a matrix ${Y \in \mathcal{M}_2(\Bbb{C})}$ such that ${Y^3 = X^2}$.

b) Prove that there exists a matrix ${A \in \mathcal{M}_3(\Bbb{C})}$ such that ${Z^3 \neq A^2}$ for all ${Z \in \mathcal{M}_3(\Bbb{C})}$.

Problem 3. Let ${A_1,A_2,...,A_k}$ be idempotent matrices (${A_i^2 = A_i}$) in ${\mathcal{M}_n(\Bbb{R})}$. Prove that

$\displaystyle \sum_{i=1}^k N(A_i) \geq \text{rank} \left(I-\prod_{i=1}^k A_i\right),$

where ${N(A_i) = n-\text{rank}(A_i)}$ and ${\mathcal{M}_n(\Bbb{R})}$ is the set of ${n \times n}$ matrices with real entries.

Problem 4. Let ${n \geq 1}$ be an integer and set

$\displaystyle I_n = \int_0^\infty \frac{\arctan x}{(1+x^2)^n}dx.$

Prove that

a) ${\displaystyle \sum_{i=1}^\infty \frac{I_n}{n} =\frac{\pi^2}{6}.}$

b) ${\displaystyle \int_0^\infty \arctan x \cdot \ln \left( 1+\frac{1}{x^2}\right) dx = \frac{\pi^2}{6}}$.

Some hints follow.