you want to colour integers from 1 to 100 so that no number is divisible by a different  number of same colour.  what is the smallest possible number of colours u can have?

Answer: $ 7$ colours.

[hide]Hint: let $ a\preceq b$ iff $ a$ divides $ b$. Then the largest chain has length $ 7$.[/hide]

[quote="zhoraster"]

let $ a\preceq b$ iff $ a$ divides $ b$. Then the largest chain has length $ 7$.[/quote]

how could u say that ?

[quote] let a\preceq b iff a divides b. Then the largest chain has length 7.[/quote]
zhoraster is terse. What he did is use the dual version of

[color=blue][b]Dilworth's theorem.[/b] In every finite partial ordered set $ (P, \preceq)$, the minimum number of antichains covering $ P$ is equal to the maximum cardinality of a chain in $ P$.[/color] (For a solution, see e.g. Reinhard Diestel, Graph Theory.)

Now take $ P \equal{} \{1, 2, \ldots, 100\}$ and $ \preceq$ be the divisibility relation; clearly this endows $ P$ with a partial order. Let $ C \equal{} \{a_1, a_2, \ldots, a_k\}$ be a chain (i.e. a totally ordered subset), hence $ a_1 \preceq a_2 \preceq \cdots \preceq a_k$. This implies $ 100 \geq a_k \geq 2a_{k \minus{} 1} \geq \cdots \geq 2^{k \minus{} 1}a_1 \geq 2^{k \minus{} 1}$, so $ k \leq 7$. An example of a maximum cardinality chain is $ M \equal{} \{1,2,4,8,16,32,64\}$. Then, by the above theorem, the minimum number of antichains partitioning $ P$ is also $ 7$, and this is what you want, so that no number colored with the color of its antichain divides another of same color.