**International Mathematical Olympiad 2018**

5) *Let a _{1} , a_{2} , ... be an infinite row of positive integers.
Suppose there is an integer N > 1 such that for every n ≥ N holds:
*

a_{1}/a_{2} + a_{2}/a_{3} + ... + a_{n-1}/a_{n} + a_{n}/a_{1} is an integer.

Prove there exists a positive integer M such that for each m ≥ M holds a_{m}=a_{m+1}.

__Solution:__

Suppose for each natural number M there is an m ≥ M such that a_{m} is not equal to a_{m+1}.

We have to prove that for each N > 1 there is an n ≥ N such that
a_{1}/a_{2} + a_{2}/a_{3} + ... + a_{n-1}/a_{n} + a_{n}/a_{1}
is not an integer.

Let N > 1. Take M = N-1. Let m ≥ M be minimal such that a_{m} is not equal to a_{m+1}, so
for n = m+1 we have a_{1} = a_{2} = ... = a_{n-1} and a_{n} is not equal to a_{1}.

We have to prove that a_{1}/a_{n} + a_{n}/a_{1} is not an integer.

Equivalently, let d = gcd(a_{1},a_{n}), a = a_{1}/d, b = a_{n}/d, so a and b
are distinct relatively prime positive integers.

We have to prove that ab doesn't divide a^{2} + b^{2}.

Since at least one of a and b must have a prime factor that doesn't divide the other, this is evident.

**International Mathematical Olympiad 2017**

3) * A myopic but persistent hunter tries to catch a rabbit with his hands according to the following procedure:
i) They start at the same spot; the rabbit jumps to a position at distance 1 meter.
ii) As long as the hunter didn't make 1000000000 moves yet, and the rabbit is within 100 meters from the hunter,
the hunter makes a move to some spot at most 1 meter from the rabbit;
iii) After each move of the hunter, the rabbit makes a jump of 1 meter.
Can the rabbit escape from the hunter by reaching a position at least 100 meters away from the hunter within
1000000000 jumps? *

__Solution:__

I think the best strategy of the rabbit is always jumping away from the hunter in the opposite direction, so I wrote the following Pascal program:

program imo2017-3;

const pi=3.141592654;

var a1,a2,b1,b2,t,mu,p1,p2,k,c,d:real;

begin

b1:=0;b2:=0;k:=0;a1:=0;a2:=1;

repeat

k:=k+1;

t:=random*2*pi;mu:=random;

p1:=a1+mu*cos(t);p2:=a2+mu*sin(t);

c:=sqrt((p1-b1)*(p1-b1)+(p2-b2)*(p2-b2));

b1:=b1+(p1-b1)/c;b2:=b2+(p2-b2)/c;

d:=sqrt((b1-a1)*(b1-a1)+(b2-a2)*(b2-a2));

a1:=a1-(b1-a1)/d;a2:=a2-(b2-a2)/d;

until (k>1000000000) or (d>100);

if d>100 then writeln('rabbit wins') else writeln ('hunt undecided');
writeln(k:13:0); readln

end.

I ran the program. The rabbit escaped after 4058428 jumps.

However, it's more realistic to assume the probability density f of the distance between the rabbit and the spot the hunter
runs to is not constant with f(0) = f(1) = 1, but linear and descending with f(0) = 2 and f(1) = 0.

In this case we have to use, instead of mu:=random, mu:=1-sqrt(random).

I ran the adapted program and found the rabbit escaped after 8115418 jumps.

**International Mathematical Olympiad 2014**

1) *Let a _{0} , a_{1} , a_{2} , ... be a strictly increasing sequence of positive integers.
*

Prove there exists a unique positive integer n such that (a_{0} + a_{1} + ... + a_{n} )/n is greater than a_{n} but at most as great as a_{n+1} .

__Solution:__

For each positive integer k, let t_{k} := (a_{k} - a_{0} ) + (a_{k} - a_{1} ) + (a_{k} - a_{k-1} ).

We have to prove there exists a unique n such that t_{n} is smaller than a_{n} , but t_{n+1} is greater than a_{n+1} .

Indeed, t_{1} is smaller than a_{1} , but, since (t_{k+1} - t_{k} ) = (k+1)*(a_{k+1} - a_{k} ), the sequence {t_{k} } increases (much) faster than
the sequence {a_{k} } , so there is a unique n where {t_{k} } goes past {a_{k} }.

3) *Let ABCD be a convex triangle with right angles at B and D. Let H on BD be such that AH is perpendicular to BD.
Let S and T be points on AB and AD, resp, such that H lies within triangle SCT and the angles CHS and CHT are 90 degrees greater than the angles CSB and CTD, resp.
Prove that the circumscribed circle of triangle STH is tangent to BD.*

