Minimum number of colors for cards

Question

There are $N$ cards numbered from $1$ to $N$. Each card is to be colored so that every two cards of the same color do not have numbers divisible by one another. What is the minimum number of colors required?

Answer 1

I think it may be a NP-Complete problem which can be reduced to INDSET problem. Suppose we can complete efficiently decomposition of prime factors for $\forall x \in \{1,2,3,...,N\}$ (if $N$ is not big enough). So for every $x$, we can get equation of prime factorization $$x = a \cdot b \cdot c_1 \cdot c_2 \cdot d \cdot ...(1)$$ $a,b,c$ and $d$ are both prime number, $c_i$ means prime $c$ should be appeared i-th times in $x$. So we can transfer every element of $x \in \{1,2,...,N\}$ to a new set $X_i=\{a,b,c_1,c_2,d,...\} $, which contains all multiplicators in equation $(1)$. And then we build a bidirectional graph $G(V,E)$.

The vertexes set $V$ is the set of $\{X_i\}$, and $\vert V \vert = N$. The edge exists between $X_i$ and $X_j $ if and only if $X_i \subset X_j$ or $X_j \subset X_i$. So the original question can be transferred into recursive independent set problem, which is:

1. set $c=0$
2. find the max independent set of vertexes in $G(V,E)$, and remove subset $c$ from $G(V,E)$, then $c = c+1$.
3. repeat step $1$, if $G(V,E)$ is not empty; go to step $3$, if $G(V,E)$ becomes empty graph.
4. the number of $c$ accumulated above is the answer.

We use $\{1,2,3,4,5,6\}$ for example. The Graph $G(V,E)$ should be: $$v_1 = \{1\}$$ $$v_2 = \{2\}$$ $$v_3 = \{3\}$$ $$v_4 = \{2_1,2_2\}$$ $$v_5 = \{5\}$$ $$v_6 = \{2,3\}$$ According to vertexes above, we can build edges as below: $$ e_{1-5} = v_1 \to v_{2-6}$$ $$ e_{6} = v_2 \to v_4$$ $$ e_{7} = v_2 \to v_6$$ $$ e_8 = v_3 \to v_6$$

We first remove $\{v_4,v_5,v_6\}$, then remove $\{v_2, v_3\}$, and finally remove $\{v_1\}$, so the answer is 3.

Answer 2

We know that at least $\lfloor \log_2 N\rfloor + 1$ colors are required because, if $k = \lfloor \log_2 N\rfloor$, then the cards $2^0, 2^1, 2^2, \dots, 2^k$ must all have different colors.

Having $\lfloor \log_2 N\rfloor + 1$ colors is enough. Number the colors $0, 1, 2, \dots$ and give a number with prime factorization $p_1^{k_1} p_2^{k_2} \cdots p_m^{k_m}$ the color numbered $k_1 + k_2 + \dots + k_m$. Then:

• Given two cards with numbers $x$ and $y$, if $x \mid y$ and $x \ne y$, then $y$ has at least as many factors of every prime, and at least one more factor of some prime, so the color of $x$ is different from the color of $y$.
• Also, a number receiving color $j$ must be at least $2^j$, so we don't use too many colors.