Теорема Ван дер Вардена

[PAV]

geomath в сообщении #177897 писал(а):

А во-вторых, сами подумайте хорошенько над басней про жемчужное зерно... Так ли уж оно ценно?

Я не собираюсь басни воспринимать буквально. В данном случае речь идет не о жемчужинах, а о математической теореме. Если Вы не видите в ней содержательного смысла - тогда займитесь чем-нибудь таким, в чем такой смысл находится. А не надо пытаться судить о чем-то таком, в чем ничего не понимаешь.

[geomath]

PAV в сообщении #177903 писал(а):

Я не собираюсь басни воспринимать буквально. В данном случае речь идет не о жемчужинах, а о математической теореме. Если Вы не видите в ней содержательного смысла - тогда займитесь чем-нибудь таким, в чем такой смысл находится. А не надо пытаться судить о чем-то таком, в чем ничего не понимаешь.

Трижды извиняюсь, но вы меня с другим участником спутали, однако успели-таки сказать обидную вещь. Я-то как раз пытаюсь углядеть в той теореме содержательный смысл и поэтому не буду спорить, а постараюсь сформулировать в связи с ней интересную математическую задачу...

[PAV]

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

Хотите сформулировать математическую задачу - замечательно, тогда формулируйте ее и оставьте в стороне оценочные рассуждения.

[geomath]

Возможно, эта задача тривиальна или ненова, да и решать ее я не собираюсь, однако лучше уж она пропадет здесь, чем в моей голове.

Рассмотрим конечную последовательность чисел 1, 2, ..., N, каждое из которых окрашено в один из M различных цветов. Пусть все цвета задействованы, но один из них преобладает, долю которого (относительное количество чисел этого цвета) обозначим d. Рассмотрим теперь арифметическую подпоследовательность этой последовательности, состоящую из чисел одинакового цвета и максимально длинную (среди всех таких подпоследовательностей), которую назовем доминантой данной последовательности. Требуется выписать минимальное значение d = d(M, N), при котором всякая доминанта будет иметь преобладающий цвет независимо от раскраски самой последовательности, лишь бы раскраска имела то же d. Например, d(2, 5) = 4/5.

[sceptic]

geomath писал(а):

Рассмотрим конечную последовательность чисел 1, 2, ..., N, каждое из которых окрашено в один из M различных цветов. Пусть все цвета задействованы, но один из них преобладает, долю которого (относительное количество чисел этого цвета) обозначим d. Рассмотрим теперь арифметическую подпоследовательность этой последовательности, состоящую из чисел одинакового цвета и максимально длинную (среди всех таких подпоследовательностей), которую назовем доминантой данной последовательности. Требуется выписать минимальное значение d = d(M, N), при котором всякая доминанта будет иметь преобладающий цвет независимо от раскраски самой последовательности, лишь бы раскраска имела то же d. Например, d(2, 5) = 4/5.

1. Что в данном контексте означает "один из цветов преобладает"?
2. Что такое "арифметическая подпоследовательность" в последовательности 1, 2, ..., N?
3. Максимально длинная: а)среди подпоследовательностей одинакового цвета данной раскраски множества {1, 2, ..., N} в М цветов; б) среди подпоследовательностей одинакового цвета по всем раскраскам в М цветов этого же множества?

[geomath]

sceptic в сообщении #180211 писал(а):

1. Что в данном контексте означает "один из цветов преобладает"?
2. Что такое "арифметическая подпоследовательность" в последовательности 1, 2, ..., N?
3. Максимально длинная: а)среди подпоследовательностей одинакового цвета данной раскраски множества {1, 2, ..., N} в М цветов; б) среди подпоследовательностей одинакового цвета по всем раскраскам в М цветов этого же множества?

1. Количество чисел, окрашенных в преобладающий цвет, является наибольшим, т.е. оно строго больше количества чисел, окрашенных в любой другой цвет, по отдельности. Впрочем, можно попробовать и не по отдельности, а всех вместе.

2. Каждый следующий член подпоследовательности больше предыдущего на одно и то же число.

3. Максимально длинная для данной раскраски последовательности.

Например, в последовательности 1, 2, 3, 4, 5 преобладает красный цвет, а доминантой является любая пара чисел одного цвета. Однако доминанта 2, 3 оказывается синего, не преобладающего цвета. Поэтому три красных числа, т.е. d = 3/5, - это маловато в случае M = 2 и N = 5 и должно быть не три, а четыре красных числа, так что d(2, 5) = 4/5.

[ДДмитрий]

geomath писал(а):

Возможно, эта задача тривиальна или ненова, да и решать ее я не собираюсь, однако лучше уж она пропадет здесь, чем в моей голове.

Рассмотрим конечную последовательность чисел 1, 2, ..., N, каждое из которых окрашено в один из M различных цветов. Пусть все цвета задействованы, но один из них преобладает, долю которого (относительное количество чисел этого цвета) обозначим d. Рассмотрим теперь арифметическую подпоследовательность этой последовательности, состоящую из чисел одинакового цвета и максимально длинную (среди всех таких подпоследовательностей), которую назовем доминантой данной последовательности. Требуется выписать минимальное значение d = d(M, N), при котором всякая доминанта будет иметь преобладающий цвет независимо от раскраски самой последовательности, лишь бы раскраска имела то же d. Например, d(2, 5) = 4/5.

