Archive

Posts Tagged ‘olympiad’

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

IMC 2016 Problems – Day 2

July 28, 2016 Leave a comment

Problem 6. Let {(x_1,x_2,...)} be a sequence of positive real numbers satisfying {\displaystyle \sum_{n=1}^\infty \frac{x_n}{2n-1}=1}. Prove that

\displaystyle \sum_{k=1}^\infty \sum_{n=1}^k \frac{x_n}{k^2} \leq 2.

Problem 7. Today, Ivan the Confessor prefers continuous functions {f:[0,1]\rightarrow \Bbb{R}} satisfying {f(x)+f(y) \geq |x-y|} for all {x,y \in [0,1]}. Fin the minimum of {\int_0^1 f} over all preferred functions.

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) {f(f(x))=x},
  • (iii) {f(f(f(x+1)+1)+1) = x} for all {x \in \Bbb{Z}_n}.

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

Problem 9. Let {k} be a positive integer. For each nonnegative integer {n} let {f(n)} be the number of solutions {(x_1,...,x_k) \in \Bbb{Z}^k} of the inequality {|x_1|+...+|x_k| \leq n}. Prove that for every {n \geq 1} we have {f(n-1)f(n+1) \leq f(n)^2}.

Problem 10. Let {A} be a {n \times n} complex matrix whose eigenvalues have absolute value at most {1}. Prove that

\displaystyle \|A^n\| \leq \frac{n}{\ln 2} \|A\|^{n-1}.

(Here {\|B\| = \sup_{\|x\|\leq 1} \|Bx\|} for every {n \times n} matrix {B} and {\|x\| = \sqrt{\sum_{i=1}^n |x_i|^2 }} for every complex vector {x \in \Bbb{C}^n}.)

Official source and more infos here.

Categories: Olympiad, Uncategorized Tags: , ,

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<CD}. 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 Problem 4 – Solution

March 6, 2016 3 comments

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

Read more…

ICPC 2015 World Final Problem B

May 21, 2015 Leave a comment

This the the solution to Problem B from the International Collegiate Programming Contest. The list of problems can be found here. The idea is to find the maximal area of the intersection of two moving polygons. The inputs give the initial positions of two convex polygons and the vectors giving their speed in the plane.

One idea of a solution is as follows: take a maximal time {T} and a discretization of the interval {[0,T]} by dividing it into {N} parts. Iterate over the translations at times given by this discretization, compute at each step the area of the intersection of the two polygons (if there is any intersection at all), and in the end find the time {t_0} for which this area is maximized. Now, even if the discretization step {T/N} is large (greater than the demanded precision of {10^{-3}}), we can conclude that {t_0} is an approximation of the final time with an error smaller than {T/N}. This is due to the fact that the function representing the area of the intersection has two monotonicity intervals, as a consequence of the fact that the polygons are convex. On the first interval, the intersection area is increasing, on the second one it is decreasing. Thus, once we have a discrete maximum, we are close to the real maximum.

Now, all we are left to do in order to achieve any desired precision is to refine the search near this discrete maximum, find a new, better approximation, and refine again, until we have enough precision. Of course, one first problem with this algorithm is the initial search using a maximal time {T}. It is possible that if {T} or {N} are not large enough, then we do not detect any intersection of the two polygons. Thus, an initial guess, based on a mathematical argument is needed in order to reduce the search of the optimal time to an interval which is small enough to have enough initial precision to detect the discrete maximum.

The algorithm presented below, uses Matlab’s predefined function polybool which can compute the intersection of two polygons. Of course, this is an overkill, since dealing with intersections of convex polygons is not that complicated (but still, I didn’t have enough time to play with the problem, in order to provide a more optimized version). I do not treat the search for the initial time interval. As I think about it, I guess a n argument based on finding some line intersections should give us a narrow enough time interval (with some care for the case when the two speed directions are collinear). The algorithm presented below solves the sample cases, but could fail in more general situations.


function Prob1_2015(p1,p2)

% choose initial polygons; see the text of the problem
p1 = [6 3 2 2 4 3 6 6 6 7 4 6 2 2 2];
p2 = [4 18 5 22 9 26 5 22 1 -2 1];

%p1 = [4 0 0 0 2 2 2 2 0 1 1];
%p2 = [4 10 0 10 2 12 2 12 0 -1 1];

np1 = p1(1);
np2 = p2(1);
cp1 = p1(2:1+2*np1);
cp2 = p2(2:1+2*np2);

vp1 = p1(end-1:end);
vp2 = p2(end-1:end);

cp1 = cp1(:);
cp1 = reshape(cp1,2,np1);

xp1 = cp1(1,:);
yp1 = cp1(2,:);
cp2 = cp2(:);
cp2 = reshape(cp2,2,np2);

xp2 = cp2(1,:);
yp2 = cp2(2,:);

%set precision
prec = 1;

%here there should be a clever initial choice of 
%the starting time and stopping time
%this choice works well in this case
start = 0;
stop  = 5;

