**Problem 2019-1/A**

*Three gamblers select a non-negative probability distribution with mean 1. Say these distributions
are F,G,H. Then x is sampled from F, y is sampled from G, z is sampled from H. Biggest number wins.
What distributions should the gamblers choose?*

__Solution:__

At first sight it doesn't matter which distributions with mean 1 the gamblers choose, because the
expectation value is always 1.

However, if X chooses the distribution F that yields the sample x = 1 with certainty, and Y and Z both use the
distribution that yields each of the samples 0.1 and 1.9 with chance 1/2, then the chance that X wins is only 1/4.

To guarantee that the chance of winning solo is at least 1/3, the gamblers have to choose distributions that yield
big samples with a relatively big chance and equal samples with zero chance.

So each of them might best choose a continuous distribution E whose density function e(x) is slowly decreasing.

I propose they choose e(x) = a/(x+b)^{2+c} for some c > 0.

From ∫_{0}^{∞} e(x) dx = 1 = ∫_{0}^{∞} x*e(x) dx we deduce
b = c and a = (c+1)c^{c+1}.
Remark e(0) = (c+1)/c.

For c > 1 the variance is finite and equal to (c+1)/(c-1), which descends to the limit 1
if c tends to ∞.

The 50-percentile is c*2^{1/(c+1)}-c, which ascends to the limit ln(2) = 0.69315.. if c tends to ∞.

So each gambler may choose some c for which the variance is not too big nor too small and the 50-percentile is not
too small and the calculating facilities not too troublesome.

If they should agree to choose the same c, for instance c = 10, then each of them only has to take a random sample r
from (0,1), because the sample s is found from the equation ∫_{0}^{s} e(x) dx = r, so the largest s
comes from the largest r.

**Problem 2019-1/B**

*For given m ≥ 3, consider the regular m-gon inscribed in the unit circle. We denote the area of this m-gon by
A _{m}. Suppose m is odd. Prove that 2A_{m} and A_{2m} have the same minimal polynomial.*

__Solution:__

We find A_{m} = (m/2)*sin(2π/m).

Let y_{1} = A_{2m} = m*sin(π/m) and y_{2} = 2A_{m} = m*sin(2π/m).
Let x_{1} = m*cos(π/m) and x_{2} = m*cos(2π/m).

According to de Moivre, (cos(φ) + i sin(φ))^{k} = cos(kφ) + i sin(kφ),
so Im(x_{1} + i y_{1})^{m} = 0 and Im(x_{2} + i y_{2})^{m} = 0.

Moreover, since m is odd, none of these last two equations holds for an exponent less than m.

But both for x + iy = x_{1} + i y_{1} and for x + iy = x_{2} + i y_{2}
we have also

Im(x + i y)^{m} =
Im (Σ_{k=0}^{m} (m over k) x^{m-k} (iy)^{k}) =
m yx^{m-1} - (m over 3) y^{3}x^{m-3} + ... ± y^{m}, where the exponents of x are all even.

Using cos^{2} = 1 - sin^{2}, we can turn this into y times the minimal polynomial p(y) over the
rationals, which is the same for y = y_{1} and y = y_{2}.

For instance, for m=3 we get p(y) = 27 - 4y^{2} and for m=5 we get 3125 - 500y^{2} + 16y^{4}.

**Problem 2019-1/C**

*Let n be a prime number. Show that there are no groups with exactly n elements of order n. What happens
with this statement if n is not a prime number?*

__Solution:__

We deal with the general case at once, so let n have prime factorization
p_{1}^{a1}...p_{k}^{ak} with p_{1} ≤ ... ≤ p_{k}.
Let φ denote Euler's totient function.

Suppose a group G contains an element x of order n. Then x generates a cyclic subgroup C of G
that contains exactly φ(n) elements of order n, which generate the same subgroup C.

