Несколько непростых задач.

[Sinus]

1. Каждое натуральное число покрашено в один из двух цветов - синий или желтый, причем чисел каждого цвета бесконечно много. Известно, что сумма любых 2003 попарно различных чисел синего цвета является числом синего цвета, а сумма 2003 попарно различных чисел желтого цвета является числом желтого цвета. Определите, в какой цвет окрашено число 2004, если число 1 покрашено в синий цвет. Ответ обоснуйте.

2. Дан многочлен $P(x)$ с целыми коэффициентами. Для каждого натурального $n$ значение $P(n)$ больше $n$. Рассмотрим последовательность $x_1 = 1$, $x_2 = P(x_1 )$, ..., $x_{n + 1} = P(x_n )$, ... . Известно, что для любого натурального $m$ в этой последовательности найдется член, делящийся на $m$. Доказать, что $P(x) = x + 1$.

[Руст]

1. Возможно разделение на два множества с указанным свойством только на чётные и нечётные. Соответственно 2004 -жёлтого цвета.
2. Если $p|x_2-x_1$, то для любого n $x_n=1\mod p$. Это означает $x_2=x_1+1$, аналогично $x_{n+1}=x_n+1.$

[Профессор Снэйп]

Руст писал(а):

1. Возможно разделение на два множества с указанным свойством только на чётные и нечётные. Соответственно 2004 -жёлтого цвета.

А доказательство?

[TOTAL]

Sinus писал(а):

1. Каждое натуральное число покрашено в один из двух цветов - синий или желтый, причем чисел каждого цвета бесконечно много. Известно, что сумма любых 2003 попарно различных чисел синего цвета является числом синего цвета, а сумма 2003 попарно различных чисел желтого цвета является числом желтого цвета. Определите, в какой цвет окрашено число 2004, если число 1 покрашено в синий цвет. Ответ обоснуйте.

1. Если есть одна пара соседних синих, то есть и вторая пара соседних синих, поэтому есть несколько троек соседних синих и т.д., поэтому найдется сколь угодно длинная цепочка синих подряд.
2. Сумму первых $2002$ синих обозначим $S$. Найдем цепочку из $S$ синих подряд и сложим первые $2002$ синих с первым (меньшим) числом этой цепочки, затем со вторым, с третьим и т.д. Синие суммы пристраиваются в хвост цепочки. Получим бесконечно продолжающуюся цепочку синих. Противоречие.

[Профессор Снэйп]

TOTAL писал(а):

1. Если есть одна пара соседних синих, то есть и вторая пара соседних синих, поэтому есть несколько троек соседних синих и т.д., поэтому найдется сколь угодно длинная цепочка синих подряд.
2. Сумму первых $2002$ синих обозначим $S$. Найдем цепочку из $S$ синих подряд и сложим первые $2002$ синих с первым (меньшим) числом этой цепочки, затем со вторым, с третьим и т.д. Синие суммы пристраиваются в хвост цепочки. Получим бесконечно продолжающуюся цепочку синих. Противоречие.

Теперь всё то же самое надо проделать с жёлтыми.

А так вроде верно (хотя, конечно, можно было написать и более понятным языком ).

[TOTAL]

Профессор Снэйп писал(а):

Теперь всё то же самое надо проделать с жёлтыми.

1. Если есть одна пара соседних желтых, то есть и вторая пара соседних желтых, поэтому есть несколько троек соседних желтых и т.д., поэтому найдется сколь угодно длинная цепочка желтых подряд.
2. Сумму первых $2002$ желтых обозначим $S$. Найдем цепочку из $S$ желтых подряд и сложим первые $2002$ желтых с первым (меньшим) числом этой цепочки, затем со вторым, с третьим и т.д. Желтые суммы пристраиваются в хвост цепочки. Получим бесконечно продолжающуюся цепочку желтых. Противоречие.

[Kid Kool]

Профессор Снэйп писал(а):