__Partial solution:__

The situation depicted in the picture amounts to a system of 25 linear equations in 24 unknown real numbers :

4 equations say the angles ABC, ADC, AHB, AHD are right, 4 others say the angles ASB, ATD, BHD are straight, 17 others say the sum of the angles in any of the 17 triangles is 180 degrees.

We want to prove that these 25 equations together with the premises e+d-u = 90 = b+c-v imply j-a = w-f , which is equivalent to the existence of M on AH such that MH = MS = MT.

I solved the system of 27 equations by expressing 18 of the variables in the other 6 (p,a,m,k,e,x), but I still need an extra equation which must yield m = e+x-90.

4) *The points P and Q are lying on the side BC of the acute angled triangle ABC so that the angles PAB and BCA are equal, and likewise the angles CAQ and ABC.
The points M and N are lying on the straight lines AP and AQ, respectively, so that P is the center of segment AM and Q the center of segment AN.
Prove that the intersection point of the straight lines BM and CN is lying on the circumscribed circle of the triangle ABC.*

__Solution:__

**International Mathematical Olympiad 2013**

4) *Let ΔABC be an acute-angled triangle with orthocenter H. Let W be a point distinct from B and C on the segment BC.
Let ω _{1} be the circumscribed circle of ΔBWH and let X be the point on ω_{1} such that WX is a diameter of ω_{1}.
Analogously, let ω_{2} be the circumscribed circle of ΔCWH and let Y be the point on ω_{2} such that WY is a diameter of ω_{2}.
Prove that X,Y,H are collinear.*

__Solution:__

Give coordinates H(0,0), A(-a,-1), B(b,-1), C(0,ab-1) with a,b positive and ab greater than 1. We have W(b-tb,tab-1) for some positive t smaller than 1.

Let M be the center of ω_{1}. We find M((ab^{2}-2b+tb+ta^{2}b-a)/(2ab-2),(ta^{2}b^{2}-2ab+tb^{2}+1-b^{2})/(2ab-2)) and
X((ta^{2}b+tab^{2}-a-b)/(ab-1),(tb^{2}+tab-ab-b^{2})/(ab-1)).

Let N be the center of ω_{2}. We find N((a+b-tb-ta^{2}b)/2,(ab-1)/2) and Y(a-ta^{2}b,ab-tab).

We see X,Y,H are lying on the line y = mx with m = (b(1-t)/(1-tab)).

**International Mathematical Olympiad 2011**

1) *For any set A of four distinct positive integers a1,a2,a3,a4 let s _{A} be the sum of the elements of A and n_{A} the number of pairs {ai,aj}
of its elements such that ai + aj divides s_{A}. Determine the sets A such that n_{A} is maximal.*

__Solution:__

Without loss of generality we assume a1 < a2 < a3 < a4.

n_{A} is maximal iff ((a1+a2 divides a3+a4) and (a1+a3 divides a2+a4) and (a1+a4 divides a2+a3)) and (a2+a3 divides a1+a4)), so iff
((a1+a2 divides a3+a4) and (a1+a3 divides a2+a4) and (a1+a4 = a2+a3)).

So the elements of A are (in increasing order) a,b,c,b+c-a, where for some positive integers m,n we must have 2c+b-a = (1+m)(a+b) and 2b+c-a = (1+n)(a+c) and m is greater than n.

When we procede to express b and c in a, we get, somewhere in the middle of the calculations: (4-mn)c = (mn+4m+4)a.

So mn can only be 2 or 3, so ((m=2 and n=1) or ((m=3 and n=1)).

After completing the calculations we get A={a,5a,7a,11a} or A={a,11a,19a,29a}.

4) *Let n be a natural number. We have a balance and n weights with masses 2 ^{i}, i=0,..,n-1. We want to lay all weights successively on the balance, either at the left side or at the right side,
in such a way that the right side is never heavier than the left side. In how many ways can we do this?*

__Solution:__

The total number of laying all weights on the balance is n!*2^{n}. We have to determine the fraction of layings that go wrong.

Since 2^{k} is greater than SUM(0≤i≤k-1: 2^{i}) for all k, the laying goes wrong iff we place a weight at the right side that is heavier than all weights laid previously.

I wrote a program to approximate the fraction f of layings that go wrong for n=1,..,100.

Among the output: for n=1 we have f=0.5, for n=2 we have f=0.375, for n=5 we have f=0.247.., for n=10 we have f= 0.177...,
for n=30 we have f=0.10.., for n=80 we have f=0.06.., for n=100 we have f=0.05...

The program:

program weegschaal;

var m,n,k,max,keus:0..100; aantal,aantalgoed:real;

gehad:array[1..100] of boolean; fout:boolean;