If G contains another element y of
order n, outside C, then y generates a cyclic subgroup D of G that has only elements of order less than n in common
with C. Etc.

So the union of all these cyclic subgroups of order n, if finite, contains mφ(n) elements of order n for some
natural m.

This number mφ(n) is equal to n iff m(p_{1}-1)..(p_{k}-1) = p_{1}..p_{k}.

Comparing the number of factors 2 at the left and right hand sides, we establish p_{1} = 2 and k ≤ 2. If
k=2 then by comparing the number of small prime factors at the left and right hand sides, we establish that
p_{2} must be 3.

We now distinguish between the cases k=1 and k=2.

1) Let k=1, so n = 2^{a} and m=2. So there are exactly two cyclic subgroups of order 2^{a}.

First suppose a=1. If the two cyclic subgroups of order 2 are generated by x and y, respectively, then there must be a
third cyclic subgroup
of order 2, generated by xy=yx. Contradiction. Here we finish the first part of the problem.

Next suppose a>1. There are several groups with 4 elements of order 4, for instance the direct product of C_{4}
and C_{2}, where C_{s} is cyclic of order s.

2) Let k=2, so n = 2^{a}3^{b} and m=3. There are several groups with 6 elements of order 6, for instance
the direct product C_{3}*C_{2}*C_{2}.

So the statement in the problem holds if n is prime, but not in general.

**Problem 2019-2/A** (edited)

*Let A = (a _{i,j} ) be the matrix on the natural base e in threedimensional euclidean space of a rotation R
(not equal to identity).
Suppose none of a_{2,3}+a_{3,2}, a_{1,3}+a_{3,1}, a_{1,2}+a_{2,1} is 0.
*

Prove that (1/(a_{2,3}+a_{3,2}), 1/(a_{1,3}+a_{3,1}), 1/(a_{1,2}+a_{2,1})) is a direction vector of the axis of R.

__Solution:__

There is an orthonormal base b, whose first vector is eigenvector of R with eigenvalue 1 and direction vector of its
axis, so that the matrix of R on base b
is [R]_{b,b} = M with matrix elements m_{1,1} = 1, m_{1,2} = m_{1,3} = m_{2,1} =
m_{3,1} = 0, m_{2,2} = m_{3,3} = cos(u), m_{3,2} = - m_{2,3} = sin(u) for some u
∈ (0,2π).

The last two vectors of b may be rotated around the axis over an arbitrary angle without changing this matrix M.
This will come in handy.

The relation between A and M is given by the formula A = [R]_{e,e} = [I]_{e,b} [R]_{b,b}
[I]_{b,e} = S M S^{-1}, where I is identity and the columns of S are the coordinates of the vectors of b
on the natural base e and S^{-1} is the inverse of S. Since b is orthonormal, S^{-1} is the transposed of S.

So we can express each matrix element a_{i,j} of A in cos(u), sin(u) and the matrix elements s_{m,n}
of S.

Now we have to prove that s_{1,1}(a_{2,3}+a_{3,2}) = s_{2,1}(a_{1,3}+a_{3,1}) =
s_{3,1}(a_{1,2}+a_{2,1}).

We may check these identities by taking the last two vectors of basis b in such a way that for some
v,w ∈ [0,2π) we have

s_{1,1} = cos(v)cos(w), s_{1,2} = - sin(v)cos(w), s_{1,3} = - sin(w),

s_{2,1} = cos(v)sin(w), s_{2,2} = - sin(v)sin(w), s_{2,3} = cos(w),

s_{3,1} = sin(v), s_{3,2} = cos(v), s_{3,3} = 0.

**Problem 2019-2/B** (adapted)

*1) Let k be a nonnegative integer and X a collection of infinite sets of positive integers such that no two sets of X
share more than k positive integers. Prove that X is countable.
*

*2) Does there exist an uncountable collection X of infinite sets of positive integers such that for all distinct sets
A and B of X the intersection of A and B is finite?*

