Kai the Artist

Probability Level 5

Kai colors the set $S = \{1,2,\ldots,2016\}$ with some colors such that if $x, y$ have the same color, then they do not divide each other. What is the minimum number of colors needed?

The answer is 11.

1 solution

Alan Yan
Nov 26, 2016

This is a poset, where the operator is $|$ . By Mirsky's Theorem , the minimum number is the maximal length of a chain, which is $\{1,2,\ldots,2^{10}\}$ , $\boxed{11}$ .

A construction is as follows: let $f(x)$ be the sum of all of the exponents in $x$ 's prime factorization. We partition $S$ into $A_0, A_1, \ldots, A_{10}$ such that $A_i = \{x : f(x) = i\}$ .

Nice construction!

Calvin Lin Staff - 4 years, 6 months ago

You can update your link to: https://brilliant.org/wiki/dilworths-theorem/#statement-of-dilworths-theorem-and-mirskys-theorem

Eli Ross Staff - 4 years, 6 months ago

Thanks! I've updated the link.

I didn't know that the converse of Dilworth was called Mirsky. I only knew it as "converse of Dilworth".

Calvin Lin Staff - 4 years, 6 months ago

Kai the Artist

The answer is 11.

1 solution

0 pending reports