### Archive

Posts Tagged ‘Combinatorics’

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

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

## Problems of the Miklos Schweitzer Competition 2014

Problem 1. Let ${n}$ be a positive integer. Let ${\mathcal{F}}$ be a familiy of sets that contains more than half of all subsets of an ${n}$-element set ${X}$. Prove that from ${\mathcal{F}}$ we can select ${\lceil \log_2 n\rceil+1 }$ sets that form a separating family of ${X}$, i.e., for any two distinct elements of ${X}$ there is a selected set containing exactly one of the two elements.

Problem 2. let ${k \geq 1}$ and let ${I_1,...,I_k}$ be non-degenerate subintervals of the interval ${[0,1]}$. Prove that

$\displaystyle \sum \frac{1}{|I_i \cup I_j|} \geq k^2,$

where the summation is over all pairs of indices ${(i,j)}$ such that ${I_i}$ and ${I_j}$ are not disjoint.

Problem 3. We have ${4n+5}$ points in the plane, no three of them collinear. The points are colored with two colors. Prove that from the points we can form ${n}$ empty triangles (they have no colored points in their interiors) with pairwise disjoint interiors, such that all points occuring as vertices of the ${n}$ triangles have the same color.

Problem 4. For a positive integer ${n}$, let ${f(n)}$ be the number of sequences ${a_1,...,a_k}$ of positive integers such that ${a_i \geq 2}$ and ${a_1...a_k = n}$ for ${k \geq 1}$. We make the convention ${f(1)=1}$. Let ${\alpha}$ be the unique real number greater than ${1}$ such that ${\sum_{n=1}^\infty n^{-\alpha}=2}$. Prove that

• (i) ${ \sum_{ k = 1}^n f(k)= O(n^\alpha)}$.
• (ii) There exists no number ${\beta<\alpha}$ such that ${f(n)=O(n^\beta)}$.

Problem 5. Let ${\alpha}$ be a non-real algebraic integer of degree two, and let ${P}$ be the set of irreducible elements of the ring ${\Bbb{Z}[\alpha]}$. Prove that

$\displaystyle \sum_{ p \in P} \frac{1}{|p|^2} = \infty.$

Problem 6. Let ${\rho : G \rightarrow GL(V)}$ be a representation of a finite ${p}$-group ${G}$ over a field of characteristic ${p}$. Prove that if the restriction of the linear map ${\sum_{ g \in G} \rho(g)}$ to a finite dimensional subspace ${W}$ of ${V}$ is injective, then the subspace spanned by the subspaces ${\rho(g)W}$ (${g \in G}$) is the direct sum of these subspaces.