__Solution:__

1) For every A in X, let A' be the set containing the smallest k+1 elements of A.

Let X' be the collection of all sets of k+1 positive integers.

Then A → A' is 1-1, so X is countable if X' is countable.

And we can count the sets A' of X' according to the principle: the greater the sum of the elements of A', the greater
its number in the count.

2) Yes: take the collection X of all infinite sets of the form {a_{1}, a_{1}a_{2},
a_{1}a_{2}a_{3}, a_{1}a_{2}a_{3}a_{4}, ... }, where a_{i}
∈ {0,1,2,...,9} (a_{1} > 0) and we use the decimal representation, so for instance
1000 ≤ a_{1}a_{2}a_{3}a_{4} ≤ 9999, etc.

We can prove that X is uncountable with the well-known Cantor diagonal argument. In fact
{a_{1}, a_{1}a_{2},
a_{1}a_{2}a_{3}, a_{1}a_{2}a_{3}a_{4}, ... } →
Σ a_{i} 10^{-i} is (almost) a bijection from X to [0.1,1].

The intersection of two distinct sets of X, if not empty, has always the form
{a_{1}, a_{1}a_{2}, ... ,
a_{1}a_{2}..a_{k}} for some positive integer k, so is always finite.

**Problem 2019-4/A**

*Let F be a monic polynomial of degree 4 with integer coefficients.
Let A be a set of integers with at least 5 elements such that for all a ∈ A holds that 2 ^{2019} divides F(a).
Prove that there exist distinct elements a,a' of A such that 2^{202} divides a - a'.*

__Solution:__

We will show that we can even replace 202 by 504. Indeed, suppose distinct elements a,a' of A
such that 2^{504} divides a - a' don't exist.
We will derive a contradiction as follows:

Suppose F = x^{4} + px^{3} + qx^{2} + rx + s.

There exist 5 elements a_{i} of A, i = 1,2,..,5 , such that 2^{2019} divides
a_{i}^{4} + pa_{i}^{3} + qa_{i}^{2} + ra_{i} + s.

So by subtracting we find 10 pairs i,j such that 2^{2019} divides
(a_{i} - a_{j})(a_{i}^{3} + a_{i}^{2}a_{j} +
a_{i}a_{j}^{2} + a_{j}^{3} + pa_{i}^{2} + pa_{i}a_{j} +
pa_{j}^{2} + qa_{i} + qa_{j} + r), so 2^{1515} divides
a_{i}^{3} + a_{i}^{2}a_{j} +
a_{i}a_{j}^{2} + a_{j}^{3} + pa_{i}^{2} + pa_{i}a_{j} +
pa_{j}^{2} + qa_{i} + qa_{j} + r.

Again by subtracting we find 10 triples i,j,k such that 2^{1011} divides
a_{i}^{2} + a_{j}^{2} + a_{k}^{2} + a_{i}a_{j} +
a_{i}a_{k} + a_{j}a_{k} + pa_{i} + pa_{j} +
pa_{k} + q.

Again by subtracting we find 5 quadruples i,j,k,m such that 2^{507} divides
a_{i} + a_{j} + a_{k} + a_{m} + p.

Again by subtracting we find that 2^{3} divides 1. Contradiction.

**Problem 2019-4/B**

*1. Let n be a positive integer, at least 2, and S a non-empty subset of {1,2,...,n-1}.
Prove that there exists a n-th root of unity z such that the real part of Σ _{s∈S} z^{s} is at
most -1/2.
*

2. Suppose n is not a power of 2. Prove that there exists a non-empty subset S of {1,2,...,n-1} such that for all n-th roots of unity z the real part of Σ_{s∈S} z^{s} is at least -1/2.

__Partial solution:__

1. Let z = exp(2πik/n) = cos(2πk/n) + i sin(2πk/n) where 0 ≤ k < n. Choosing z amounts to choosing k.

