Ограничение на одноцветные решения

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

Придумать функцию $n(k)$ такую, что при любой раскраске натурального ряда в $k$ цветов уравнение $x+y=z$ имеет одноцветное решение, для которого $x,y,z \leqslant n(k)$ (в этой задаче считается, что натуральный ряд начинается с единицы).

P. S. Я знаю, как доказать существование такой функции, однако это доказательство неконструктивно и ничего не даёт в плане построения $n(k)$ в явном виде.

[maxal]

Минимальное такое n(k) называется числом Шура: http://mathworld.wolfram.com/SchurNumber.html

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

вот тут когда-то похожие задачи обсуждали: http://www.nsu.ru/phorum/read.php?f=29&t=2564&a=1

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

maxal писал(а):

вот тут когда-то похожие задачи обсуждали: http://www.nsu.ru/phorum/read.php?f=29&t=2564&a=1

Да, действительно... Я уже забыл то обсуждение. Память девичья

Походил по указанным ссылкам, странная какая-то вещь вырисовывается. Если $S(k)$ --- число Шура (наименьшее из всех возможных $n(k)$), то

\[ \frac{3^k-1}{2} \leqslant S(k) < R(3,k) \leqslant c\frac{k^2}{\ln k} \]

для некоторой константы $c$ и всех $k \in \mathbb{N}$. Как такое возможно?

[maxal]

MathWorld не на те числа Рамсея ссылку дает. Нужные там только всколзь упоминаются как "обобщенные числа Рамсея". Если переводить "R(3,k)" на язык MathWorld, то это R(3,3,...,3;2), где количество троек равно k.
Или вот в этой статье они называются k-color Ramsey numbers.
Вот они же в OEIS: A003323

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

Цитата:

A generalized Ramsey number is written

\[ R(m_1, \ldots, m_k;n) \]

and is the smallest integer $r$ such that, no matter how each $n$-element subset of an $r$-element set is colored with $k$ colors, there exists an $i$ such that there is a subset of size $m_i$, all of whose $n$-element subsets are color $i$.

Ну да, понятно. Существование таких чисел должно следовать из теоремы Рамсея: если для бесконечного множества $I$ множество всех его $n$-элементных подмножеств $I^{[n]}$ поделено на конечное число частей, то найдётся бесконечное $J \subseteq I$, для которого все элементы $J^{[n]}$ принадлежат одной и той же части. Знаком также с доказательством этой теоремы (через ультрафильтры). Но доказательство это неконструктивно и не даёт никакой верхней оценки для обобщённых чисел Рамсея.

Так что вопрос всё равно остаётся: получить верхнюю оценку для чисел Шура в виде какой-нибудь "хорошей функции" (например, выражающейся через степени, сложение и умножение).

[maxal]

В статье Upper bounds for ramsey numbers R(3, 3, ...,3) and Schur numbers доказывается, что

$$R(3,\dots,3)\leq \frac{e-e^{-1}+3}{2}n!+1$$

для всех $n\geq 4$, что также дает оценку для $S(n)$.

Там же в случае чётного $n$ дана чуть более лучшая оценка для чисел Шура:

$$S(n) \leq \frac{e-e^{-1}+3}{2}n!-n+2$$

для всех чётных $n\geq 6$.