А доказательство?

Можно я отвечу?

Существует бесконечно много синих чисел a, таких что a+1 - желтое и бесконечно много синих b, таких что b-1 - желтое. Рассмотрим 1000 чисел первого вида и 1002 - второго. Считаем, что все эти числа больше 2004. Обозначим это множество через A, а соответствующие желтые числа - через B. Пусть s - сумма чисел A, тогда сумма чисел B будет равна s+2. Тогда для любого синего числа с, не входящего в A, s+с тоже синее. Значит, синими будут все достаточно большие числа вида c+sx. Аналогично, желтыми будут все достаточно большие d+(s+2)y для любого желтого d, не входящего в B. Чтобы эти 2 арифметические прогресии не пересекались, необходимо, чтобы s и s+2 имели общий делитель, не делящий c-d. Этим общим делителем может быть лишь 2, откуда получаем, что синие и желтые числа, не входящие ни в A, ни в B - разной четности.

Добавлено спустя 3 минуты 9 секунд:

TOTAL писал(а):

поэтому есть несколько троек соседних синих и т.д.

почему это?

[TOTAL]

Kid Kool писал(а):

TOTAL писал(а):

поэтому есть несколько троек соседних синих и т.д.

почему это?

$a, a+1$ и $b, b+1$ - вот две двойки синих.
$a+b, a+b+1, a+b+2$ - вот созданная с их помощью тройка
Из двух троек создадим пятерку.

[Профессор Снэйп]

TOTAL писал(а):

Профессор Снэйп писал(а):

Теперь всё то же самое надо проделать с жёлтыми.

1. Если есть одна пара соседних желтых, то есть и вторая пара соседних желтых, поэтому есть несколько троек соседних желтых и т.д., поэтому найдется сколь угодно длинная цепочка желтых подряд.
2. Сумму первых $2002$ желтых обозначим $S$. Найдем цепочку из $S$ желтых подряд и сложим первые $2002$ желтых с первым (меньшим) числом этой цепочки, затем со вторым, с третьим и т.д. Желтые суммы пристраиваются в хвост цепочки. Получим бесконечно продолжающуюся цепочку желтых. Противоречие.

Я не имел в виду, что надо копипастить рассуждения и подставлять везде слово "жёлтый" вместо слова "синий". Достаточно было обойтись замечанием о том, что для жёлтых чисел сходное утверждение доказывается аналогично.

Если же вообще выпускать из рассмотрения жёлтые числа, то Ваше доказательство становится неполным. Действительно, мы доказали, что синие числа не могут идти "подряд", то есть что для любого $n \in \mathbb{N}$ числа $n$ и $n+1$ не могут быть оба синего цвета. Ну и что? Из этого ещё не следует, что все нечётные числа --- синие, а все чётные --- жёлтые. А вот если мы отметим справедливость аналогичного утверждения для жёлтых чисел, то тогда задача будет действительно решена.

[Kid Kool]

TOTAL писал(а):

$a+b, a+b+1, a+b+2$ - вот созданная с их помощью тройка

Как мы так лихо складываем числа? Мне не понятно. По условию сумма 2003-х чисел одного вида - число того же вида. Можете Вы опираясь только на это условие и условие бесконечности чисел каждого вида вывести свои утверждения о тройках, пятерках и т.п.?

[TOTAL]

Профессор Снэйп писал(а):

Если же вообще выпускать из рассмотрения жёлтые числа, то Ваше доказательство становится неполным.

Говорить про желтые числа нет необходимости. Мы доказали, что начиная с какого-то числа все числа будут синими. Это противоречит условию (бесконечному числу желтых чисел).

Добавлено спустя 2 минуты 55 секунд:

Kid Kool писал(а):

TOTAL писал(а):

$a+b, a+b+1, a+b+2$ - вот созданная с их помощью тройка

