Solutions by H Reuvers


I submitted solutions for 30 problems of Nieuw Archief voor Wiskunde:
2005-2/C, 2006-4/AB, 2007-1/AB, 2007-2/C, 2007-4/A, 2008-1/A, 2011-3/A, 2014-1/C, 2014-3/ABC, 2014-4/A, 2015-2/A, 2015-3/ABC, 2015-4/A, 2016-1/C, 2016-2/(A)B(C), 2017-1/AC, 2017-2/A, 2017-3/A(C), 2017-4/ABC, 2018-1/A(BC).
Most of them have already been recognized by NAW.
Here are some of them, and some partial solutions.
I was awarded book tokens for 2011-3/A, 2014-3/C, 2015-3/C, 2016-2/C and 2017-4/A.

The problem section of NAW came to a stop in september 2018.
NAW still has to review the submitted solutions of 2018-1 and 2018-2.
I submitted 2018-1/A(BC) (see nawdoor ) and 2018-2/(A)B(C) (see nawfloor ).
In any case, NAW still has to send me the awarded book token for 2017-4/A.


Problem 2011-3/A

Fix a point P in the interior of a face of a regular tetrahedron Δ. Show that Δ can be partitioned into four congruent convex polyhedra such that P is a vertex of one of them.

Solution:

Let A,B,C,D be the vertices of Δ and suppose P is an arbitrary point in the interior of face ABC.
P is determined by its distances λ, μ, ν to A,B,C resp.
Let us fix three more points so that on each face we have one of the four fixed points and each of A,B,C,D is at distance λ from one of them, at distance μ from another one, and at distance ν from a third one:

Let TABC be the point on face ABC at distances λ, μ, ν to A,B,C resp. (So TABC = P.)
Let TBCD be the point on face BCD at distances λ, μ, ν to C,D,B resp.
Let TCDA be the point on face CDA at distances λ, μ, ν to D,C,A resp.
Let TDAB be the point on face DAB at distances λ, μ, ν to B,A,D resp.

So δ := TABCTBCDTCDATDAB is also a regular tetrahedron. Let O be its center.

Now we will allot points of Δ to each X ∈ {A,B,C,D} in such a way that the points allotted to X form a convex polyhedron, and such that the four polyhedra are congruent and form a partition of Δ.
The allotment will first be done in two steps:

Step 1)
The points in the hexahedron ATABCTCDATDABO belong to A.
The points in the hexahedron BTABCTBCDTDABO belong to B.
The points in the hexahedron CTABCTBCDTCDAO belong to C.
The points in the hexahedron DTBCDTCDATDABO belong to D.

Step 2)
To allot the remaining points in the interior of Δ while preserving convexity and congruence, we extend (to the exterior of δ) the six planes through O and a side of δ that bisect the angles between two faces of δ.
Through each vertex of δ there go three of these bisectrix planes.
Now for each X ∈ {A,B,C,D}, allot to X all remaining points y ∈ Δ such that, for each plane through O and a side of the nearest face of δ, X and y are at the same side of that plane.

Of course, we can sum it all up, including both steps 1 and 2, as follows:
For each X ∈ {A,B,C,D}, allot to X all points y ∈ Δ such that, for each plane through O and a side of the nearest face of δ, X and y are at the same side of that plane.


Problem 2013-2/A revised (to make it a bit simpler)

We have two hourglasses, A for a seconds and B for b seconds, where a and b are relatively prime positive integers.
Let t be an integer with t ≥ ab. Show that A and B can be used to identify the time t if the upper bulbs are empty at the start.

Solution:

We will find non-negative integers p and q such that pa + qb = t, which is clearly sufficient for our purpose, as follows;
Since a and b are coprime, there exist positive integers m and n such that mb - na = 1 (or mb - na = -1, then reverse the roles of a and b).
So for any positive integer s we have (tm-sa)b + (sb-tn)a = t.
If we can find such s within [tn/b,tm/a] = [tn/b, tn/b + t/ab], we can take p = tm-sa, q = sb-tn, and then we are finished.
Now if t ≥ ab, then this interval has length ≥ 1, so then we can find in it this positive integer s.


