Доказать: Существует такое целое число К, что при любой раскраске чисел 1,...,К в 3 цвета найдется одноцветная трехчленная арифметическая прогрессия.

Как я понимаю, это частный случай теоремы ван дер Вандена.

задан 28 Май '17 16:37

Да, это частный случай общей теоремы. Не уверен, что легко придумать для этого случая доказательство, которое было бы принципиально проще по сравнению с общей ситуацией.

(28 Май '17 16:52) falcao

@falcao Но в общей ситуации нужно доказать для произвольного количества цветов, и для всего натурального ряда, да и в арифметической прогрессии произвольное кол-во элементов. Правильно же я понимаю, что у написанной выше задаче можно привести конкретное K (видимо очень маленькое), перебрать все раскрасски в 3 цвета и показать что в любом случае арифм. прогрессия есть?

(28 Май '17 17:01) Андрей234443

@Андрей234443: доказательство теоремы ведёт к очень быстро растущим числам. Но это оценки, а не оптимальные значения. Я знаю, что можно вручную решить задачу для двух цветов и прогрессий из трёх членов. Там получается K=9. Это значение оптимально. Если рассуждать по схеме из доказательства, получается завышенная оценка порядка 325. Чему именно равно минимальное K для 3 цветов и 3-членных прогрессий, я не знаю. Оно может оказаться и не слишком маленьким, и тогда компьютерный перебор примерно 3^K вариантов будет долгим.

(28 Май '17 17:19) falcao

@falcao понял, спасибо больше, буду вникать в доказательство общей теоремы.

(28 Май '17 17:21) Андрей234443
10|600 символов нужно символов осталось
1

Я тут навёл некоторые справки -- оказывается, оптимальное значение для W(3,3) известно, и оно равно 27. То есть перебирать надо примерно 3^{27} вариантов, это долго. См. таблицу отсюда.

А общих доказательств на данный момент известно много, причём среди них есть достаточно новые, которые технически проще известных ранее. Помимо знаменитой брошюры Хинчина, есть интересный текст Вадима Бугаенко.

ссылка

отвечен 28 Май '17 18:06

10|600 символов нужно символов осталось
Ваш ответ

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

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

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

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

отмечен:

×1,476

задан
28 Май '17 16:37

показан
354 раза

обновлен
28 Май '17 18:06

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

по почте:

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

по RSS:

Ответы

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

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