Recently Professor Peter Cameron posed a [number theory problem which is related to graphs of groups](https://cameroncounts.wordpress.com/2022/06/17/id-like-to-see-this-solved/). 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](https://cameroncounts.wordpress.com/2022/07/05/why-id-like-to-see-this-solved/) 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](https://arxiv.org/abs/2207.07156)



A nice problem by Peter Cameron on subsets of $\{1,\dots,n\}$
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.


