### Archive

Archive for the ‘Algebra’ Category

## IMO 2018 Problems – Day 2

Problem 4. A site is any point ${(x, y)}$ in the plane such that ${x}$ and ${y}$ are both positive integers less than or equal to 20.

Initially, each of the 400 sites is unoccupied. Amy and Ben take turns placing stones with Amy going first. On her turn, Amy places a new red stone on an unoccupied site such that the distance between any two sites occupied by red stones is not equal to ${\sqrt{5}}$. On his turn, Ben places a new blue stone on any unoccupied site. (A site occupied by a blue stone is allowed to be at any distance from any other occupied site.) They stop as soon as a player cannot place a stone.

Find the greatest ${K}$ such that Amy can ensure that she places at least ${K}$ red stones, no matter how Ben places his blue stones.

Problem 5. Let ${a_1,a_2,\ldots}$ be an infinite sequence of positive integers. Suppose that there is an integer ${N > 1}$ such that, for each ${n \geq N}$, the number

$\displaystyle \frac{a_1}{a_2} + \frac{a_2}{a_3} + \ldots + \frac{a_{n-1}}{a_n} + \frac{a_n}{a_1}$

is an integer. Prove that there is a positive integer ${M}$ such that ${a_m = a_{m+1}}$ for all ${m \geq M}$.

Problem 6. A convex quadrilateral ${ABCD}$ satisfies ${AB\cdot CD = BC\cdot DA}$. Point ${X}$ lies inside ${ABCD}$ so that ${\angle{XAB} = \angle{XCD}}$ and ${\angle{XBC} = \angle{XDA}}$. Prove that ${\angle{BXA} + \angle{DXC} = 180}$.

Source: AoPS

Problem 1. A quadrilateral ${ABCD}$ is inscribed in a circle ${k}$, where ${AB>CD}$ and ${AB}$ is not parallel to ${CD}$. Point ${M}$ is the intersection of the diagonals ${AC}$ and ${BD}$ and the perpendicular from ${M}$ to ${AB}$ intersects the segment ${AB}$ at the point ${E}$. If ${EM}$ bisects the angle ${CED}$, prove that ${AB}$ is a diameter of the circle ${k}$.

Problem 2. Let ${q}$ be a positive rational number. Two ants are initially at the same point ${X}$ in the plane. In the ${n}$-th minute ${(n=1,2,...)}$ each of them chooses whether to walk due north, east, south or west and then walks the distance of ${q^n}$ meters. After a whole number of minutes, they are at the same point in the plane (non necessarily ${X}$), but have not taken exactly the same route within that time. Determine all the possible values of ${q}$.

Problem 3. Alice and Bob play the following game: They start with two non-empty piles of coins. Taking turns, with Alice playing first, each player chooses a pile with an even number of coins and moves half of the coins of this pile to the other pile. The came ends if a player cannot move, in which case the other player wins.

Determine all pairs ${(a,b)}$ of positive integers such that if initially the two piles have ${a}$ and ${b}$ coins, respectively, then Bob has a winning strategy.

Problem 4. Find all primes ${p}$ and ${q}$ such that ${3p^{q-1}+1}$ divides ${11^q+17^p}$.

## When is arccos a rational multiple of pi?

Recently I had to test if the ${\arccos}$ of some algebraic number is a rational multiple of ${\pi}$ or not. I found this solution online and since it is quite nice, I write it here in a more generalized form.

Suppose that ${r}$ is an algebraic number. Under which circumstances we have

$\displaystyle \arccos(r) \in \pi\Bbb{Q}?$

Suppose that ${\arccos(r) = \frac{p}{q} \pi}$ with ${p,q \in \Bbb{Z}, q > 0}$. Then ${q\arccos(r) = p\pi}$ and applying ${\cos}$ we see that

$\displaystyle \cos(q\arccos(r)) -(-1)^p = 0.$

It is well known that the function ${P_q\ :\ x \mapsto \cos(q\arccos(x))}$ is polynomial for ${|x|\leq 1}$. If we denote ${f(x) = P_q(x)-(-1)^p}$ then ${f}$ is a polynomial of degree ${q}$ with leading coefficient ${2^{q-1}}$. Since we have ${f(r) = 0}$, the minimal polynomial ${Q_r}$ associated to ${r}$ must divide ${f(r)}$. This gives us the following necessary condition:

If ${\arccos(r) \in \pi\Bbb{Q}}$ then there exist ${p,q \in \Bbb{Z}}$, ${q > 0}$ such that ${Q_r}$ (the minimal polynomial of ${r}$) divides ${P_q\pm 1}$ (where ${P_q}$ is the Chebyshev polynomial of degree ${q}$).

It is not difficult to see that this condition is also sufficient. Now, using this we have the following application:

Consequence. If ${r}$ is an algebraic number whose minimal polynomial has a leading coefficient which is not a power of ${2}$, then

$\displaystyle \arccos(r) \notin \pi \Bbb{Q}.$

Since the minimal polynomial ${Q_r}$ has a leading coefficient which is not a power of ${2}$, it cannot divide ${P_q\pm 1}$ for some positive integer ${q}$. Therefore, following the arguments stated above, ${\arccos(r) \notin \pi\Bbb{Q}}$.

Applications.

• ${\arccos(\sqrt{n}/3)\notin \pi\Bbb{Q}}$ if ${\gcd(n,3) \leq 3}$.
• ${\arccos(\sqrt{m/n}) \notin \pi\Bbb{Q}}$ for ${m,n \in \Bbb{N}^*}$ if ${n>1},\ \gcd(m,n)=1$ and ${n}$ is not a power of ${2}$.
Categories: Algebra

## 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}$.