Solutions by H Reuvers

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)cc+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*21/(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 ∫0s 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 Am. Suppose m is odd. Prove that 2Am and A2m have the same minimal polynomial.

Solution:

We find Am = (m/2)*sin(2π/m).
Let y1 = A2m = m*sin(π/m) and y2 = 2Am = m*sin(2π/m). Let x1 = m*cos(π/m) and x2 = m*cos(2π/m).
According to de Moivre, (cos(φ) + i sin(φ))k = cos(kφ) + i sin(kφ), so Im(x1 + i y1)m = 0 and Im(x2 + i y2)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 = x1 + i y1 and for x + iy = x2 + i y2 we have also
Im(x + i y)m = Im (Σk=0m (m over k) xm-k (iy)k) = m yxm-1 - (m over 3) y3xm-3 + ... ± ym, where the exponents of x are all even.
Using cos2 = 1 - sin2, we can turn this into y times the minimal polynomial p(y) over the rationals, which is the same for y = y1 and y = y2.
For instance, for m=3 we get p(y) = 27 - 4y2 and for m=5 we get 3125 - 500y2 + 16y4.

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 p1a1...pkak with p1 ≤ ... ≤ pk. 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(p1-1)..(pk-1) = p1..pk.
Comparing the number of factors 2 at the left and right hand sides, we establish p1 = 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 p2 must be 3.
We now distinguish between the cases k=1 and k=2.
1) Let k=1, so n = 2a and m=2. So there are exactly two cyclic subgroups of order 2a.
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 C4 and C2, where Cs is cyclic of order s.
2) Let k=2, so n = 2a3b and m=3. There are several groups with 6 elements of order 6, for instance the direct product C3*C2*C2.
So the statement in the problem holds if n is prime, but not in general.

Problem 2019-2/A (edited)

Let A = (ai,j ) be the matrix on the natural base e in threedimensional euclidean space of a rotation R (not equal to identity). Suppose none of a2,3+a3,2, a1,3+a3,1, a1,2+a2,1 is 0.
Prove that (1/(a2,3+a3,2), 1/(a1,3+a3,1), 1/(a1,2+a2,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 m1,1 = 1, m1,2 = m1,3 = m2,1 = m3,1 = 0, m2,2 = m3,3 = cos(u), m3,2 = - m2,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 ai,j of A in cos(u), sin(u) and the matrix elements sm,n of S.
Now we have to prove that s1,1(a2,3+a3,2) = s2,1(a1,3+a3,1) = s3,1(a1,2+a2,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
s1,1 = cos(v)cos(w), s1,2 = - sin(v)cos(w), s1,3 = - sin(w),
s2,1 = cos(v)sin(w), s2,2 = - sin(v)sin(w), s2,3 = cos(w),
s3,1 = sin(v), s3,2 = cos(v), s3,3 = 0.

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 {a1, a1a2, a1a2a3, a1a2a3a4, ... }, where ai ∈ {0,1,2,...,9} (a1 > 0) and we use the decimal representation, so for instance 1000 ≤ a1a2a3a4 ≤ 9999, etc.
We can prove that X is uncountable with the well-known Cantor diagonal argument. In fact {a1, a1a2, a1a2a3, a1a2a3a4, ... } → Σ ai 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 {a1, a1a2, ... , a1a2..ak} 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 22019 divides F(a).
Prove that there exist distinct elements a,a' of A such that 2202 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 2504 divides a - a' don't exist. We will derive a contradiction as follows:

Suppose F = x4 + px3 + qx2 + rx + s.
There exist 5 elements ai of A, i = 1,2,..,5 , such that 22019 divides ai4 + pai3 + qai2 + rai + s.
So by subtracting we find 10 pairs i,j such that 22019 divides (ai - aj)(ai3 + ai2aj + aiaj2 + aj3 + pai2 + paiaj + paj2 + qai + qaj + r), so 21515 divides ai3 + ai2aj + aiaj2 + aj3 + pai2 + paiaj + paj2 + qai + qaj + r.
Again by subtracting we find 10 triples i,j,k such that 21011 divides ai2 + aj2 + ak2 + aiaj + aiak + ajak + pai + paj + pak + q.
Again by subtracting we find 5 quadruples i,j,k,m such that 2507 divides ai + aj + ak + am + p.
Again by subtracting we find that 23 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 zs 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 zs 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 zs 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' zs' 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 zs = -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 Sn the permutation group on {1,2,...,n}. An element σ ∈ Sn 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 Sn?

Solution:

Suppose that σ ∈ Sn is represented by f(X) = Σi=0m aiXi.
Then for all k ∈ {1,2,...,n} we have σ(k) - σ(1) = f(k) - f(1) = Σi=0m ai(ki - 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 an):
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 = n1n2 for odd n1 and n2 a power of 2.
We look for m1 and m2 with 0 ≤ m1 < m2 ≤ n-1 and τ(m1) = τ(m2).
If n1 > 1 we find
m1 = (2n2 - n1 - 1 )/2, m2 = (2n2 + n1 - 1 )/2 if 2n2 ≥ n1 + 1, and
m1 = (-2n2 + n1 - 1 )/2, m2 = (2n2 + n1 - 1 )/2 if 2n2 ≤ n1 - 1,
so τ is no permutation.
If n1 = 1, such m1 and m2 don't exist, so τ is a permutation.

b) As for the parity of the permutations with n = 2k, we know that T(m) is congruent modulo 2k to T(2k+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]) := supx,y ∈ G |f(x) - f(y)| ≤ 2 - 2/n.
b) Show that if G is cyclic, then there exists a near-homomorphism f: G → R with diam(f[G]) = 2 - 2/n.

Partial solution to a) and complete solution to b):

a) Let G = {x1, x2, ... , xn} with f(x1) ≤ f(x2) ≤ ... ≤ f(xn), so the diameter is f(xn) - f(x1).
For any x∈G we have Σ f(xi) = Σ f(xix) = Σ (f(xi) + f(x) + δi) = Σ f(xi) + nf(x) + Σ δi with -1 ≤ δi ≤ 1, so f(x) = -Σδi/n ∈ [-1,1].
So -1 ≤ f(x1) ≤ f(xn) ≤ 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(gk) := (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 2n. Let σ be an automorphism of A such that the order of σ is a power of 2. Then the order of σ is at most 2n-2.

Solution:

A is the direct product of the cyclic (additive) groups Z2m1, ... Z2mr with m1 ≤ ... ≤ mr and m1 + ... + mr = 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(Z2n) ≅ Z2 x Z2n-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 2n-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 (u1,v1) := (3x,x), and then (a+b)/gcd(a,b) = (3x+x)/x = 4 is a power of 2.
Predecessor 2 is (u2,v2) := (5y,3y) with x = 2y, and then (a+b)/gcd(a,b) = (5y+3y)/y = 8 is a power of 2.
Predecessor 3 is (u3,v3) := (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 (u4,v4) := (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 (u5,v5) := (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 (un,vn) := ((2n+1-s) x/2n-1, s x/2n-1) where s = un-1 2n-2/x. Then (a+b)/gcd(a,b) = 2n+1 is a power of 2.

On the other hand, if (a+b)/gcd(a,b) = 2n+1, then we can find x,s such that (a,b) = ((2n+1-s) x/2n-1, s x/2n-1) and then the n-th successor of (a,b) is (x,x).
Indeed, x := gcd(a,b) 2n-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; 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;
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.