Problem 2014-4/A

Let k be an integer, at least 4. Determine the variance of the greatest common divisor of k positive integers.
Here we mean the limit, as n → ∞, of the variance of the greatest common divisor of k integers in {1,2,...,n} with respect to the uniform distribution on {1,2,...,n}k.

Solution:

We find the probability that d is gcd is (1/dk)*Πp prime(1 - 1/pk) = 1/(dk*ζ(k)).
So the expectation value of the gcd is Σd=1 d/(dk*ζ(k)) = ζ(k-1)/ζ(k).
So the variance of the gcd is Σd=1 (d - ζ(k-1)/ζ(k))2/(dk*ζ(k)) = (ζ(k)*ζ(k-2) - ζ(k-1)2)/ζ(k)2.

(The formula for the probability means: that the k integers are divisible by d and, after division by d, for each prime p, not all of them divisible by p.)


Problem 2016-1/C

Determine all two-sided infinite sequences of positive integers in which each number is the Euler-φ of the next.

Solution

If n has prime factorization p1a1p2a2...pkak then φ(n) = p1a1-1p2a2-1...pkak-1(p1-1)(p2-1)...(pk-1).

Since for n larger than 1 we find φ(n) smaller than n, such a sequence must begin with infinitely many 1's.
We may terminate these 1's at the left hand side of the sequence by replacing the last 1 by 2, which is the only other number whose φ is 1.
If we do that, then in the next position after 2 we can put only 22 or 2*3. We can't put 3, because there would be no option for the next position after the 3.
Now if at some position we have 2s, then in the next position we can only put 2s+1 or 2s3. For example, we can't put 2s-15 or 2s-317, for, going further to the right, we would soon run out of factors 2.
And if at some position we have 2s3t, then in the next position we can only put 2s3t+1. For example, we can't put there 2s-13t7, because we would again run out of options for lack of factors 2 after a few steps to the right.
So this sums up all possible sequences.


Problem 2016-2/B: Suppose there are N ≥ 2 players, labeled 1,2,..,N, and each of them holds precisely m ≥ 1 coins of value 1, m coins of (integer) value n ≥ 2, m coins of value n2, etc.
A transaction from player i to player j consists of player i giving a finite number of his coins to player j.
We say an N-tuple (a1,a2, ... ,aN) of integers is (m,n)-payable if Σi=1,2,..,N ai = 0 and after a finite number of transactions the i-th player has received (in value) ai more than he has given away.
Show that for every N-tuple (a1,a2, ... ,aN) with Σi=1,2,..,N ai = 0 to be (m,n)-payable, it is necessary and sufficient that m > n - n/N - 1.

Solution

The inequality can be rewritten as (n-1)(N-1) ≤ mN.
This is the necessary and sufficient condition that for each k the mN coins can be redistributed so that all but one players at the end have up to n-1 coins of worth nk for each k, thus covering in the n-ary system all values of possession.
(The player who paid the most holds the rest of the total value.)

Problem 2016-2/C: For each integer n ≥ 1, let cn be the largest real number such that for any finite set of vectors X ⊂ ℜn with Σv∈X |v| ≥1 there exists a subset Y ⊆ X with |Σv∈Y v| ≥ cn.
Prove the recurrence relation c1 = 1/2, cn+1 = 1/(2πn cn).

Solution:

For each n we seek X ⊂ ℜn with Σv∈X |v| ≥1 for which the maximum of |Σv∈Y v| with Y ⊆ X is as small as possible.
For this we consider X consisting of an even number of vectors of equal length whose directions are as distinct as possible and whose lengths add up to 1.
The corresponding best Y consists of the half of these vectors whose directions are as much the same as possible.

For n=1 we consider X = {1/2,-1/2} and Y={1/2}. We find c1 = 1/2.

