结论：答案等于 $\lceil\log_k n\rceil$。

充分性：把数组划分成 $k$ 块，块与块之间使用颜色 $c_1$，再在每一块中划分 $k$ 小块，块间颜色 $c_2$…… 这样总共需要 $\lceil\log_k n\rceil$ 种颜色，且任意同色路径长不超过 $k-1$。

必要性：归纳，$c=0$ 时 $n$ 最大为 $k^c=k^0=1$。假设 $c=m$ 时成立，对于 $c=m+1$，如果 $n>k^{m+1}$。根据 Dilworth 定理，假设 $m+1$ 号颜色的最长链点数为 $x$，那么最小反链覆盖也为 $x$，并有 $x\le k$。反链上的点之间不能再用 $m+1$ 染色。根据抽屉原理可得，一定存在一条反链的点数大于 $k^m$。而这是无法用剩下 $m$ 种颜色染色的。由此我们证明了使用 $c$ 种颜色染色 $n$ 最大不能超过 $k^c$。也就是说答案一定 $\ge \lceil\log_k n\rceil$。

证毕。