begin

readln(n);

aantal:=0; aantalgoed:=0;

while true do

begin

aantal:=aantal+1;

for m:=1 to n do gehad[m]:=false;

k:=0; max:=0; fout:=false;

repeat

k:=k+1;

repeat keus:=random(n)+1 until (not gehad[keus]);

gehad[keus]:=true;

if random>0.5 then if keus>max then fout:=true;

if keus>max then max:=keus

until (fout or (k=n));

if not fout then aantalgoed:=aantalgoed+1;

writeln(aantalgoed/aantal:13:10)

end

end.

Studying the output, I found the solution as follows:

The probability that with placing the k-th weight the laying goes wrong is 1/(2k). (This is the probability that the k-th weight is the maximum up to now and we place it to the right.)

So the fraction of layings that do not go wrong is PRODUCT(1≤k≤n: 1-1/(2k)).

So the number of correct layings is (2n-1)(2n-3)(2n-5)...5.3.1.

**International Mathematical Olympiad 2001** (Allegedly, no solution has been published up to now.)

5) *Let ABC be a triangle and let the angle at A be 60 degrees. Let X belong to BC such that AX bisects the angle at A. Let Y belong to AC such that BY bisects the angle at B.
Suppose AX+BX = AY+BY. Determine the possible values in degrees of the angle β at B.*

__Solution:__

The possible values are β=60 and β=30 only. This can be proved as follows:

Give coordinates A(0,0), B(c,0), C(1/2,√3/2) = C(c-ρcos(β),ρsin(β)), X(τ(√3/2,1/2)) = X(c-σcos(β),σsin(β)),
Y(ζ(1/2,√3/2) = Y(c-ωcos(β/2),ωsin(β/2)).

From AX+BX = AY+BY we have σ+τ = ζ+ω.

Now we can express c,ρ,σ,τ,ω,ζ in β. Subsequently, using σ+τ = ζ+ω we get:

(2sin(β)+1)(sin(β/2)+√3cos(β/2)) = (2sin(β/2)+√3)(cos(β)+√3sin(β)).

Let p:=sin(β/2). We use the wellknown goniometrical formulas and take squares to eliminate roots. Then we get a polynomial equation in p of degree six.

Since p=0 and p=1/2 (corresponding to β=60) clearly are solutions, we can divide by p and 2p-1. Thereafter we have:

(64-32√3)p^{4} + (-16+16√3)p^{3} + (-80+48√3)p^{2} + (20-12√3)p + (24-14√3) = 0.

After a numerical exploration up to 10 decimal places we guess this equation has no other solution than the one corresponding to β=30 and (hence) p=(√6-√2)/4.

For this value of p the left hand side is exactly zero.

Analysis of the derivatives shows that there are no other zeros of the left hand side between 0 and 1.

**International Mathematical Olympiad 1997 (generalized problem)**

5) *For natural numbers s and t find natural numbers a and b such that a ^{bs} = b^{at}.*

__Solution:__

Of course, a=b=1 yields a solution, and if s=t then a=b. Henceforth we only observe non-trivial solutions.

Then from unique prime factorization we deduce there must be natural numbers n, a_{1}, ... , a_{n}, b_{1}, ... , b_{n}, and primes p_{1}, ... , p_{n},
such that

a = p_{1}^{a1} ... p_{n}^{an}, b = p_{1}^{b1} ... p_{n}^{bn}

and a_{i}b^{s} = b_{i}a^{t} for all i ∈ {1,..,n}.

So there must exist natural numbers f and g with gcd(f,g)=1 such that fa_{i} = gb_{i}, and natural numbers c_{i} := b_{i}/f = a_{i}/g.

For c := p_{1}^{c1} ... p_{n}^{cn} we have a = c^{g}, b = c^{f} and
g/f = a_{i}/b_{i} = a^{t}/b^{s} = c^{gt}/c^{fs}, so fc^{gt} = gc^{fs}.

Now for given s and t we readily find the solutions.

For instance, if s=2 and t=1 we have fc^{g} = gc^{2f}. Then we consider three cases:

If g < 2f then f/g = c^{2f-g}, g=1, f = c^{2f-1}. If c=1 we get trivial solutions, else f ≥ 2^{2f-1}, yielding a contradiction.

If g = 2f then from fc^{g} = gc^{2f} we find g=f, yielding a contradiction.

If g > 2f then g/f = c^{g-2f}, f=1, g = c^{g-2}, so either g=3, c=3, b=3, a=27, or g=4, c=2, b=2, a=16.

Another example: s=3 and t=2, so fc^{2g} = gc^{3f}.

As above we find one nontrivial case with g = c^{2g-3} and f=1, g=2, c=2, b=2, a=4.