For n=2 we consider X consisting of 2m vectors (cos(kπ/m),sin(kπ/m))/(2m), k=0,1,..,m-1,m,..,2m-1, and Y consisting of the first m of these vectors of X, so with k=0,1,..,m-1.
We use complex numbers to calculate c2 and find |Σk=0,..,m-1 eikπ/m|/(2m) = |(eimπ/m - 1)/(eiπ/m - 1)|/(2m) = 1/(2m sin(π/(2m))) → 1/π = c2 for m → ∞.

Now it's sufficient to prove cn+2 = (n/(n+1)) cn.
The step from X and Y in ℜn to X' and Y' in ℜn+2 can be made by replacing each of all p vectors v ∈ X (of length 1/p) by 2m vectors v' = (pnv/(n+1) + (√(2n+1)/(n+1))(cos(kπ/m)em+1 + sin(kπ/m)em+2))/(2pm), k=0,1,..,2m-1, (of length 1/(2pm) = 1/p'), where the ei form the orthonormal base in ℜn(+2). Then Σv'∈Y' v' = (n/(n+1)) Σv∈Y v.

Explanation of the factor n/(n+1) in pnv/(n+1):
When making new directions by adding orthogonal adjustments to the old directions, in order to keep the directions as distinct as possible (so having maximal variance), we must weigh the old direction vectors with factor cos(ψ) = n/(n+1). Then sin(ψ) = √(2n+1)/(n+1).

Problem 2016-4/A: For a finite sequence s = (s1, s2, ... , sn) of positive integers, denote by p(s) the number of ways to write s as a sum s = Σi=1n aiei + Σj=1n-1 bj(ej+ej+1) with all ai and bj non-negative.
Here ei denotes the sequence of which the i-th term is 1 and of which all the other terms are 0.
Show that there exists an integer B > 1 such that for any product F of (positive) Fibonacci numbers, there exists a finite sequence s = (s1, s2, ... , sn) with all si ∈ {1,2,..,B} such that p(s) = F.

Partial solution:

If n=1 we only have the equation a1 = s1, so p(s)=1.
If n=2 we only have the equations a1 = s1 - b1, a2 = s2 - b1, so 0 ≤ b1 ≤ min(s1,s2) and p(s) = min(s1,s2) + 1.
This equals F iff min(s1,s2) = F-1, but then the terms of s aren't bounded by an integer B > 1.
If n=3 we have a1 = s1 - b1, a2 = s2 - b1 - b2, a3 = s3 - b2, so p(s) = Σb1=0s1 Σb2=0min(s3,s2-b1) 1.
If n ≥ 4 we have a1 = s1 - b1, a2 = s2 - b1 - b2, ... , an-1 = sn-1 - bn-2 - bn-1, an = sn - bn-1, so p(s) = Σb1=0s1 Σb2=0s2-b1 ... Σbn-2=0sn-2-bn-3 Σbn-1=0min(sn,sn-1-bn-2) 1.
Especially, if s(n) is a row of n ones, we find: p(s(1)) = 1, p(s(2)) = 2, p(s(3)) = Σb1=01 Σb2=01-b1 1 = 3, and for n≥4
p(s(n)) = Σb1=01 Σb2=01-b1 ... Σbn-2=01-bn-3 Σbn-1=01-bn-2 1 = {taking b1 = 0 and b1 = 1} = p(n-1) + p(n-2).
So by induction we find p(s(n)) = Fn, that is the n-th Fibonacci number.
Now clearly if F = Ft1*Ft2* ... *Ftk is any product of k ≥ 1 Fibonacci numbers > 1, then F = p(s) where s is the concatenation (s(t1),0,s(t2),0, ... , 0,s(tk)).
But how do we get rid of the zeroes?


Problem 2017-1/A: Reconstruction. Suppose you get to know the n midpoints of the n edges of a polygon. Can you determine the polygon?

Solution:

Let the vertices of the polygon in the complex plane be denoted by a1, a2, ... , an, with n > 2.
Given z1 = (a1 + a2)/2, z2 = (a2 + a3)/2, ... , zn = (an + a1)/2, we have to find a1, a2, ... , an.

