We show that there is an infinite graph of finite degree defined by a Borel equivalence relation on a probability space such that it can be coloured properly with 17 colours but only in ways that induce paradoxical decompositions. We also show that there are problems of optimization such that every epsilon-optimal solution for small enough positive epsilon induces a paradoxical decomposition.