**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 A_{i,j} the intersection of all A ∈ F with i,j ∈ A.

Then A_{i,j} belongs to F, so if 1 < i < j then A_{i,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.

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