while prec>1e-6
n = 100;

timex = linspace(start,stop,n);
areas = zeros(size(timex));

for i = 1:n
   t = timex(i);
   xt1 = xp1+t*vp1(1);
   yt1 = yp1+t*vp1(2);
   xt2 = xp2+t*vp2(1);
   yt2 = yp2+t*vp2(2);
   
   [x,y] = polybool('intersection',xt1,yt1,xt2,yt2);
   areas(i) = polyarea(x,y);
end
[m,I] = max(areas);
if m<1e-6
   % if no polygonal intersection is detected
   % there is nothing further to do
   display('never');
   break
end

tapp = timex(I);
fprintf('Precision %f | Time %f\n',prec,tapp);
start = tapp-prec;
stop  = tapp+prec;
prec  = prec/10;
end
clf
%this draws the final position of the polygon
%as well as their intersection
fill(xt1,yt1,'blue')
axis equal
hold on
fill(xt2,yt2,'red')
fill(x,y,'green')
axis equal
hold off

Here’s what you get for the first sample test provided in the questions:polygons3

 >> Prob1_2015
    res = 4.193548

Balkan Mathematical Olympiad – 2015 Problems

Problem 1. If {{a, b}} and {c} are positive real numbers, prove that

\displaystyle a ^ 3b ^ 6 + b ^ 3c ^ 6 + c ^ 3a ^ 6 + 3a ^ 3b ^ 3c ^ 3 \ge{ abc \left (a ^ 3b ^ 3 + b ^ 3c ^ 3 + c ^ 3a ^ 3 \right) + a ^ 2b ^ 2c ^ 2 \left (a ^ 3 + b ^ 3 + c ^ 3 \right)}.

(Montenegro)

Problem 2. Let {\triangle{ABC}} be a scalene triangle with incentre {I} and circumcircle {\omega}. Lines {AI, BI, CI} intersect {\omega} for the second time at points {D, E, F}, respectively. The parallel lines from {I} to the sides {BC, AC, AB} intersect {EF, DF, DE} at points {K, L, M}, respectively. Prove that the points {K, L, M} are collinear. (Cyprus)

Problem 3. A committee of {3366} film critics are voting for the Oscars. Every critic voted just an actor and just one actress. After the voting, it was found that for every positive integer {n \in \left \{1, 2, \ldots, 100 \right \}}, there is some actor or some actress who was voted exactly {n} times. Prove that there are two critics who voted the same actor and the same actress. (Cyprus)

Problem 4. Prove that among {20} consecutive positive integers there is an integer {d} such that for every positive integer {n} the following inequality holds

\displaystyle n \sqrt{d} \left\{n \sqrt {d} \right \} > \dfrac{5}{2}

where by {\left \{x \right \}} denotes the fractional part of the real number {x}. The fractional part of the real number {x} is defined as the difference between the largest integer that is less than or equal to {x} to the actual number {x}. (Serbia)

Source: AoPS

Categories: Olympiad Tags:

Seemous 2015 Problems

March 11, 2015 Leave a comment

Problem 1. Prove that for every {x \in (0,1)} the following inequality holds:

\displaystyle \int_0^1 \sqrt{1+\cos^2 y}dy > \sqrt{x^2+\sin^2 x}.

Problem 2. For any positive integer {n}, let the functions {f_n : \Bbb{R} \rightarrow \Bbb{R}} be defined by {f_{n+1}(x)=f_1(f_n(x))}, where {f_1(x)=3x-4x^3}. Solve the equation {f_n(x)=0}.

Problem 3. For an integer {n>2}, let {A,B,C,D \in \mathcal{M}_n(\Bbb{R})} be matrices satisfying:

\displaystyle AC-BD = I_n,

\displaystyle AD+BC = O_n,

where {I_n} is the identity matrix and {O_n} is the zero matrix in {\mathcal{M}_n(\Bbb{R})}.

Prove that:

  • (a) {CA-DB = I_n} and {DA+CB = O_n}.
  • (b) {\det(AC) \geq 0} and {(-1)^n \det(BD) \geq 0}.

Problem 4. Let {I\subset \Bbb{R}} be an open interval which contains {0} and {f: I \rightarrow \Bbb{R}} be a function of class {C^{2016}(I)} such that {f(0)=0, f'(0)=1, f''(0) = ... = f^{(2015)}(0)=0,\ f^{(2016)}(0)<0}.

  • (i) Prove that there exists {\delta>0} such that {0<f(x)<x} for {x \in (0,\delta)}.
  • (ii) With {\delta} determined at (i) define the sequence {(a_n)} by

    \displaystyle a_1 = \frac{\delta}{2},\ a_{n+2}=f(a_n),\ n \geq 1.

    Study the convergence of the series {\displaystyle \sum_{n=1}^\infty a_n^r} for {r \in \Bbb{R}}.

Hints: 

Read more…

Categories: Olympiad Tags: , , ,
%d bloggers like this: