Maximal number of colours in a palette that allows for fewer than 500 mixtures

Question

An artist is planning on mixing together any number of different colours from her palette. A mixture results as long as the artist combines at least two colours. If the number of possible mixtures is less than 500, what is the greatest number of colours the artist could have in her palette?

Answer 1

Assume that the artist has $n$ colours. Then the possible number of mixtures with

• $2$ colours, is equal to $\dbinom{n}{2}$
• $3$ colours, is equal to $\dbinom{n}{3}$,
• $\ldots$,
• $n-1$ colours, is equal to $\dbinom{n}{n-1}$,
• $n$ colours, is equal to $\dbinom{n}{n}$,

Thus the total number of mixtures is equal to $$\sum_{k=2}^{n}\binom{n}{k}=-\binom{n}{0}-\binom{n}{1}+\sum_{k=0}^{n}\binom{n}{k}1^{n-k}1^k=-1-n+(1+1)^n$$ by the Binomial Theorem. Thus you need to find the maximum $n$ that satisfies $$-1-n+2^n<500 \iff 2^n-n<501$$ By trial and error and since the LHS is increasing in $n$, you can find that $$2^8-8=248<501 \\ 2^9-9=503\not<501$$ therefore the maximum such $n$ is $n=8$.

---

As indicated in the comments, a more straightforward way to calculate the total number of mixtures is to observe that if you have $n$ colours then there are $2^n$ possible sets of colours ($2^n$ is the cardinality of the powerset). Now from this $2^n$ sets exclude all sets that contain just 1 colour (there are $n$ such sets) and the empty set. Thus, you obtain that there are $$2^n-n-1$$ possible mixtures.