Каждому числу натурального ряда сопоставили один из конечного множества цветов. Доказать, что всегда тройка $%x,y,z$% одного цвета для которых верно $%x+y = z$%.

задан 20 Июл '15 22:52

изменен 21 Июл '15 13:39

%D0%92%D0%B8%D1%82%D0%B0%D0%BB%D0%B8%D0%BD%D0%B0's gravatar image


9917

10|600 символов нужно символов осталось
2

Рассмотрим граф, у которого множество вершин есть $%\mathbb N$%. Пусть ребро соединяет числа $%a < b$%. Раскрасим его в цвет числа $%b-a$%. При этом рёбра окажутся раскрашены в конечное число цветов, и при этом найдётся одноцветный треугольник (для этого достаточно $%[n!e]+1$% вершины при $%n$% цветах, что доказывается по индукции).

Пусть $%a < b < c$% -- вершины такого треугольника. Положим $%x=b-a$%, $%y=c-b$%, $%z=c-a$%. Тогда $%x+y=z$%, и все три числа имеют один и тот же цвет.

ссылка

отвечен 20 Июл '15 22:58

Необычная идея - граф с бесконечным (счетным) числом вершин, а насчет утверждения доказываемого под индукции: B выражении [n!e] + 1 e это число эйлера, значит надо как-то анализ привлекать?

(20 Июл '15 23:11) sapere aude

@sapere aude: анализ привлекать не надо -- это просто такая верхняя оценка. Достаточно доказать для достаточно большого числа вершин. Это задача рамсеевского типа. Для двух цветов хватает 6 вершин, для трёх нужно 17, и так далее.

(20 Июл '15 23:13) falcao
1

Вот эта последовательность: http://oeis.org/A073591 Рекуррента f[n] := n*(f[n - 1] - 1) + 2;

(21 Июл '15 11:57) knop
10|600 символов нужно символов осталось
Ваш ответ

Если вы не нашли ответ, задайте вопрос.

Здравствуйте

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

Присоединяйтесь!

отмечен:

×1,825
×1,482
×970

задан
20 Июл '15 22:52

показан
676 раз

обновлен
21 Июл '15 11:57

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru