Solutions by Hendrik Reuvers Brusselsestraat 92 6211PH Maastricht


Problem 2018-2/A:
Let n > 2 be an odd integer and let C be an embedding of the circle in Rn. That is, C = f([0,1]), where f : [0,1] → Rn is continuous, f(0) = f(1), and f is injective on [0,1].
Show that there is an affine hyperplane in Rn that contains at least n+1 points from C.

Solution:

Let n = 2m+1. We use induction to m.

Let m=1. Suppose there is no plane H such that C contains at least 4 points of H.
Then there must exist a plane H' such that C contains 2 or 3 points of H' and all other points of C lie on the same side of H'. Let's call this side the good side and these 2 or 3 points extremal points.
Let H" be a plane parallel to H' and at the good side of H' and sufficiently close to H'. The 2 or 3 extremal points mentioned above divide C in 2 or 3 parts such that each of them contains at least 2 points of H", each close to one of the 2 extremal points that are the end points of the part. So C contains at least 4 points of H". Contradiction.

Now suppose m > 1 and the proposition holds for n=2m-1.
Let the projection p: R2m+1 → R2m-1 be defined by p(x1,x2,..,x2m-1,x2m,x2m+1) = (x1,x2,..,x2m-1). Then p(C) is an embedding of the circle in R2m-1.
By induction hypothesis, there is an affine hyperplane in R2m-1 that contains at least 2m points from p(C). This can be extended to an affine hyperplane in R2m+1 that holds most of C at one side and contains at least 2m extremal points of C.
Suppose there is no affine hyperplane H in R2m+1 such that C contains at least 2m+2 points of H.
Then there must exist an affine hyperplane H' such that C contains 2m or 2m+1 extremal points of H' and all other points of C lie on the same good side of H'.
Let H" be a plane parallel to H' and at the good side of H' and sufficiently close to H'. The 2m or 2m+1 extremal points mentioned above divide C in 2m or 2m+1 parts that each contain at least 2 points of H". Contradiction.


---------------------------------------------------------------------------------------------------------------


Problem 2018-2/B:
Place coins on the vertices of the lattice Z2, all showing heads. You are allowed to flip coins in sets of three at places (m,n), (m,n+1) and (m+1,n), where m and n are chosen arbitrarily.
Is it possible to achieve a position where two coins are showing tails and all other show heads using finitely many moves?

Solution:

No, for if it were possible, we could also from the final position with two tails achieve the position with zero tails, using a minimal number of moves. We will show this isn't possible.

Let's start with two tails and try to achieve zero tails with a minimal number of moves. Then flipping three heads to tails in one move is useless. But any move that doesn't flip three heads to tails or vice versa either increases or decreases the number of tails by one.
So, starting with two tails and using a minimal number of moves to achieve zero tails, we may achieve positions with more than two tails, but not a position with tails at places (m,n), (m,n+1) and (m+1,n). So eventually we must come back to a position with two tails.
From here we may achieve a position with one tail. But from such a position we can't achieve zero tails, either.


---------------------------------------------------------------------------------------------------------------


Problem 2018-2/C:
Say that a natural number is k-repetitive if its decimal expansion is a concatenation of k equal blocks. For instance, 1010 is 2-repetitive and 666 is 3-repetitive.
Let Rk be the set of all k-repetitive numbers. Determine its greatest common divisor.

Solution:

Gcd(Rk) is the gcd of the infinite sequence of numbers whose i-th term has the decimal representation with k ones and i-1 zeroes between each pair of consecutive ones, because this i-th term is the gcd of all k-repetitive numbers whose repeated parts have length i.
For instance, gcd(R5) = gcd(11111,101010101,1001001001001,10001000100010001, ...).
By considering the terms mod 9 and mod 10, we see: gcd(Rk) is divisible by 3 if and only if k is divisible by 3; gcd(Rk) is divisible by 9 if and only if k is divisible by 9; gcd(Rk) is never divisible by 2 or 5.
The i-th term is also equal to 1 + 10i + 102i + ... + 10i(k-1) = (10ik-1)/(10i-1) = repunit(ik)/repunit(i), where repunit(m) = 11..1 (m ones).


---------------------------------------------------------------------------------------------------------------