### Archive

Archive for the ‘Problem Solving’ 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

## IMO 2018 Problems – Day 1

Problem 1. Let ${\Gamma}$ be the circumcircle of acute triangle ${ABC}$. Points ${D}$ and ${E}$ are on segments ${AB}$ and ${AC}$ respectively such that ${AD = AE}$. The perpendicular bisectors of ${BD}$ and ${CE}$ intersect minor arcs ${AB}$ and ${AC}$ of ${\Gamma}$ at points ${F}$ and ${G}$ respectively. Prove that lines ${DE}$ and ${FG}$ are either parallel or they are the same line.

Problem 2. Find all integers ${n \geq 3}$ for which there exist real numbers ${a_1, a_2, \dots a_{n + 2}}$ satisfying ${a_{n + 1} = a_1}$, ${a_{n + 2} = a_2}$ and

$\displaystyle a_ia_{i + 1} + 1 = a_{i + 2}$

For ${i = 1, 2, \dots, n}$.

Problem 3. An anti-Pascal triangle is an equilateral triangular array of numbers such that, except for the numbers in the bottom row, each number is the absolute value of the difference of the two numbers immediately below it. For example, the following is an anti-Pascal triangle with four rows which contains every integer from ${1}$ to ${10}$

$\displaystyle 4$

$\displaystyle 2\quad 6$

$\displaystyle 5\quad 7 \quad 1$

$\displaystyle 8\quad 3 \quad 10 \quad 9$

Does there exist an anti-Pascal triangle with ${2018}$ rows which contains every integer from ${1}$ to ${1 + 2 + 3 + \dots + 2018}$?

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

## Sum of the Euler Totient function

Given a positive integer ${n}$, the Euler totient function ${\varphi(n)}$ is defined as the number of positive integers less than ${n}$ which are co-prime with ${n}$ (i.e. they have no common factors with ${n}$). There are formulas for computing ${\varphi(n)}$ starting from the factorization of ${n}$. One such formula is

$\displaystyle \varphi(n) = n \prod_{p|n} \left(1-\frac{1}{p}\right),$

where the product is made over all primes dividing ${n}$.

If you have to compute ${\varphi(n)}$ for all numbers less than a threshold then another property could be useful: ${\varphi}$ is arithmetic, that is, ${\varphi(mn) = \varphi(m)\varphi(n)}$ whenever ${\gcd(m,n)=1}$. Therefore you could store all values computed until ${k}$ and for computing the value ${\varphi(k+1)}$ there are two possibilities: ${k+1=p^\alpha}$ is a prime power and then ${\varphi(k+1) = p^{\alpha}-p^{\alpha-1}}$ or ${k+1}$ is composite and ${k+1 = mn}$ with ${m,n\leq k,\ \gcd(m,n)=1}$. Then use the stored values to compute ${\varphi(k+1)=\varphi(m)\varphi(n)}$.

I now come to the main point of this post: computing the sum of all values of the totient function up to a certain ${N}$:

$\displaystyle \text{Compute } S(N) = \sum_{i=1}^N \varphi(i).$

One approach is to compute each ${\varphi(i)}$ and sum them. I will call this the brute-force approach. For all numerical purposes I will use Pari-GP in this post. On my computer it takes less than a second to compute ${S(10^6)}$ and about ${12}$ seconds to compute ${S(10^7)}$. This is super linear in time, since the algorithm computes the factorization for each ${n}$ and then sums the values. Using the sieve approach could improve the timing a bit, but the algorithm is still super linear.

In some Project Euler problems it is not uncommon to have to compute something like ${S(10^{11})}$ or even larger. Therefore, there must be more efficient ways to compute ${S(N)}$ out there, so let’s study some of the properties of ${S(N)}$. In another post I dealt with the acceleration of the computation of the sum of the divisor function.