If n = 2 then z = -1 satisfies the requirement.

If n ≥ 3 suppose there is a S so that for each k the real part of Σ_{s∈S} z^{s} is greater
than -1/2.

Let S' be the complement of S in {1,2,...,n-1).

Then for each k the real part of Σ_{s'∈S'} z^{s'} is less than -1/2.

This means that for each k there are many s'∈S' such that ks'(mod n) is close to n/2. Contradiction.

2. If n = p where p is an odd prime, then S = {1,2,...,(p-1)/2} satisfies the requirement because then (unless z = 1)
Σ_{s∈S} z^{s} = -1/2 = Σ_{s∈S} z^{-s}.

In general, if n = pm where p is an odd prime, then S = {m,2m,...,m(p-1)/2} satisfies the requirement.

**Problem 2019-4/C**

*Let n be a positive integer. Denote by S _{n} the permutation group on {1,2,...,n}. An element σ ∈
S_{n} is called representable if there exists a polynomial f ∈ Z[X] such that for all x ∈ {1,2,...,n}
we have σ(x) = f(x). What is the number of representable elements of S_{n}?*

__Solution:__

Suppose that σ ∈ S_{n} is represented by
f(X) = Σ_{i=0}^{m} a_{i}X^{i}.

Then for all k ∈ {1,2,...,n} we have σ(k) - σ(1) = f(k) - f(1) =
Σ_{i=0}^{m} a_{i}(k^{i} - 1), so σ(k) - σ(1) is divisible by k-1.

Since σ is a permutation on {1,2,...,n}, there are only two possibilities (dependent on the sign of a_{n}):

either σ(k) = k for all k and f(x) = x, or σ(k) = n+1-k for all k and f(x) = n+1-x.

(If n=1, the two solutions coincide.)

**Problem 2020-1/A**

*
For every positive integer n, we write [n] = {0,1,...,n-1}.
For every integer m, we let
T(m):= m (m+1)/2 be the m-th triangular number. Let τ : [n] → [n] be the map given by
m → T(m) mod n.
a) For which n is τ a permutation?
b) For these n, determine the sign of τ as a function of n.
*

__Complete solution to a) and partial solution to b):__

I did some investigations with the help of a pascal program.

I found n must be a power of 2 and τ is only even for n=1 and for n=2.

a) To prove that n must be a power of 2, suppose n = n_{1}n_{2} for odd n_{1} and
n_{2} a power of 2.

We look for m_{1} and m_{2} with 0 ≤ m_{1} < m_{2} ≤ n-1 and
τ(m_{1}) = τ(m_{2}).

If n_{1} > 1 we find

m_{1} = (2n_{2} - n_{1} - 1 )/2, m_{2} = (2n_{2} + n_{1} - 1 )/2
if 2n_{2} ≥ n_{1} + 1, and

m_{1} = (-2n_{2} + n_{1} - 1 )/2, m_{2} = (2n_{2} + n_{1} - 1 )/2
if 2n_{2} ≤ n_{1} - 1,

so τ is no permutation.

If n_{1} = 1, such m_{1} and m_{2} don't exist, so τ is a permutation.

b) As for the parity of the permutations with n = 2^{k}, we know that T(m) is congruent modulo 2^{k}
to T(2^{k+1}-1-m).

Hence we can prove with induction that the parity is odd for k ≥ 2.

**Problem 2020-1/B**

*
Let G be a finite group of order n and R the set of the real numbers.
A map f: G → R is called a near-homomorphism if for
all x, y ∈ G, we have |f(xy) - f(x) - f(y)| ≤ 1.
a) Show that for every near-homomorphism f from G to R, we have diam(f[G]) :=
sup*

__Partial solution to a) and complete solution to b):__

a) Let G = {x_{1}, x_{2}, ... , x_{n}} with f(x_{1}) ≤ f(x_{2}) ≤ ...
≤ f(x_{n}), so the diameter is f(x_{n}) - f(x_{1}).

