## Putnam 2017 A2 – Solution

**Problem A2.** We have the following recurrence relation

for , given and . In order to prove that is always a polynomial with integer coefficients we should prove that divides 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

We add them and we obtain the following relation

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 such that:

**Problem 2.** Consider an acute-angled triangle with and let be its circumscribed circle. Let and be the tangents to the circle at points and , respectively, and let be their intersection. The straight line passing through the point and parallel to intersects in point . The straight line passing through the point and parallel to intersects in point . The circumcircle of the triangle intersects in , where is located between and . The circumcircle of the triangle intersects the line (or its extension) in , where is located between and .

Prove that , , and are concurrent.

**Problem 3.** Let denote the set of positive integers. Find all functions such that

for all

**Problem 4.** On a circular table sit 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 be a positive integer and denote by the ring of integers modulo . Suppose that there exists a function satisfying the following three properties:

- (i) ,
- (ii) ,
- (iii) for all .

Prove that modulo .

## IMC 2016 – Day 1 – Problem 2

**Problem 2.** Let and be positive integers. A sequence of matrices is *preferred* by Ivan the Confessor if for , but for with . Show that if in al preferred sequences and give an example of a preferred sequence with for each .

## Balkan Mathematical Olympiad – 2016 Problems

**Problem 1.** Find all injective functions such that for every real number and every positive integer ,

**Problem 2.** Let be a cyclic quadrilateral with . The diagonals intersect at the point and lines and intersect at the point . Let and be the orthogonal projections of onto lines and respectively, and let , and be the midpoints of , and respectively. Prove that the second intersection point of the circumcircles of triangles and lies on the segment .

**Problem 3.** Find all monic polynomials with integer coefficients satisfying the following condition: there exists a positive integer such that divides for every prime for which 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 colours so that no rectangle with perimeter contains two squares of the same colour. Show that no rectangle of size or contains two squares of the same colour.

## SEEMOUS 2016 – Problems

**Problem 1.** Let be a continuous and decreasing real valued function defined on . Prove that

When do we have equality?

**Problem 2.** a) Prove that for every matrix there exists a matrix such that .

b) Prove that there exists a matrix such that for all .

**Problem 3.** Let be idempotent matrices () in . Prove that

where and is the set of matrices with real entries.

**Problem 4.** Let be an integer and set

Prove that

a)

b) .

Some hints follow.

## Problems of the Miklos Schweitzer Competition 2014

**Problem 1.** Let be a positive integer. Let be a familiy of sets that contains more than half of all subsets of an -element set . Prove that from we can select sets that form a separating family of , i.e., for any two distinct elements of there is a selected set containing exactly one of the two elements.

**Problem 2.** let and let be non-degenerate subintervals of the interval . Prove that

where the summation is over all pairs of indices such that and are not disjoint.

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

**Problem 4.** For a positive integer , let be the number of sequences of positive integers such that and for . We make the convention . Let be the unique real number greater than such that . Prove that

- (i) .
- (ii) There exists no number such that .

**Problem 5.** Let be a non-real algebraic integer of degree two, and let be the set of irreducible elements of the ring . Prove that

**Problem 6.** Let be a representation of a finite -group over a field of characteristic . Prove that if the restriction of the linear map to a finite dimensional subspace of is injective, then the subspace spanned by the subspaces () is the direct sum of these subspaces.

**Problem 7.** Lef be a continuous function and let be arbitrary. Suppose that the Minkowski sum of the graph of and the graph of (i.e. the set has Lebesgue measure zero. Does it follow then that the function is of the form , with suitable constants ?

**Problem 8.** Let be a fixed integer. Calculate the distance

where runs over polynomials of degree less than with real coefficients and runs over functions of the form

defined on the closed interval , where and .

**Problem 9.** Let , and let be a convex body, i.e. a compact convex set with nonempty interior. Define the barycenter of the body with respect to the weight function by the usual formula

Prove that the translates of the body have pairwise distinct barycenters with respect to .

**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 be a random variable that is uniformly distributed on the interval , and let

Show that, as , the limit distribution of is the Cauchy distribution with density function .