Как мы так лихо складываем числа? Мне не понятно. По условию сумма 2003-х чисел одного вида - число того же вида. Можете Вы опираясь только на это условие и условие бесконечности чисел каждого вида вывести свои утверждения о тройках, пятерках и т.п.?

Возьмите и добавьте к каждому из этих трех подряд идущих чисел (полученных каждое как сумма двух синих чисел) еще сумму 2001 синих чисел.

[Профессор Снэйп]

Kid Kool писал(а):

TOTAL писал(а):

$a+b, a+b+1, a+b+2$ - вот созданная с их помощью тройка

Как мы так лихо складываем числа? Мне не понятно. По условию сумма 2003-х чисел одного вида - число того же вида. Можете Вы опираясь только на это условие и условие бесконечности чисел каждого вида вывести свои утверждения о тройках, пятерках и т.п.?

Да не, понятно, что он имеет в виду. Нужно рассмотреть числа $s+a+b$, $s+a+b+1$ и $s+a+b+2$, где $s$ --- сумма $2001$ различных чисел синего цвета, ни одно из которых не входит в множество $\{ a,a+1,b,b+1 \}$.

Добавлено спустя 1 минуту 27 секунд:

TOTAL писал(а):

Профессор Снэйп писал(а):

Если же вообще выпускать из рассмотрения жёлтые числа, то Ваше доказательство становится неполным.

Говорить про желтые числа нет необходимости. Мы доказали, что начиная с какого-то числа все числа будут синими. Это противоречит условию (бесконечному числу желтых чисел).

Мы доказали это исходя из предположения, что найдутся два следующих друг за другом синих числа. А с чего вдруг это предположение обязано быть верным?

[TOTAL]

Профессор Снэйп писал(а):

Мы доказали это исходя из предположения, что найдутся два следующих друг за другом синих числа. А с чего вдруг это предположение обязано быть верным?

Какая-то путаница началась. Предполагая, что есть два синих подряд, приходим к противоречию с условием. Поэтому предположение неверно. Не могут быть два синих подряд. Неужели надо явно произносить, что и желтых (по этому же рассуждению) не может быть два подряд?

[Профессор Снэйп]

TOTAL писал(а):

Неужели надо явно произносить, что и желтых (по этому же рассуждению) не может быть два подряд?

Ну что значит "надо"?

Можно ограничиться ответом, а в качестве решения привести одно слово "очевидно". Тогда вообще ничего не надо... Если же всё-таки писать доказательство, то, на мой взгляд, столь важный шаг в рассуждениях следует хотя бы обозначить.

[Sinus]

TOTAL писал(а):

1. Если есть одна пара соседних синих, то есть и вторая пара соседних синих, поэтому есть несколько троек соседних синих и т.д., поэтому найдется сколь угодно длинная цепочка синих подряд.
2. Сумму первых $2002$ синих обозначим $S$. Найдем цепочку из $S$ синих подряд и сложим первые $2002$ синих с первым (меньшим) числом этой цепочки, затем со вторым, с третьим и т.д. Синие суммы пристраиваются в хвост цепочки. Получим бесконечно продолжающуюся цепочку синих. Противоречие.

Все правильно. Спасибо!

Руст писал(а):

2. Если $p|x_2-x_1$, то для любого n $x_n=1\mod p$. Это означает $x_2=x_1+1$, аналогично $x_{n+1}=x_n+1.$

Вы доказали, что $P(1) = 2$. Ясно, что для любого натурального

\[ m \]

найдется бесконечно много чисел последовательности, делящихся на

\[ m \]

. Поэтому если $p\left| {x_{n + 1} - x_n } \right.$, то

\[ x_n \equiv x_{n + 1} \equiv x_{n + 2} \equiv ...\bmod p \]

, и, значит,

\[ p\left| {x_n } \right. \]

. При этом нельзя утверждать, что

\[ p\left| {x_{n -1}} \right. \]

. Как здесь показать, что

\[ x_{n + 1} = x_n + 1 \]

?