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

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

• We should add that (on his blog) Peter also observed that the greedy algorithm (build each set with the first numbers that are not forbidden) works for all tested values of $n$ (up to 1000), which seems to be super strong evidence to me. I tested it for a few more values, and it miraculously works. Commented Jul 5, 2022 at 9:43
• @GordonRoyle, there's a comment that for $n=10920$ it's possible for the greedy algorithm to go wrong. (More specifically, there's more than one greedy algorithm, and the choice of non-prohibited elements to assign to each $A_i$ matters). Commented Jul 5, 2022 at 9:58
• Shahrooz, could you be a bit more precise about the patterns? Maybe give examples of assignments which show a relationship between $n=2$, $n=5$, $n=10$? Commented Jul 5, 2022 at 10:02
• Peter, OK... But now I do not have access to my computer and I am writing with my phone. Commented Jul 5, 2022 at 10:18

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.

• That is a beautiful construction - how did you find it? Commented Jul 10, 2022 at 5:29
• @GordonRoyle I try to attack it, and i find that this problem relate to this fomula: en.wikipedia.org/wiki/Euler%27s_totient_function#Divisor_sum. I want to find formula similar like that to solve the problem, but seem like it hard to find good formula. But there a nice trick using fraction that have denominator n to proof that formula. So I assume there some mysterius formula that I need to proof, so I need to extend to all fraction that have denominator not greater than n. And it work. Commented Jul 10, 2022 at 6:10
• I wish I could up vote this more than once! Commented Jul 10, 2022 at 7:38
• @veronicaPhan very nice solution... you can share it by professor Cameron. He is so eager to see this answer. Commented Jul 10, 2022 at 13:14
• @Shahrooz he has known it Commented Jul 10, 2022 at 14:35