Раскраска в два цвета, задача на доказательство

[Ktina]

Для каждого натурального $k$ доказать, что множество всех натуральных чисел можно раскрасить в два цвета так, чтобы для каждого натурального $n$ числа $n$ и $kn+1$ были покрашены в разные цвета.

[Cash]

$f(n)=kn+1$
Берем $a_1=1$. В последовательности $a_1, f(a_1), f(f(a_1)), \ldots , f^n(a_1), \ldots$ чередуем цвета.
Далее $a_2$ - наименьшее непокрашенное число. Красим его в любой цвет и в последовательности
$a_2, f(a_2), f(f(a_2)), \ldots , f^n(a_2), \ldots$ чередуем цвета. И так далее...
Последовательности, очевидно, не пересекаются.

[Ktina]

Cash,
У меня есть более красивое (на мой взгляд) решение, доступное пятиклассникам. Да ещё и в одну строчку.

[Cash]

(Оффтоп)

Не спорю, как и у почти всякой простой задачи у нее может быть много решений. И красить здесь можно почти как угодно...

[Ktina]

Cash,
Если в $k$-ичной записи числа чётное число единиц, красим в первый цвет. Иначе -- во второй. Разве не так?

[Cash]

Все правильно. Но можно также, например, считать не все единицы, а только последние.

[Ktina]

Cash в сообщении #672412 писал(а):

Все правильно. Но можно также, например, считать не все единицы, а только последние.

Что понимать под последними?

-- 16.01.2013, 17:41 --

И по моему, Вы не правы. Поясните, пожалуйста, что Вы имели в виду?

[Cash]

Я имел в виду количество единиц идущих подряд на конце числа (в k-ичной системе)

[Ktina]

Cash в сообщении #672653 писал(а):

Я имел в виду количество единиц идущих подряд на конце числа (в k-ичной системе)

Тогда Вы правы.
Я подумала о другом. О количестве единичек среди последних (LSD), скажем, 10 цифр. Тогда Вы были бы не правы.