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.



HOME