Archive

Posts Tagged ‘olympiad’

IMO 2018 Problems – Day 1

July 9, 2018 Leave a comment

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.

Advertisements

Balkan Mathematical Olympiad 2018

June 23, 2018 Leave a comment

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

Source: https://bmo2018.dms.rs/wp-content/uploads/2018/05/BMOproblems2018_English.pdf

Romanian Masters in Mathematics contest – 2018

March 9, 2018 Leave a comment

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

March 1, 2018 Leave a comment

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

Source: official site of SEEMOUS 2018 

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

December 4, 2017 Leave a comment

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.

IMC 2017 – Day 2 – Problems

August 3, 2017 Leave a comment

Problem 6. Let {f: [0,\infty) \rightarrow \Bbb{R}} be a continuous function such that {\lim_{x \rightarrow \infty}f(x) = L} exists (finite or infinite).

Prove that

\displaystyle \lim_{n \rightarrow \infty} \int_0^1 f(nx) dx = L.

Problem 7. Let {p(x)} be a nonconstant polynomial with real coefficients. For every positive integer {n} let

\displaystyle q_n(x) = (x+1)^n p(x)+x^n p(x+1).

Prove that there are only finitely many numbers {n} such that all roots of {q_n(x)} are real.

Problem 8. Define the sequence {A_1,A_2,...} of matrices by the following recurrence

\displaystyle A_1 = \begin{pmatrix} 0& 1 \\ 1& 0 \end{pmatrix}, \ A_{n+1} = \begin{pmatrix} A_n & I_{2^n} \\ I_{2^n} & A_n \end{pmatrix} \ \ (n=1,2,...)

where {I_m} is the {m\times m} identity matrix.

Prove that {A_n} has {n+1} distinct integer eigenvalues {\lambda_0<\lambda_1<...<\lambda_n} with multiplicities {{n \choose 0},\ {n\choose 1},...,{n \choose n}}, respectively.

Problem 9. Define the sequence {f_1,f_2,... : [0,1) \rightarrow \Bbb{R}} of continuously differentiable functions by the following recurrence

\displaystyle f_1 = 1; f'_{n+1} = f_nf_{n+1} \text{ on } (0,1) \text{ and } f_{n+1}(0)=1.

Show that {\lim_{n\rightarrow \infty}f_n(x)} exists for every {x \in [0,1)} and determine the limit function.

Problem 10. Let {K} be an equilateral triangle in the plane. Prove that for every {p>0} there exists an {\varepsilon >0} with the following property: If {n} is a positive integer and {T_1,...,T_n} are non-overlapping triangles inside {K} such that each of them is homothetic to {K} with a negative ratio and

\displaystyle \sum_{\ell =1}^n \text{area}(T_\ell) > \text{area} (K)-\varepsilon,

then

\displaystyle \sum_{\ell =1}^n \text{perimeter} (T_\ell) > p.

Balkan Mathematical Olympiad 2017 – Problems

May 10, 2017 Leave a comment

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<AC} 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

%d bloggers like this: