Let $N\_+$ denote the set of positive integers. Let $E$ be the collection of all finite $A\subseteq \mathbb{N}\_+$ such that $|A|\geq 3$ and $\min(A)$ is the greatest common divisor of $A\setminus\{\min(A)\}$.


**Question.** Is there a positive integer $n$ such that there is a map $f: \mathbb{N}\_+ \to \{1,\ldots,n\}$ with the property that whenever $A\in E$, the restriction $f\restriction\_A$ is not constant - and if yes, what is the smallest value that $n$ can take?



"Coloring" the greatest common divisor relation
There is no such $n$.
Denote $f(1)=2$, $f(n)=2f(n-1)+2$, that is, $f(n)=2^{n+1}-2$.
The claim follows from the following


**Proposition.** Assume that $N\geqslant f(n)$ and all subsets of an $N$-set $\Omega$ are colored with $n$ colors. Then there exist three distinct sets $A,B,C$ of the same color such that $A=B\cap C$.


**Proof.** Induction in $n$. Base $n=1$ is clear. Assume that $n>1$, $N\geqslant f(n)$ and the proposition holds for $n-1$. Let $\emptyset$ be blue. Consider two cases:


1. There exists a non-empty blue set $A$ such that $N-|A|\geqslant f(n-1)+1$. If there exists a non-empty blue subset of $\Omega\setminus A$, then this set, $A$ and $\emptyset$ give a desired triple. Otherwise all non-empty subsets of $\Omega\setminus A$ are colored with $n-1$ colors. Fix $x\_0\in \Omega\setminus A$ and concentrate on subsets of the form $\{x\_0\}\sqcup B$, $B\subset \Omega\setminus (A\cup \{x\_0\})$. Their coloring induces a coloring of subsets of the set $\Omega\setminus (A\cup \{x\_0\})$, and applying induction proposition to this coloring we get a desired triple.
2. $|A|\geqslant N-f(n-1)\geqslant f(n)-f(n-1)\geqslant f(n-1)+2$ for all non-empty blue subsets $A$. Take any subset $\Theta\subset \Omega$ of size $f(n-1)$, any $x\_0\in \Omega\setminus \Theta$, and consider the coloring of subsets $B\subset \Theta$ induced by the coloring of $B\sqcup \{x\_0\}$. This coloring does not use blue, so we again may apply induction proposition.


