Раскраска натурального ряда #507134

Задача 1: Можно ли раскрасить натуральный ряд в два цвета так, чтобы для любого натурального n числа n и 2*n были окрашены в разные цвета? Задача 2: Можно ли раскрасить натуральный ряд в 2 цвета так, чтобы не было бесконечной арифметической прогрессии раскрашенной одним цветом?

апну

в первом случае видимо можно

если шаг прогрессии - 0 то нельзя :)

1. можно 2. можно (иррациональное число)

1 1. для любого К (начиная с 1) красим текущим цветом числа К и 2*К. 2. К = К+1 3. Если цвет К отличается от текущего, то меняем цвет. 4. GoTo 1. Для 2 ответ в

прогрессия конечно из натурального ряда

+ полностью в натуральном ряде

имел в виду - взять любое иррациональное число (пи, е, корень из 2х) в 2ичной форме и раскрашивать соответственно цветами, хотя это неочевидно), хотя наверно проще так: 2красных, 3 синих, 4 красных, 5 синих, 6 красных и т.д. для 1.: все простые красим в красный, простые*2 в синий и т.д., 1 - в синий;

и почему решил что не будет? на первую задачу, во что красим непростое 333?

потому что у прогрессии фиксированный шаг, и рано или поздно он будет меньше чем число подряд идущих одного цвета, а так как она бесконечная, то перейдет с одного цвета на другой; про первую - не простые, а нечетные

не факт, не факт смотри все четные 1, а вот нечетные ведут себя хаотически

про первую понятно, так я и думал собственно

+ в двоичной системе

Представим натуральный ряд в виде бинароного дерева. Чилды узла k: 2k-левый и 2k+1-левый Понятно что никто нам не мешает покрасить все правые чилды узлов в противополжный от родителя цвет. Во второй задаче - конечно можно, и очень просто - закрасили всё в один цвет, кроме 1-го,2-го,4-го,8-го (просто взяли геометрическую прогрессию)

по второй: арифм. прогрессия 3,6,9,12,... одного цвета

Понял! Я не так понял условие задачи. Сейчас подумаю.

Закрасить n^к+к, для всех к>1 и n>1, ни одна арифметическая програссия через такой заслон не пройдет. А само это множество не может дать арифметической програссии, ибо плотность с возрастанием номера ячейки падает.

Представим натуральный ряд в виде бинарного дерева. Чилды узла k: 2k-правый и 2k+1-левый - вот так правильней.

так не понял таки как закрасить для второй задачи

В один цвет все элементы вида n^к+к, в другой все остальные. Докажем что остальными цветами не получим арифметическую прогрессию. Понятно что с шагом 1 програссию не получить. Прогрессия пусть имеет вид a+(n*b) её будут пересекать элемнты противоположного цвета вида n^a+a (b=n^(a-1)),  N^(a+n)+(a+n) (b=n^(a+n-1)+1) и т.д.

почему ты b подбираешь определенного вида, не обязательно b будет таким

поменяй местами b и n.

согласен