A nice problem by Peter Cameron on subsets of $\{1,\dots,n\}$

Question

Recently Professor Peter Cameron posed a number theory problem which is related to graphs of groups. The problem is:

Problem:

Let $n$ be a positive integer. Show that there exist subsets $A_1, A_2, …,A_n$ of $\{1,2,…n\}$ with the properties

1. $|A_i| = \varphi(i)$ for $i = 1,2,…,n$;

2. if $\mathrm{lcm}(i,j) ≤ n$, then $A_i$ and $A_j$ are disjoint, where $\mathrm{lcm}$ denotes the least common multiple.

Professor Cameron gave some motivations for this question in his blog.

I checked it for a lot of numbers and the results seems to be true. Also, it seems that for some class of numbers there are patterns. For example if $n$ is prime and the statement is true, then it seems that it is true for the multiples of it.

My question: Is it sufficient that we prove this problem for prime numbers?

The first version of the paper published. Congratulate to Veronica Phan, a medical student who knows mathematics well. I think she is the first medical student which has common paper with professor Cameron. Paper

Answer 1

Let $F_n$ be a set of all irreducible fraction $\frac{p}{q}$ such that $0<\frac{p}{q}\leq 1,1\leq p,q\leq n$ and for $i\in \{1,...,n\}$, $D_i$ be subset of $F_n$ which contain all irreducible fraction of the form $\frac{k}{i}$. We have $D_i$ are pairwise disjoint and $|D_i|=\varphi(i)$. So we want a function $f:F_n\rightarrow \{1,...,n \}$ then we can take $A_i=f(D_i)$.

We construct $f$ as follow: if $\frac{m-1}{n}<\frac{p}{q}\leq \frac{m}{n}$ then $f(\frac{p}{q})=m$. If $f(\frac{p}{q})=f(\frac{p'}{q'})=m$ then $|\frac{p}{q}-\frac{p'}{q'}|<\frac{m}{n}-\frac{m-1}{n}=\frac{1}{n}$ (#).

-If $f(\frac{k}{i})=f(\frac{l}{i}), i\leq n$ then by (#) we have $|\frac{k-l}{i}|<\frac{1}{n}$, because $i\leq n$ we must have $k-l=0\Rightarrow k=l$. So the restriction of $f$ to $D_i$ is injective for all $i\in \{1,...,n\}$, therefore $|A_i|=|D_i|=\varphi(i)$.

-If $m\in A_i\cap A_j,i\neq j$, then there exist irreducible fractions $\frac{k}{i}\in D_i,\frac{l}{j}\in D_j$ such that $f(\frac{k}{i})=f(\frac{l}{j})=m$, by (#) we have $\frac{P}{Q}=|\frac{k}{i}-\frac{l}{j}|<\frac{1}{n}$ with $\frac{P}{Q}$ is irreducible. Because $i\neq j$ so $\frac{k}{i}\neq \frac{l}{j}\Rightarrow \frac{P}{Q}>0\Rightarrow P\geq 1$.
We have $\frac{P}{Q}=\frac{|k\frac{lcm(i,j)}{i}-l\frac{lcm(i,j)}{j}|}{lcm(i,j)}>0\Rightarrow Q\leq lcm(i,j)$ (because $\frac{P}{Q}$ is irreducible) and $\frac{P}{Q}<\frac{1}{n}\Rightarrow Q>Pn\geq n$ so $lcm(i,j)>n$. So if $lcm(i,j)\leq n$, $A_i,A_j$ must be disjoint.
So $A_1,...,A_n$ are subsets of $\{1,...,n\}$ we want.