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

[TOTAL]

Sinus писал(а):

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

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

?

Пусть уже доказано, что $x_k=k$ для $k=1,\hdots,n$.
Имеем $x_{n+1}=P(x_n)=P(n)=q+1$.
Допустим, что $q>n$, тогда по модулю $q$ получаем:
$x_{n+1}=1$
$x_{n+2}=P(x_{n+1})=P(1)=x_2=2$
$x_{n+3}=P(x_{n+2})=P(2)=x_3=3$
$\hdots$
$x_{2n}=P(x_{2n-1})=P(n-1)=x_n=n$
$x_{2n+1}=P(x_{2n})=P(n)=x_{n+1}=1$
и т.д. кругами, т.е. на $q$ не делится ничто. Поэтому $q=n$

Добавлено спустя 10 минут:

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 - разной четности.

Не нужны арифметические прогрессии.
1. Из-за бесконечного числа сочетаний (желтый-синий) и (синий-желтый) всегда можно выбрать 2002 синих чисел с суммой $S$ и 2002 желтых чисел с суммой $G$ так, что $S=G+2$
2. Если имеется два соседних синих, то можно найти 1 синий равный $s$ и один желтый равный $g$ такие, что $s=g-2$
3. $S+s=G+g$ - противоречие.

[Sinus]

TOTAL писал(а):

Sinus писал(а):

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

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

?

Пусть уже доказано, что $x_k=k$ для $k=1,\hdots,n$.
Имеем $x_{n+1}=P(x_n)=P(n)=q+1$.
Допустим, что $q>n$, тогда по модулю $q$ получаем:
$x_{n+1}=1$
$x_{n+2}=P(x_{n+1})=P(1)=x_2=2$
$x_{n+3}=P(x_{n+2})=P(2)=x_3=3$
$\hdots$
$x_{2n}=P(x_{2n-1})=P(n-1)=x_n=n$
$x_{2n+1}=P(x_{2n})=P(n)=x_{n+1}=1$
и т.д. кругами, т.е. на $q$ не делится ничто. Поэтому $q=n$

Спасибо еще раз, все понятно.

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

Sinus писал(а):

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

Вот интересно стало: а что, если раскрашивать не натуральные, а рациональные числа? То есть сформулируем такую задачу:

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

Будет ли эта задача иметь однозначное (или вообще хоть какое-то) решение?

[Sinus]

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

Вот интересно стало: а что, если раскрашивать не натуральные, а рациональные числа? То есть сформулируем такую задачу:

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

Будет ли эта задача иметь однозначное (или вообще хоть какое-то) решение?

Задача, которую вы сформулировали, имеет такое же решение, что задача, сформулированная мной в первом посте. Может быть, вы имели ввиду следующую формулировку:

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

[Руст]

Очевидно, не существует такой раскраски.

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

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

Очевидно, не существует такой раскраски.

Почему? Это голословное утверждение или Вы умеете его доказывать?

[Руст]

Рассмотрите числа вида $X_d=\frac{x}{d}, x\in N$ с фиксированным d.Для некоторого d получается бесконечность синих и жёлтых чисел в $X_d$. Рассмотрите тогда $X_{2d}$ где все чётные и нечётные x чисел $x/d \in X_d$ становятся чётными в $X_{2d}$, что приведёт к противоречию с возможностью такой раскраски.

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

Ну да, согласен.

Кстати, если вместо $\mathbb{Q}^+$ взять $\mathbb{R}^+$, то раскраска вроде опять существует.

Предлагаю в плане обобщения подумать над следующими двумя задачами (вдруг кому-то станет интересно?)

Задача I. Пусть $\mathfrak{A} = \langle A, + \rangle$ --- бесконечная коммутативная полугруппа. Какими свойствами должна обладать $\mathfrak{A}$ для того, чтобы существовала раскраска множества $A$ в два цвета, при которой

1) для любого цвета существует бесконечно много элементов $A$, окрашенных в этот цвет;

2) сумма любых трёх различных элементов $A$ одного цвета есть элемент того же самого цвета.

Задача II. Пусть $n,k \in \mathbb{N}$ фиксированы. При каком условии на эти числа существует раскраска натурального ряда в $n$ цветов, такая что каждый цвет имеет бесконечно много окрашенных в него чисел и сумма любых $k$ чисел одного цвета есть число того же самого цвета.

Для задачи номер 2, похоже, при $n=2$ раскраска существует тогда и только тогда, когда $k$ нечётно. Есть гипотеза, что при произвольном $n$ раскраска существует в том и только в том случае, если $k \equiv 1 \, (\mathrm{mod}\, n)$.