Problem 7. Lef ${f: \Bbb{R} \rightarrow \Bbb{R}}$ be a continuous function and let ${g: \Bbb{R} \rightarrow \Bbb{R}}$ be arbitrary. Suppose that the Minkowski sum of the graph of ${f}$ and the graph of ${g}$ (i.e. the set ${\{(x+y,f(x)+g(y) : x,y \in \Bbb{R}\}}$ has Lebesgue measure zero. Does it follow then that the function ${f}$ is of the form ${f(x)=ax+b}$, with suitable constants ${a,b \in \Bbb{R}}$?

Problem 8. Let ${n \geq 1}$ be a fixed integer. Calculate the distance

$\displaystyle \inf_{p,f} \max_{0 \leq x \leq 1} |f(x)-p(x)|,$

where ${p}$ runs over polynomials of degree less than ${n}$ with real coefficients and ${f}$ runs over functions of the form

$\displaystyle f(x) = \sum_{ k = n}^\infty c_kx^k$

defined on the closed interval ${[0,1]}$, where ${c_k\geq 0}$ and ${\sum_{k=n}^\infty c_k =1}$.

Problem 9. Let ${\rho : \Bbb{R}^n \rightarrow \Bbb{R},\ \rho(x)=e^{-\|x\|^2}}$, and let ${K \subset \Bbb{R}^n}$ be a convex body, i.e. a compact convex set with nonempty interior. Define the barycenter ${s_K}$ of the body ${K}$ with respect to the weight function ${\rho}$ by the usual formula

$\displaystyle s_K = \frac{\int_K \rho(x) x dx}{\int_K \rho(x)dx}.$

Prove that the translates of the body ${K}$ have pairwise distinct barycenters with respect to ${\rho}$.

Problem 10. To each vertex of a given triangulation of the two dimensional sphere, we assign a convex subset of the plane. Assume that the three convex sets corresponding to the three vertices of any two dimensional face of the triangulation have at least one point in common. Show that there exist four vertices such that the corresponding convex sets have at least one point in common.

Problem 11. Let ${U}$ be a random variable that is uniformly distributed on the interval ${[0,1]}$, and let

$\displaystyle S_n = 2\sum_{k=1}^n \sin(2kU\pi).$

Show that, as ${n \rightarrow \infty}$, the limit distribution of ${S_n}$ is the Cauchy distribution with density function ${f(x) =\frac{1}{\pi(1+x^2)}}$.

## IMC 2014 Day 2 Problem 5

For every positive integer ${n}$, denote by ${D_n}$ the number of permutations ${(x_1,...,x_n)}$ of ${(1,2,...,n)}$ such that ${x_j \neq j}$ for every ${1 \leq j \leq n}$. For ${1 \leq k \leq \frac{n}{2}}$, denote by ${\Delta(n,k)}$ the number of permutations ${(x_1,...,x_n)}$ of ${(1,2,...,n)}$ such that ${x_i = k+i}$ for every ${1 \leq i \leq k}$ and ${x_j \neq j}$ for every ${1 \leq j \leq n}$. Prove that

$\displaystyle \Delta(n,k) = \sum_{i = 0}^{k-1} {k-1 \choose i} \frac{D_{(n+1)-(k+i)}}{n-(k+i)}.$

IMC 2014 Day 2 Problem 5

## IMC 2014 Day 2 Problem 4

We say that a subset of ${\Bbb{R}^n}$ is ${k}$almost contained by a hyperplane if there are less than ${k}$ points in that set which do not belong to the hyperplane. We call a finite set of points ${k}$generic if there is no hyperplane that ${k}$-almost contains the set. For each pair of positive integers ${k}$ and ${n}$, find the minimal number ${d(k,n)}$ such that every finite ${k}$-generic set in ${\Bbb{R}^n}$ contains a ${k}$-generic subset with at most ${d(k,n)}$ elements.

IMC 2014 Day 2 Problem 4

## IMC 2014 Day 1 Problem 5

Let ${A_1A_2...A_{3n}}$ be a close broken line consisting of ${3n}$ line segments in the Euclidean plane. Suppose that no three of its vertices are collinear and for each index ${i=1,2,...,3n}$, the triangle ${A_iA_{i+1}A_{i+2}}$ has counterclockwise orientation and ${\angle A_iA_{i+1}A_{i+2}=60^\circ}$, using the notation modulo ${3n}$. Prove that the number of self-intersections of the broken line is at most ${\displaystyle \frac{3}{2}n^2 -2n+1}$.

IMC 2014 Day 1 Problem 5

## IMO 2014 Problem 6

July 9, 2014 1 comment

A set of lines in the plane is in general position if no two are parallel and no three pass through the same point. A set of lines in general position cuts the plane into regions, some of which have finite area; we call these its finite regions. Prove that for all sufficiently large ${n}$, in any set of ${n}$ lines in general position it is possible to colour at least ${\sqrt{n}}$ lines blue in such a way that none of its finite regions has a completely blue boundary.

Note: Results with ${\sqrt{n}}$ replaced by ${c\sqrt{n}}$ will be awarded points depending on the value of the constant ${c}$.

IMO 2014 Problem 6 (Day 2)