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 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]:=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.


Problem 2021-2/A

A hot frying pan contains 22021 potato slices. Each time we toss the slices, each slice has a chance of 0.5 to land on its other side. These probabilities are individually independent. How often do we need to toss the slices so that with probability at least 0.5 all slices will have lain on both sides?

Solution:

Suppose n is the answer. Then, since for each slice the chance to land on the same side all n times is (1/2)n, we must have
(1-(1/2)n)22021 ≥ 0.5 and (1-(1/2)n-1)22021 < 0.5.
Now since (1-1/t)t → 1/e for t → ∞, (1-1/t)t will for large t be close to 1/e.
This also holds for t = 22021 and for t = 22022, so we find that (1-(1/2)2021)22021 and (1-(1/2)2022)22022 both are close to 1/e, which is smaller than 0.5.
Then (1-(1/2)2022)22021= (1-(1/2)2022)22022-1 = (1-(1/2)2022)220222-1 is close to (1/e)2-1 = 1/√e, which is greater than 0.5.
So n=2022 is the answer.


Problem 2021-3/A

Write T = (Z/8Z)2 for the torus chessboard. For every square t ∈ T its neighbours are the squares in the set {t+d/d∈D} for D = {-1,0,1}2\{(0,0)}. A line is a set of squares of the form {t+nd/n∈Z} for t∈T and d∈D.
Disprove or give an example of the following assertion: There exists a pairing of neighbouring squares, i.e. a partitioning of T into pairs {s,t} of two neighbours, such that every line contains a pair.

Partial solution:

There are 64 squares on the board. There are 32 lines: 8 running to the east (or west), 8 to the north-east (or south-west), 8 to the north (or south), 8 to the north-west (or south-east). Notice that a line may continue at an other side of the board, and neighbouring squares may sit at distinct sides of the board.
First we paint all 64 squares white. Then we choose on each of the 32 lines a pair of two neighbours, and paint them black. If these 32 chosen pairs cover T, so all 64 squares are black now, we have found a pairing as required (if we wrote down all relevant coordinates).
I wrote a program which simulates this procedure as often as we want. After ten hours of running, it gave no pairing as required as yet. Perhaps we'd better try and prove there is no such pairing.
The listing of the program is as follows:

program board;
var m,n,t1,t2,t3,t4,p,q,r,s,u,v:integer; a:array[0..7,0..7] of 0..1; partitie:boolean;
begin
  while true do
  begin
    for m:=0 to 7 do for n:=0 to 7 do a[m,n]:=0;
    for t1:=0 to 7 do begin p:=random(8); u:=t1; v:=p; a[u,v]:=1; a[u,(v+1) mod 8]:=1; write(u:2,v:2,'*') end; writeln;
    for t2:=0 to 7 do begin q:=random(8); u:=q; v:=t2; a[u,v]:=1; a[(u+1) mod 8,v]:=1; write(u:2,v:2,'*') end; writeln;
    for t3:=0 to 7 do begin r:=random(8); u:=(t3+r) mod 8; v:=r mod 8; a[u,v]:=1; a[(u+1) mod 8,(v+1) mod 8]:=1;
      write(u:2,v:2,'*') end; writeln;
    for t4:=0 to 7 do begin s:=random(8); u:=(t4+8-s) mod 8; v:=s mod 8; a[u,v]:=1; a[(u+7) mod 8,(v+1) mod 8]:=1;
      write(u:2,v:2,'*') end; writeln; writeln;
    partitie:=true;
    for m:=0 to 7 do for n:=0 to 7 do if a[m,n]=0 then partitie:=false;
    if partitie then begin writeln('gevonden!'); readln end
  end
end.

We may also try and paint on each of the 32 lines a pair of neighbour squares with one of four colors, dependent on the direction.


Problem 2021-3/B

Write φ for the Euler totient function. Determine all infinite sequences {an} of positive integers satisfying an = φ(an+1) for all n.

Partial solution:

An example of a solution is 1,1,1,1,2,4,8,16,32,...



HOME