We have ${S(N) = \sum_{i=1}^N \varphi(i)}$ which is the number of pairs ${(a,b)}$ with ${1\leq a\leq b \leq N}$ such that ${\gcd(a,b) =1}$. It is not difficult to see that the total number of such pairs is ${n(n+1)/2}$. Moreover, the possible values of ${\gcd(a,b)}$ are ${1,2,...,N}$. Now, if for ${m \leq N}$ we search instead for pairs satisfying ${\gcd(a,b)=m}$ then we have ${a = ma',\ b = mb'}$ with ${\gcd(a',b')=1}$ and we get

$\displaystyle 1 \leq a' \leq b' \leq N/m,\ \gcd(a',b')=1.$

There fore the number of pairs with gcd equal to ${m}$ is ${S(\lfloor N/m\rfloor )}$. Now we arrive at an interesting recursive formula:

$\displaystyle S(N) = \frac{n(n+1)}{2} - \sum_{m=2}^N S(\lfloor N/m \rfloor ).$

At a first sight this looks more complicated, but there is a trick to keep in mind whenever you see a summation over ${m}$ of terms of the form ${\lfloor N/m \rfloor}$: these quantities are constant on large intervals. Indeed,

$\displaystyle \lfloor N/m \rfloor = d \Leftrightarrow md \leq N < m(d+1)\Leftrightarrow N/(d+1)

Therefore we can change the index of summation from ${m}$ to ${d=\lfloor N/m \rfloor}$. The range of ${d}$ for which the interval ${I_d = [N/(d+1),N/d]}$ contains more than one integer is of order ${\sqrt(N)}$. Indeed, ${N/d-N/(d+1) = N/(d(d+1))}$. Therefore for ${d\leq \sqrt(N)}$ we should have at least one integer in the interval ${I_d}$. The part where ${d}$ is larger than ${\sqrt{N}}$ corresponds to ${m}$ smaller than ${\sqrt{N}}$. Therefore, we can split ${S(N)}$ into two sums, each of order ${\sqrt{N}}$. and get that

$\displaystyle S(N) = \frac{n(n+1)}{2}- \sum_{m=2}^{\sqrt{N}} S(\lfloor N/m \rfloor)-\sum_{d=1}^{\sqrt{N}}\left(\lfloor N/d \rfloor-\lfloor N/(d+1)\rfloor\right)S(d),$

where in the last sum we must make sure that ${d \neq \lfloor N/d \rfloor}$ in order to avoid duplicating terms in the sum.

Therefore we replaced a sum until ${N}$ to two sums with upper bound ${\sqrt{N}}$. The complexity is not ${\sqrt{N}}$, but something like ${N^{2/3}}$ since we have a recursive computation. Nevertheless, with this new formula and using memoization, to keep track of the values of ${S}$ already computed, we can compute ${S(N)}$ very fast:

${S(10^6) = 303963552392}$ is computed instantly (vs ${1}$ second with brute force)

${S(10^7) = 30396356427242}$ takes ${1}$ second (vs ${12}$ seconds with brute force)

${S(10^8)}$ takes ${5}$ seconds (vs over ${3}$ minutes with brute force)

${S(10^9)}$ takes ${30}$ seconds

${S(10^{11})}$ takes about ${12}$ minutes

etc. Recall that these computations are done in Pari GP, which is not too fast. If you use C++ you can compute ${S(10^8)}$ in ${0.2}$ seconds, ${S(10^9)}$ in ${1}$ second and ${S(10^{10})}$ in ${6}$ seconds and ${S(10^{11})}$ in under a minute, if you manage to get past overflow errors.

Categories: Number theory, Programming

## Spherical triangles of area Pi

Recently I stumbled upon this page and found out a very nice result:

If a spherical triangle has area $\pi$ then four copies of it can tile the sphere.

Here we are talking about triangles on the unit sphere whose edges are geodesics. The above result is a simple consequence of the following facts:

