I’d like to see this solved

Here is a problem that I would really like to see solved. I have spent quite a bit of time on it myself, and have suggested it to a few other people, but it still resists all attacks, though it looks relatively simple.

As background, recall Euler’s totient function φ, defined for positive integers n by the rule that φ(n) is the number of integers in the interval from 0 to n−1 which are coprime to n. The one fact I need is that, if you sum φ(d) over the divisors d of n, the result is n. This is because φ(d) is the number of integers x in the interval from 0 to n−1 for which the greatest common divisor of x and n is n/d; and for every integer in this interval, gcd(n,x) is some divisor of n.

Now here is the problem.

Problem: Let n be a positive integer. Show that there exist subsets A₁, A₂, … A_n of {1,2,…n} with the properties

• |A_i| = φ(i) for i = 1,2,…,n;
• if lcm(i,j) ≤ n, then A_i and A_j are pairwise disjoint, where lcm denotes the least common multiple.

The conditions of the problem require, in particular, that the sets A_i for which i divides n should be pairwise disjoint; but by our earlier remark, there are just enough points to permit this.

I have tried several different attacks, which I won’t detail here; I don’t want to lead you into a blind alley. But I will make one remark.

One obvious construction to try is the greedy algorithm. Choose the sets A₁, A₂, …, in turn. When choosing A_i, we must avoid points lying in any A_j with j ≤ i and lcm(i,j) ≤ n; continue through the natural numbers until φ(i) points have been chosen. We win if no number greater than n needs to be chosen. This is very simple to implement computationally. It has been checked up to n = 1000 and succeeds in all cases.

I certainly feel that if the greedy algorithm succeeds in solving a problem, that problem should be easy!