International Mathematical Olympiad 2011
1) For any set A of four distinct positive integers a1,a2,a3,a4 let sA be the sum of the elements of A and nA the number of pairs {ai,aj} of its elements such that ai + aj divides sA. Determine the sets A such that nA is maximal.
Solution:
Without loss of generality we assume a1 < a2 < a3 < a4.
nA 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 2i, 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!*2n. We have to determine the fraction of layings that go wrong.
Since 2k is greater than SUM(0≤i≤k-1: 2i) 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)p4 + (-16+16√3)p3 + (-80+48√3)p2 + (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.