For any x∈G we have Σ f(x_{i}) =
Σ f(x_{i}x) =
Σ (f(x_{i}) + f(x) + δ_{i}) =
Σ f(x_{i}) + nf(x) + Σ δ_{i}
with -1 ≤ δ_{i} ≤ 1, so f(x) = -Σδ_{i}/n ∈ [-1,1].

So -1 ≤ f(x_{1}) ≤ f(x_{n}) ≤ 1.

I think diam(f[G]) is maximal if G is cyclic and f as follows in b):

b) Let G be cyclic with generator g.

Then f with f(g^{k}) := (2k - n)/n for k ∈ {0,1,..,n-1} satisfies the requirements.

**Problem 2020-1/C**

*
Let n ≥ 4 be an integer and let A be an abelian group of order 2 ^{n}.
Let σ be an automorphism of A such that the order of σ is a power of 2.
Then the order of σ is at most 2^{n-2}.*

__Solution:__

A is the direct product of the cyclic (additive) groups Z_{2m1}, ...
Z_{2mr} with
m_{1} ≤ ... ≤ m_{r} and m_{1} + ... + m_{r} = n.

Let id be the neutral element of the (multiplicative) automorphism group Aut(A) of A.
We have to prove that σ^{2n-2} = id.

This follows from a theorem of Gausz I found in the literature:
Aut(Z_{2n}) ≅ Z_{2} x Z_{2n-2}.

**Problem 2020-2/B**

*For nonnegative integers a and b let f(a,b) := (2 min(a,b), max(a,b)-min(a,b)).
We call (a,b) equipotent if for some nonnegative integers x and n holds f ^{(n)}(a,b) = (x,x).
Show that if a and b are positive then (a,b) is equipotent if and only if (a+b)/gcd(a,b) is a power of 2.*

__Solution:__

First note that f(a,b) = f(b,a), and we write (a,b) iff a ≥ b.

Now we calculate the n-th predecessor (a,b) of (x,x) for any positive x and n, that is f^{(n)}(a,b) = (x,x).
It will turn out we can do this as long as x is divisible by 2^{n-1}.

Predecessor 0 is (x,x) itself, and then (a+b)/gcd(a,b) = (x+x)/x = 2 is a power of 2.

Predecessor 1 is (u_{1},v_{1}) := (3x,x), and then (a+b)/gcd(a,b) = (3x+x)/x = 4 is a power of 2.

Predecessor 2 is (u_{2},v_{2}) := (5y,3y) with x = 2y, and then (a+b)/gcd(a,b) = (5y+3y)/y = 8 is a
power of 2.

Predecessor 3 is (u_{3},v_{3}) := (11z,5z) with x = 2y = 4z, and then (a+b)/gcd(a,b) = (11z+5z)/z = 16
is a power of 2.

Predecessor 4 is (u_{4},v_{4}) := (21k,11k) with x = 2y = 4z = 8k, and then (a+b)/gcd(a,b)
= (21k+11k)/k = 32 is a power of 2.

Predecessor 5 is (u_{5},v_{5}) := (43m,21m) with x = 2y = 4z = 8k = 16m, and then (a+b)/gcd(a,b) =
(43m+21m)/m = 64 is a power of 2.

Etc. We easily find with induction:

Predecessor n is (u_{n},v_{n}) := ((2^{n+1}-s) x/2^{n-1}, s x/2^{n-1})
where s = u_{n-1} 2^{n-2}/x. Then (a+b)/gcd(a,b) = 2^{n+1} is a power of 2.

On the other hand, if (a+b)/gcd(a,b) = 2^{n+1}, then we can find x,s such that
(a,b) = ((2^{n+1}-s) x/2^{n-1}, s x/2^{n-1}) and then the n-th successor of (a,b) is (x,x).

Indeed, x := gcd(a,b) 2^{n-1}, s := b/gcd(a,b).

