Рассмотрим пары вида где В каждой паре имеется хотя бы одно непокрашенное число, поскольку

Аналогичным образом получается, что пары содержат не менее трех непокрашенных чисел. Наконец, числа и не попавшие ни в одну из пар, по условию тоже не окрашены. Таким образом, имеется не менее непокрашенных чисел, откуда

Покажем, что полученная оценка реализуется. Покрасим числа а также все числа от до Пусть и — зеленые числа. Нам достаточно проверить, что не является степенью двойки. Если то это очевидно. В случае мы получаем

Наконец, если и то