Suppose that we have a colour palette, i.e., an array of n elements, which needs to be coloured by distinct numbers. We are only allowed to use 0 or 1 to colour every elements in each colouring step. In every step, we try to use almost uniformly distributed colours. For example, for n = 4, in the first step we may add the 1st slice of colour {0, 1, 0, 1}, in the second step we may add the second slice of colour {0, 0, 1, 1}, and voilà done! now every elements has a distinct colour, {00, 10, 01, 11}.
How may times should we colour a palette of n elements to have distinct colours?
Note: I am looking for complete answers.
Clearly with $k$ steps, each of which makes only a $2$-way distinction, you can distinguish at most $2^k$ elements. Suppose that $2^k<n\le 2^k+1$. Number the $n$ elements $0$ through $n-1$, and write the $n$ numbers in binary as $(k+1)$-bit numbers (with leading zeros as needed). On pass $i$ add a slice to each element whose $i$-th bit is $1$; this will result in distinct colors for each of the $n$ elements. Thus, the number of passes needed is $\lceil\log_2n\rceil$.