Что то мне кажется, что все это не очень тривиально. Во всяком случае, если не ошибаюсь, задача поиска такого минимального $\omega(k)$, что последовательность $1,2,\ldots,\omega(k)$, раскрашенная всего в ДВА цвета, гарантированно имеет "одноцветную" арифметическую прогрессию длины $k$ еще не решена даже для небольших (порядка 10) значений $k$. Прокомментируйте (подтвердите или опровергните) это, если кто знает. А то вот школьникам собрался об этом рассказать, да не уверен правильно ли все это.

[maxal]

ДДмитрий
см. http://en.wikipedia.org/wiki/Van_der_Waerden_number

[Виктор Ширшов]

PAV в сообщении #177865 писал(а):

Цена - понятие субъективное. Помните басню Крылова про петуха и жемчужное зерно?

Цитата:

Навозну кучу разрывая,
Петух нашел Жемчужное Зерно
И говорит: «Куда оно?
Какая вещь пустая!
Не глупо ль, что его высоко так ценят?
А я бы, право, был гораздо боле рад
Зерну ячменному: оно не столь хоть видно,
Да сытно».

Невежи судят точно так:
В чем толку не поймут, то всё у них пустяк.

А у академика Б. Мигдала есть ещё такое высказывание про жемчужину, может быть, чуточку парафразированное мною: "Прежде чем разрывать кучу навоза, сначала убедитесь, какова вероятность того, что там есть жемчужина". Эти слова он сказал в своём обращении к молодым учёным.

[Alexander Soifer]

Ну если Академик велит в дерьме не копаться... то надо бы ослушаться :-).

Когда я был студентом, мой друг-доцент Алик Блох сказал:

"Из ложки дёгтя можно сделать бочку мёда."

Эта новая мудрость мне позволила немедленно дорешать проблему, ставшую диссертацией.

[Elena31]

geomath

Цитата:

То "новое, значительно более простое и прозрачное доказательство" теоремы Ван дер Вардена, которое излагает Хинчин, было найдено М.А. Лукомской и опубликовано в УМН в 1948 году. Кто такая Лукомская? Что с ней стало? Если она была молодой тогда, то со временем имела неплохой шанс вырасти в знаменитого математика... Однако ничего о ней мне в Интернете найти не удалось. Может, она сменила фамилию?

Лукомская Мира Абрамовна (моя мама) родилась 1 мая 1900 года, умерла 30 октября 1976 года. Окончила Ленинградский университет, физмат, много лет проработала доцентом Белорусского государственного университета. Работы, главным образом, по дифференциальным уравнениям. Как она решала упомянутую Вами задачу, я хорошо помню.
С уважением, Е.Н.Ламбина

[Alexander Soifer]

geomath в сообщении #177376 писал(а):

geomath писал(а):

Это вы не меня процитировали, а вот эту книжку.

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

http://www.amazon.com/gp/product/0387746404/ref=cap_pdp_dp_0,

ее автор, математик-еврей, наш бывший соотечественник, самым скрупулезным образом рассматривает и оценивает с моральной точки зрения тот факт, что профессор Ван дер Варден, оставаясь голландским гражданином, преподавал математику в нацистском Лейпциге даже в течение тех пяти лет, когда Германия оккупировала Нидерланды.

А скажите мне, господин geomath, прочему Вы меня представили как "математик-еврей"?

Я ведь в Москве родился, и стало быть был русским, даром что КГБ-Милиция под "национальностью" понимали этническое проишождение. Вы ведь не из органов - они такие книги как "The Mathematical Coloring Book" не читают, и не "скачивают бесплатно".

Sincerely,
Alexander Soifer

[worm2]

Вот здесь: http://www.math.u-bordeaux.fr/~yuri/various/habtalk/indexru.html показано, как теорема Ван дер Вардена может быть использована для посрамления лжеучёных, откапывающих в религиозных текстах всяческие предсказания.

[Евгений Машеров]

Практическое приложение простое. Пояснить, как может возникнуть видимая регулярность, если это не результат какого-то целенаправленного воздействия.
Если, скажем, нашли в серии исторических дат отчётливо видимую последовательность - можно кричать о том, что вот перед нами фальсификация, а можно вспомнить, что такая последовательность возникнет всегда. И, стало быть, её наличие не доказывает ничего.

[ksp4]

Весь день пытался доказать, что на машине Тьюринга, которая не может ничего записывать на ленту, нельзя проверить, является ли данное слово палиндромом.

Пока придумал доказательство только с использованием упомянутой теоремы, да и то не уверен, что оно правильное.

Видимо, эта теорема может быть полезна, чтобы доказывать результаты типа,
что на таком-то языке программирования такую-то программу нельзя написать.