## Balkan Mathematical Olympiad 2018

**Problem 1.** A quadrilateral is inscribed in a circle , where and is not parallel to . Point is the intersection of the diagonals and and the perpendicular from to intersects the segment at the point . If bisects the angle , prove that is a diameter of the circle .

**Problem 2.** Let be a positive rational number. Two ants are initially at the same point in the plane. In the -th minute each of them chooses whether to walk due north, east, south or west and then walks the distance of meters. After a whole number of minutes, they are at the same point in the plane (non necessarily ), but have not taken exactly the same route within that time. Determine all the possible values of .

**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 of positive integers such that if initially the two piles have and coins, respectively, then Bob has a winning strategy.

**Problem 4.** Find all primes and such that divides .

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

## Sum of the Euler Totient function

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

where the product is made over all primes dividing .

If you have to compute for all numbers less than a threshold then another property could be useful: is arithmetic, that is, whenever . Therefore you could store all values computed until and for computing the value there are two possibilities: is a prime power and then or is composite and with . Then use the stored values to compute .

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

One approach is to compute each 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 and about seconds to compute . This is super linear in time, since the algorithm computes the factorization for each 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 or even larger. Therefore, there must be more efficient ways to compute out there, so let’s study some of the properties of . In another post I dealt with the acceleration of the computation of the sum of the divisor function.

We have which is the number of pairs with such that . It is not difficult to see that the total number of such pairs is . Moreover, the possible values of are . Now, if for we search instead for pairs satisfying then we have with and we get

There fore the number of pairs with gcd equal to is . Now we arrive at an interesting recursive formula:

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

Therefore we can change the index of summation from to . The range of for which the interval contains more than one integer is of order . Indeed, . Therefore for we should have at least one integer in the interval . The part where is larger than corresponds to smaller than . Therefore, we can split into two sums, each of order . and get that

where in the last sum we must make sure that in order to avoid duplicating terms in the sum.

Therefore we replaced a sum until to two sums with upper bound . The complexity is not , but something like since we have a recursive computation. Nevertheless, with this new formula and using memoization, to keep track of the values of already computed, we can compute very fast:

is computed instantly (vs second with brute force)

takes second (vs seconds with brute force)

takes seconds (vs over minutes with brute force)

takes seconds

takes about minutes

etc. Recall that these computations are done in Pari GP, which is not too fast. If you use C++ you can compute in seconds, in second and in seconds and in under a minute, if you manage to get past overflow errors.

## Romanian Masters in Mathematics contest – 2018

**Problem 1.** Let be a cyclic quadrilateral an let be a point on the side The diagonals meets the segments at The line through parallel to mmets the extension of the side beyond at The line through parallel to meets the extension of the side beyond at Prove that the circumcircles of the triangles and are tangent .

**Problem 2.** Determine whether there exist non-constant polynomials and with real coefficients satisfying

**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 be positive integers such that and . Let be the set of values attained by as runs through the positive integers. Show that is the set of all positive divisors of some positive integer.

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

- each of the points is a startpoint or endpoint of an arrow;
- no two arrows intersect;
- there are no two arrows and such that , , and appear in clockwise order around the circle (not necessarily consecutively).

**Problem 6.** Fix a circle , a line to tangent , and another circle disjoint from such that and lie on opposite sides of . The tangents to from a variable point on meet at and . Prove that, as varies over , the circumcircle of 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 with the circle . You’ll notice immediately that this point belongs to the circle . Furthermore, there is a common tangent to the two circles at this point.

For Problem 2 we have . 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 divides and then divides .

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.

## Project Euler – Problem 264

Today I managed to solve problem 264 from Project Euler. This is my highest rating problem until now: 85%. You can click the link for the full text of the problem. The main idea is to find all triangles ABC with vertices having integer coordinates such that

- the circumcenter O of each of the triangles is the origin
- the orthocenter H (the intersection of the heights) is the point of coordinates (0,5)
- the perimeter is lower than a certain bound

I will not give detailed advice or codes. You can already find a program online for this problem (I won’t tell you where) and it can serve to verify the final code, before going for the final result. Anyway, following the hints below may help you get to a solution.

The initial idea has to do with a geometric relation linking the points A, B, C, O and H. Anyone who did some problems with vectors and triangles should have come across the needed relation at some time. If not, just search for important lines in triangles, especially the line passing through O and H (and another important point).

Once you find this vectorial relation, it is possible to translate it in coordinates. The fact that points A, B, C are on a circle centered in O shows that their coordinates satisfy an equation of the form , where is a positive integer, not necessarily a square… It is possible to enumerate all solutions to the following equation for fixed , simply by looping over and . This helps you find all lattice points on the circle of radius .

Once these lattice points are found one needs to check the orthocenter condition. The relations are pretty simple and in the end we have two conditions to check for the sum of the x and y coordinates. The testing procedure is a triple loop. We initially have a list of points on a circle, from the previous step. We loop over them such that we dont count triangles twice: i from 1 to m, j from i+1 to m, k from j+1 to m, etc. Once a suitable solution is found, we compute the perimeter using the classical distance formula between two points given in coordinates. Once the perimeter is computed we add it to the total.

Since the triple loop has cubic complexity, one could turn it in a double loop. Loop over pairs and construct the third point using the orthocenter condition. Then just check if the point is also on the circle. I didn’t manage to make this double loop without overcounting things, so I use it as a test: use double loops to check every family of points on a given circle. If you find something then use a triple loop to count it properly. It turns out that cases where the triple loop is needed are quite rare.

So now you have the ingredients to check if on a circle of given radius there are triangles with the desired properties. Now we just iterate over the square of the radius. The problem is to find the proper upper bound for this radius in order to get all the triangles with perimeter below the bound. It turns out that a simple observation can get you close to a near optimal bound. Since in the end the radii get really large and the size of the triangles gets really large, the segment OH becomes small, being of fixed length 5. When OH is very small, the triangle is almost equilateral. Just use the upper bound for the radius for an equilateral triangle of perimeter equal to the upper bound of 100000 given in the problem.

Using these ideas you can build a bruteforce algorithm. Plotting the values of the radii which give valid triangles will help you find that you only need to loop over a small part of the radii values. Factoring these values will help you reduce even more the search space. I managed to solve the problem in about 5 hours in Pari GP. This means things could be improved. However, having an algorithm which can give the result in “reasonable” time is fine by me.

I hope this will help you get towards the result.

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

## Missing digit – short puzzle

The number has digits, all different; which digit is missing?

*Mathematical Mind-Benders, Peter Winkler*

## Monotonic bijection from naturals to pairs of natural numbers

This is a cute problem I found this evening.

Suppose is a bijection such that if and , then .

Prove that if then .

*Proof:* The trick is to divide the pairs of positive integers into families with the same product.

Note that the -th column contains as many elements as the number of divisors of . Now we just just use a simple observation. Let be on the -th column (i.e. ). If then cannot be on one of the first columns. Indeed, the monotonicity property implies . The fact that is a bijection assures us that cover the first columns. Moreover, one element from the -th column is surely covered, namely . This means that

where we have denoted by the number of positive divisors of .