"Coloring" the greatest common divisor relation

Question

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?

Answer 1

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.

Answer 2

There is no such $n$. Proof: Suppose $n$ and $f$ are as in the problem. Of the $2n+1$ numbers $1,2,4,8, \dots, 2^{2n}$, some three have the same $f$-value. And the smallest of those three is the greatest common divisor of all three.