1. If a spherical triangle has angles $\alpha,\beta,\gamma$ then its area is $\alpha+\beta+\gamma-\pi$. Therefore if a triangle has area $\pi$, then $\alpha+\beta+\gamma = 2\pi$.
2. If $ABC$ is a triangle of area $\pi$ and $D$ is obtained by symmetrizing $A$ with respect to the midpoint of $BC$ on the sphere, then $DCB$ and $ABC$ are congruent triangles.
3. Using angles and the fact that on the sphere similar triangles are congruent, we obtain that the triangles $ABC,BCD,CDA,DAC$ are all congruent.

Here are a few examples of such partitions:

Categories: Combinatorics, Geometry

## Romanian Masters in Mathematics contest – 2018

Problem 1. Let ${ABCD}$ be a cyclic quadrilateral an let ${P}$ be a point on the side ${AB.}$ The diagonals ${AC}$ meets the segments ${DP}$ at ${Q.}$ The line through ${P}$ parallel to ${CD}$ mmets the extension of the side ${CB}$ beyond ${B}$ at ${K.}$ The line through ${Q}$ parallel to ${BD}$ meets the extension of the side ${CB}$ beyond ${B}$ at ${L.}$ Prove that the circumcircles of the triangles ${BKP}$ and ${CLQ}$ are tangent .

Problem 2. Determine whether there exist non-constant polynomials ${P(x)}$ and ${Q(x)}$ with real coefficients satisfying

$\displaystyle P(x)^{10}+P(x)^9 = Q(x)^{21}+Q(x)^{20}.$

Problem 3. Ann and Bob play a game on the edges of an infinite square grid, playing in turns. Ann plays the first move. A move consists of orienting any edge that has not yet been given an orientation. Bob wins if at any point a cycle has been created. Does Bob have a winning strategy?

Problem 4. Let ${a,b,c,d}$ be positive integers such that ${ad \neq bc}$ and ${gcd(a,b,c,d)=1}$. Let ${S}$ be the set of values attained by ${\gcd(an+b,cn+d)}$ as ${n}$ runs through the positive integers. Show that ${S}$ is the set of all positive divisors of some positive integer.

Problem 5. Let ${n}$ be positive integer and fix ${2n}$ distinct points on a circle. Determine the number of ways to connect the points with ${n}$ arrows (oriented line segments) such that all of the following conditions hold:

• each of the ${2n}$ points is a startpoint or endpoint of an arrow;
• no two arrows intersect;
• there are no two arrows ${\overrightarrow{AB}}$ and ${\overrightarrow{CD}}$ such that ${A}$, ${B}$, ${C}$ and ${D}$ appear in clockwise order around the circle (not necessarily consecutively).

Problem 6. Fix a circle ${\Gamma}$, a line ${\ell}$ to tangent ${\Gamma}$, and another circle ${\Omega}$ disjoint from ${\ell}$ such that ${\Gamma}$ and ${\Omega}$ lie on opposite sides of ${\ell}$. The tangents to ${\Gamma}$ from a variable point ${X}$ on ${\Omega}$ meet ${\ell}$ at ${Y}$ and ${Z}$. Prove that, as ${X}$ varies over ${\Omega}$, the circumcircle of ${XYZ}$ is tangent to two fixed circles.

Source: Art of Problem Solving forums

Some quick ideas: For Problem 1 just consider the intersection of the circle ${(BKP)}$ with the circle ${(ABCD)}$. You’ll notice immediately that this point belongs to the circle ${(CLQ)}$. Furthermore, there is a common tangent to the two circles at this point.

For Problem 2 we have ${10\deg P = 21 \deg Q}$. Eliminate the highest order term from both sides and look at the next one to get a contradiction.

Problem 4 becomes easy after noticing that if ${q}$ divides ${an+b}$ and ${cn+d}$ then ${q}$ divides ${ad-bc}$.

In Problem 5 try to prove that the choice of start points determines that of the endpoints. Then you have a simple combinatorial proof.

Problem 6 is interesting and official solutions use inversions. Those are quite nice, but it may be worthwhile to understand what happens in the non-inverted configuration.

I will come back to some of these problems in some future posts.

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