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.


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 {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 permations 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.



HOME