Solutions by Hendrik Reuvers Brusselsestraat 92 6211PH Maastricht


Problem 2018-1/A:
Let f be a function from the set of positive integers to itself such that, for every n, the number of positive integer divisors of n is equal to f(f(n)). For example, f(f(6)) = 4 and f(f(25)) = 3. Prove that if p is prime then f(p) is also prime.

Solution:

First we note f(f(1)) = 1 and f(f(2)) = 2 and if n is greater than 2 then f(f(n)), being the number of positive integer divisors of n, is greater than 1 and smaller than n, because 1 and n are divisors of n, but n-1 is not a divisor of n.
Furthermore, for all n greater than 1 we have: f(f(n)) = 2 if and only if n has no divisors except 1 and n, so f(f(n)) = 2 if and only if n is a prime.

Suppose p is a prime. So f(f(p)) = 2.
If f(p) = 1 we find f(1) = 2 and f(2) = f(f(1)) = 1.
To prove that f(p) is a prime, we have to prove that f(p) is greater than 1 and f(f(f(p))) = 2, so we have to prove that f(2) = 2. This can be done as follows:

Consider any n such that both n and f(n) are at least 2.
Then both the sequences n, f(f(n)), f(f(f(f(n)))), ... and f(n), f(f(f(n))), f(f(f(f(f(n))))), ... are strictly decreasing until after a finite number of terms greater than 2 they end up with infinitely many terms 2,2,2,...
So f(2) = 2.


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


Problem 2018-1/B:
Let n be a positive integer and F ⊆ 2[n] a family of subsets of [n] = {1,2,...,n} that is closed under taking intersections. Suppose that
1. for every A ∈ F we have: |A| is not divisible by 3, and
2. for every pair i,j ∈ [n] there is an A ∈ F such that i,j ∈ A.
Show that n is not divisible by 3.

Solution:

(Notice that if n is not divisible by 3, then F := {[n]} satisfies the conditions.)

Henceforth we assume n is divisible by 3, say n = 3m, and want to derive a contradiction.
First we observe the intersection of all A ∈ F belongs to F, so can't be empty.
Without loss of generality we assume 1 belongs to all sets of F.
For any pair i,j with i < j, denote by Ai,j the intersection of all A ∈ F with i,j ∈ A.
Then Ai,j belongs to F, so if 1 < i < j then Ai,j must contain 1,i,j and at least one other element k.

Now if we would add to F two (n-1)-sets that don't include i,j respectively, we have to add the (n-2)-set that doesn't include i nor j, too. To include in F the pair i,j we have to add {1,i,j,k,...}. Here we can't stop with k nor with one more element nor with two more elements, etc, since either the added set itself or its intersection with the (n-1)-set or its intersection with the (n-2)-set would count a number of elements divisible by 3.
So we can't add to F two (n-1)-sets.
Again, if we would add to F only one (n-1)-set, say {1,2,3,...,3m-1}, then to provide for the pairs i,3m we could add to F the sets {1,2,3,4,3m}, {1,5,6,7,3m}, ... , {1,3m-4,3m-3,3m-2,3m}, but would still miss the pair 3m-1,3m.

So the best we can try to include in F as many pairs i,j as possible is the following:
(Assuming n is large enough, for small n are easy to deal with.)
Let F contain {1}, all 2-sets {1,i} with 1 < i, all 4-sets {1,i,j,k} with 1 < i < j < k, but if the intersection of two of these 4-sets is a 3-set then throw away the 4-set with the largest sum.
So of the 4-sets we only keep {1,2,3,4},{1,2,5,6},{1,2,7,8}, ...
Now, adding as many 5-sets as possible, we pick from each remaining 4-set the element 1 and one other element, so we get {1,3,5,7,9},{1,4,6,8,10},{1,11,13,15,17},{1,12,14,16,18}, ...
Continuing in the same way we get 7-sets {1,3,11,19,27,35,43},{1,4,12,20,28,36,44},{1,5,13,21,29,37,45}, {1,6,14,22,30,38,46},{1,7,15,23,31,39,47},{1,8,16,24,32,40,48},{1,9,17,25,33,41,49},{1,10,18,26,34,42,50}, {1,3,51,59,67,75,83}, ... and 8-sets {1,3,51,99,... .... etc.
So creating an F with as many pairs i,j as possible, we clearly don't get all pairs i,j. For instance, here we don't get the pair 3,8. Contradiction.


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


Problem 2018-1/C:
Cut three squares of equal size in exactly the same way into three pieces each in such a way that the resulting nine pieces can be rearranged to form a regular twelvegon. Open question: can you cut the three squares into eight pieces that form a regular twelvegon?

Solution:

On the internet I found these two pictures that demonstrate how we can cut 1 square into 6 pieces that can be rearranged to form 1 regular dodecagon.

We may argue this way we have also cut 3 squares into 8 pieces that form a regular dodecagon, albeit a small one because 2 squares are left uncut and not used. But I don't think the proposer of the problem will accept this solution.

So we are trying to cut 3 squares with area 1 into a minimal total number n of pieces that can be rearranged to form a regular 12-gon with area 3.
Then the vertices of this 12-gon lie on a circle with radius 1 and the 12-gon consists of 12 similar triangles with area 1/4 that all have 1 vertex in the center of the circle and 2 neighbour vertices in common with the 12-gon.
Each of these 12 triangles has two sides of length 1 that form an angle of 30 degrees and one side of length √(2 - √3) and two angles of 75 degrees.

Now we can also start from the dual problem, cutting the regular 12-gon with area 3 into a minimal number n of pieces that can be rearranged to form 3 squares with area 1.
We clearly have to cut the 12-gon into 4 major pieces with area 3/4, each of which consists of 3 neighbouring triangles as above, because we have to take advantage from the fact that such a major part makes up three quarters of a square with area 1, leaving only one quarter uncovered in a corner of the square.
But then we must hope we can cut 1 of these 4 major pieces in a small number of minor pieces that can be used as a complement to the other 3 major pieces so as to make them squares with area 1.
This is possible indeed. Here's how we have to cut the 4-th major piece in 6 parts that complement the 3 other major parts:


We clearly can't design the required jigsaw puzzle with less than 9 pieces.

So this procedure yields the following solution to the original problem, starting from the 3 squares, with a minimum n=9 of cuts:
Cut along the arrows. The 2 minor pieces can be rearranged to form a 4-th triangle with area 1/4 similar to the 3 triangles in the major piece. So each of the 3 squares yields 4 of the 12 triangles that form the 12-gon.



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