With the usual method of solving linear equations, we find:
1) If n is odd, then ai = zi - zi+1 + zi+2 - ... + zi+n-1 (i=1,2,..,n, indices modulo n).
2) If n is even then we must have zn = z1 - z2 + z3 - ... + zn-1, or the given set of midpoints would be false. We have n-1 independent linear equations in a1, a2, ... ,an. If we would take an = 2a as we like, we would find an-1 = 2zn-1 - 2a, an-2 = 2zn-2 - 2zn-1 + 2a, ... , a1 = 2z1 - 2z2 + 2z3 - ... + 2zn-1 - 2a.

We conclude: if n is odd, we can reconstruct the original polygon, but if n is even we only find the original polygon if we happen to take a = an/2, where an is the n-th vertex of the original polygon.


Problem 2017-1/B: Large is odd. Let G be a graph with vertices V and edges E. A subset U of V is called large if every vertex that is not in U has a neighbour in U. Prove that the number of large subsets is odd.

Partial solution:

First notice that the number of large subsets is the product of the numbers of large subsets in maximal connected subgraphs. Therefore we need only consider the case that G is connected, which we henceforth assume.

Apart from the trivial cases wherein G has only one or two vertices, there is at least one vertex of degree greater than 1.
We are going to use induction to the number n of vertices of degree at least 2.

If n = 1 then G is a flower with 1 center v and k ≥ 2 leaves. In this case, every subset that includes v is large, and the only large subset that doesn't include v must include all the end points of the leaves. So the number of large subsets is 2k+1, which is odd.

Now suppose the proposition is true if n ≤ m.
Consider a connected graph with n=m+1 vertices of degree greater than 1.
Put aside a vertex w of degree greater than 1 with a minimal number of connections to vertices of degree greater than 1, together with the vertices of degree 1 w is connected to and all the edges with w as an endpoint.
By induction hypothesis, the remaining part of the graph has an odd number of large subsets. We are going to show that if we put back the removed part then the following two facts hold so we can do the induction step:
1) Each of these large subsets of the remaining part can in an odd number of ways be strictly extended to a large subset of the original graph.
2) The number of large subsets of the original graph whose restriction to the remaining part is not large in the remaining part is even.
Indeed:
1) Such a strict extension can be made by either including w and excluding or including at random vertices of degree 1 connected to it, or excluding w and including all vertices of degree 1 connected to it. This yields the odd number 2k+1 of strict extensions if there are k ≥ 1 vertices of degree 1 connected to w, and the odd number 1 of strict extensions if there are no vertices of degree 1 connected to w.
2)


Problem 2017-1/C: Meanders. Let n be an even number. Consider the integers 1 to n in the complex plane and connect them by semicircles with center (n+1)/2 in the upper half plane. Let n = a+b for even numbers a and b. Connect the first a integers by semicircles around (a+1)/2 in the lower half plane. Similarly, connect the final b integers by semicircles around a + (b+1)/2 in the lower half plane. The resulting curve or set of curves is a meander. For which a and b is it connected?

Solution:

Let a=2p and b=2q and p ≥ q. Consider the following operations:
A) Connecting r with 2p+1-r for 1 ≤ r ≤ 2p (by drawing a semicircle below at the left hand side).
B) Connecting s with 2p+2q+1-s for 1 ≤ s ≤ 2p+2q (by drawing a semicircle above from the left to the right or vice versa).
C) Connecting t with 4p+2q+1-t for 2p+1 ≤ t ≤ 2p+2q (by drawing a semicircle below at the right hand side).
Subsequently we perform an operation of type A or C and an operation of type B without taking the pencil from the paper, starting at 1. The meander is connected if and only if we meet all numbers 1 to n this way.

We notice that if p and q have a common divisor d then by each operation we connect an integer u with an integer v where v = 1-u (mod d), so if u = 1 (mod d) then v = 0 (mod d) and vice versa. So, starting with 1, we meet only integers w that are congruent to 0 or 1 (mod d). So in this case, if d is greater than 2, the meander is not connected.