**Problem 2020-2/C** (*)

*Uncle Donald cuts a 3 kg piece of cheese in an arbitrary, finite
number n of pieces of arbitrary weights. He distributes them uniformly randomly among his nephews
Kwik, Kwek, and Kwak.
Prove or disprove: the probability that two of the nephews each get strictly more
than 1 kg is at most two thirds.
*

__Numerical solution:__

For n=1 the probability is 0.

For n=2 the probability would be 1/3 if uncle Donald could choose all weights x and 3-x with x ∈ [0,3].
Indeed, if and only if he chooses an x ∈ (1,2), two of the nephews each get more than 1 kg (since both x and 3-x are greater than
1), and one gets nothing.

However, in reality only a finite number of x can occur, due to the limited capacities of uncle Donald's brain, eyes
and hands.
(I'm using my electronic calculator as a model of uncle Donald's brain.) But then these
possible x, including x=1 and x=2, have a positive chance to be chosen, so the probability
for n=2 is less than 1/3.

For n=3, the nephews may mould their cheese into three cords of equal diameter whose lengths add up to 3 units.
So uncle Donald could as well have cut a cord of length 3 at two random points x and y with 0 ≤ x ≤ y ≤ 3
and distributed the three pieces with lengths x, y-x, 3-y among his nephews.

Now if Donald could choose all pairs (x,y) then the probability that two of the lengths
are greater than 1 is 1/3 (see the picture below).

In reality, he can choose only a finite number of pairs (x,y). These pairs have a positive chance to be chosen, so the
probability for n=3 is less than 1/3.

I wrote a pascal program simulating Donald's action with n pieces for 1 ≤ n ≤ 3000.

The program includes a procedure that generates n random positive numbers that add up to 3,
with the help of the well known subroutine bubblesort:

program duckbrain;

var j,k,m,n,p,q,max:integer; som,t,gok,kwik,kwek,kwak:real; hulp,stuk:array[0..3000] of real;

begin

max:=0; som:=0;

for n:=1 to 3000 do

begin

m:=0;

for k:=1 to 100 do

begin

for j:=1 to n-1 do hulp[j]:=random;

for p:=n-1 downto 2 do

for q:=1 to p-1 do

if hulp[q]>hulp[p] then

begin t:=hulp[p]; hulp[p]:=hulp[q]; hulp[q]:=t end;

hulp[0]:=0; hulp[n]:=1;

for j:=1 to n do stuk[j]:=3*(hulp[j]-hulp[j-1]);

kwik:=0;kwek:=0;kwak:=0;

for j:=1 to n do

begin

gok:=random;

if gok<1/3 then kwik:=kwik+stuk[j]
else if gok<2/3 then kwek:=kwek+stuk[j] else kwak:=kwak+stuk[j]

end;

if ((kwik>1) and (kwek>1)) then m:=m+1;

if ((kwik>1) and (kwak>1)) then m:=m+1;

if ((kwek>1) and (kwak>1)) then m:=m+1

end;

if m>max then max:=m; som:=som+m;

writeln(n:4,m/100:13:2);

end;

writeln('maximum ',max/100:13:2,' gemiddelde: ',som/300000:13:6); readln

end.

The output shows that the probability, as a function of n, fluctuates about a parabola with maximum 0.66
for n = 1636.

The average probability for 1 ≤ n ≤ 3000 is 0.48937 .

These results support my conclusion that the probability asked for is less than 2/3.

I tried to generalize:

Suppose uncle Donald would cut A kg of cheese in n pieces and divide them randomly among A nephews,
what is the maximum probability that A-1 nephews each get more than 1 kg and for which n is this maximum attained?

I ran a modified program and found the following output:

A=4, max 0.29, n=956

A=5, max 0.13, n=549

A=6, max 0.05, n=691

A=7, max 0.02, n=192

A=8, max 0.01, n=118.