Solutions by H Reuvers


I submitted solutions for 20 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).
Most of them have already been recognized by NAW.
I received book tokens for 2011-3/A, 2014-3/C, 2015-3/C and 2016-2/C.


Problem A sept 2011

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 2A 2013 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 4A 2014

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 1C 2016

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 2B 2016: 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.)



HOME