In general, starting with 1, we meet subsequently numbers that are congruent mod 2p+2q to: 1, 2p, 1-2p, 4p, 1-4p, 6p, etc. Now we meet all numbers 1 to n = 2p+2q if and only if the first n numbers in this sequence are distinct modulo 2p+2q. Since an even and an odd number can't be congruent modulo 2p+2q, this is only false if 2kp = 2mp (mod 2p+2q) and hence kp = mp (mod p+q) for some distinct k and m in the range from 1 to p+q. This occurs if and only if gcd(p,q) ≥ 2, so in this case the meander is disconnected. But if gcd(p,q)=1, the meander is connected.


Problem 2017-2/A:
Show that there are no infinite antichains for the partial order ≤ on ℵk defined by (x1,x2,...,xk) ≤ (y1,y2,...,yk) iff xi ≤ yi for all i, 1≤i≤k.

Solution:

Recall an antichain is a set S of at least two elements of ℵk such that any two distinct members p,q of the set are incomparable, so neither p ≤ q nor q ≤ p.
Since ℵk is countable, the elements of S can be numbered s1, s2, ...

We proceed with induction.

If k=1 the partial order is total. Any two natural numbers p,q are comparable, so in this case there don't exist antichains, let alone infinite antichains.
So the proposition holds for k=1.

Let k>1. Our induction hypothesis is that the proposition holds for each smaller k .

Assume there exists an infinite antichain S = {s1, s2, ...}. We have to show this contradicts the induction hypothesis.

Because s1 is incomparable with each other element of S, for each s ∈ S there must exist i,j with 1 ≤ i, j ≤ k and i≠j such that s1i < si and s1j > sj.
Moreover, since S is infinite and {1,2,..,k} finite, there must exist such i,j such that s1i < si and s1j > sj for infinitely many s.

But there are only finitely many natural numbers smaller than s1j, so there must exist an infinite subset S' of S whose members all have the same j-th coordinate.
Now by taking the j-th coordinate away, we derive from S' an infinite antichain in ℵk-1, which contradicts the induction hypothesis.


Problem 2017 3-A:
Let n be a natural number and suppose that A1, A2, ... , An are different subsets of {1,2,...,n}.
Prove that there is a k ∈ {1,2,..,n} such that A1\{k}, A2\{k}, ... , An\{k} are different.

Solution:

We use induction to n.
The statement is clearly true for n=1.
Now suppose the statement is true for some n.
Suppose A1, A2, ... , An+1 are different subsets of {1,2,...,n+1}.
If A1\{n+1}, A2\{n+1}, ... , An+1\{n+1} are different, we are finished.
Otherwise, for one or more disjoint unordered pairs {i,j}, Ai\{n+1} and Aj\{n+1} are equal, whereas one of Ai and Aj contains n+1 and the other doesn't.
By forgetting for a moment, for each of these pairs, one of the two equal sets Ai\{n+1} and Aj\{n+1}, we reduce the list to m ≤ n different subsets B1, B2, ... , Bm of {1,2,..,n}.
By induction hypothesis, there is a k ∈ {1,2,..,n} such that B1\{k}, B2\{k}, ... , Bm\{k} are different. (Of course, this also holds if m < n.)
Now for each Bp that equals Ai\{n+1} = Aj\{n+1} for distinct i and j, Ai\{k} and Aj\{k} are different since one of them contains n+1 and the other doesn't.
So A1\{k}, A2\{k}, ... , An+1\{k} are different.

Notice that by looking at the complements we can prove a similar statement with '∪' instead of '\'.


Problem 2017 3-C:
Determine all n ∈ ℕ such that 2n-1 divides 3n-1.

Partial solution:

