Каждое натуральное число нужно покрасить в соответствии со следующими тремя правилами:

1. каждое число окрашивается красным или зеленым цветом

2. сумма любых двух различных красных чисел является красным числом

3. сумма любых двух различных зеленых чисел является зеленым числом

Сколькими различными способами это можно сделать?

Допустим, единица выкрашена в зеленый цвет, тогда если есть еще зеленые числа, то все натуральные числа большие или равные второго зеленого числа тоже зеленые (т. к. просто к каждому зеленому будем прибавлять эту зеленую единицу и получать подряд идущие зеленые числа). Теперь, если между единицей и ближайшим к ней зеленым числом было хотя бы два красных числа, то сумма двух красных чисел ближайших слева к этому второму зеленому будет больше второго зеленого числа. С одной стороны эта сумма обязана быть красной, а с другой стороны, мы выяснили, что после второго зеленого числа все числа тоже зеленые. Значит такого быть не может, т. е. возможны только две ситуации: 1) кроме единицы больше зеленых нет 2) между зеленой единицей и следующим зеленым числом есть только одно красное. Аналогичное рассуждение проводится в случае, если единица - красная. Итак, возможны только 4 раскраски:

з к к к к к ...

з к з з з з ...

к з з з з з ...

к з к к к к ...

Ответ: 4.