  We show that for any two values $\alpha, \beta >0 $ for which
$\alpha+\beta>1$ then there is a value $N$ so that for all $n \geq N$ the
following holds. For any binary phylogenetic tree $T$ on $n$ leaves there is a
set of $\lfloor n^\alpha \rfloor$ characters that capture $T$, and for which
each character takes at most $\lfloor n^\beta \rfloor$ distinct states. Here
`capture' means that $T$ is the unique perfect phylogeny for these characters.
Our short proof of this combinatorial result is based on the probabilistic
method.