First we see that n=1 is a solution. We want to show it's the only solution.
Suppose n > 1 and 2n-1 divides 3n-1.
If n is even then 2n-1 is divisible by 3, whereas 3n-1 is not, so n must be odd.
In general, if 2n-1 is divisible by some prime q and 3n-1 is not, then n can't be a solution.
For instance, if n is a multiple of 3, and hence congruent to 3 mod 6 since n is odd, then 2n-1 is divisible by 7, whereas 3n-1 is not, so n can't be a multiple of 3.
If n is a multiple of 5, and hence congruent to 5 mod 30 or to 25 mod 30 since n is no multiple of 2 and no multiple of 3, then 2n-1 is divisible by 31, whereas 3n-1 is not, so n can't be a multiple of 5.
If n is a multiple of 7, and hence congruent to 7 mod 42 or to 35 mod 42 since n is no multiple of 2 and no multiple of 3, then 2n-1 is divisible by 127, whereas 3n-1 is not, so n can't be a multiple of 7.
I think we can continue with induction as follows:
Assume n is not divisible by the first k primes, and let p be the k+1-st prime.
Suppose n is a multiple of p, so p is the smallest prime divisor of n.
For statistical reasons, there must exist some prime q with p dividing q-1 such that 2n-1 is divisible by q, whereas 3n-1 is not divisible by q.
So n can't be divisible by p, either.
So with induction we conclude that n can't be divisible by any prime.


Problem 2017-4/A:
Consider two identical bags of stones, all having integral weights. No two weights in a bag are the same. Suppose that the stones from these two bags are divided into proper subsets of equal cardinality and equal total weight. No two weights in a subset are the same. Is it then possible to readjust this division so that each subset contains only stones from the same bag?

Solution:

This is not always possible.

For instance, let each bag contain stones of weights 1,2,3,4,5,6.
If we divide the twelve stones from the two bags into three subsets of cardinality four and total weight fourteen, without putting two stones of equal weight in the same subset, then these subsets can only contain stones of weights 1,2,5,6 and 1,3,4,6 and 2,3,4,5, respectively.
But then at least one of these subsets must contain two stones from either bag.


Problem 2017-4/B:
Let H1, H2, ... , Hk be k planes in R3. Prove that the unit ball contains an open ball of radius 1/(k+1) which does not intersect any of the planes.

Solution:

The planes divide the unit ball in one or more parts. The maximal radius of an open ball in such a part that doesn't intersect any of the planes is minimal iff the planes are all parallel and divide the diameter they are perpendicular to in k+1 equal segments. Then this radius is 1/(k+1).


Problem 2017-4/C:
Suppose that a,b,n,m are integers, and that m,n are positive, such that an ≡ bn ≡ -1 mod m.
Prove there exists an integer c such that ab ≡ c2 mod m.
Also provide a fast method to compute such c which works even if the prime factors of m are unknown.

Solution:

First we note that gcd(a,m)=gcd(b,m)=1.

Suppose ab is a nonresidue mod m. Gausz already showed then one of the following two must hold:
1) either there exists an odd prime p dividing m such that ab is a nonresidue mod p
2) or there exists a positive integer d such that 2d divides m and ab is a nonresidue mod 2d.
We will derive contradictions in both cases.

1) In the first case:
Let δ be a primitive element of GF(p), so -1 = δ(p-1)/2 and without loss of generality a = δ2k+1, b = δ2j for some nonnegative integers k and j.
Then there must exist nonnegative integers s and t such that (2k+1)n = (2s+1)(p-1)/2 and 2jn = (2t+1)(p-1)/2.
But here the right hand sides have the same number of factors 2, whereas the left hand sides don't.

2) In the second case:
If d=1 then ab can't be a nonresidue mod 2d.
If d=2 then, since gcd(a,m)=gcd(b,m)=1, if ab is a nonresidue mod 2d we have ab ≡ 3 mod 4.
Hence a or b must be congruent to 1 mod 4, which contradicts an ≡ bn ≡ -1 mod 4.
If d≥3 then from an ≡ bn ≡ -1 mod 8 we find a ≡ b ≡ 7 mod 8, but then ab is a quadratic residue mod 2d.

We may always find c by trying c = 0,1,2,... We need at most 1 + m/2 trials.



HOME