Обобщнная теорема Ван дер Вардена. Для любой клетчатой фигуры 𝐹 и для любого натурального 𝑘 существует такое 𝑁, что внутри любого квадрата 𝑁 × 𝑁, раскрашенного в 𝑘 цветов, найдётся одноцветная фигура, гомотетичная фигуре 𝐹. Доказательство можно вести двойной индукцией: по 𝑘 и по размеру фигуры |𝐹|. 122. Слабый индукционный переход обобщённой теоремы Ван дер Вардена: пусть теорема доказана для фигур размера 𝑛 и любого числа цветов, докажите для фигур размера 𝑛 + 1 и двух цветов. 123. Сильный индукционный переход обобщённой теоремы Ван дер Вардена: пусть теорема доказана для фигур размера 𝑛 и любого числа цветов, докажите для фигур размера 𝑛 + 1 и 𝑘 цветов

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

задан 28 Авг '19 20:58

1

Индукция по двум параметрам встречается довольно часто. Например, говорят "сначала по n, а при фиксированном n по k". Тогда при переходе от n к n+1 можно последовательно доказывать утверждение для случаев n+1,2, потом n+1,3, и так далее.

(28 Авг '19 23:32) falcao

Ну я примерно понимаю о чем Вы говорите, но может Вы знаете где есть доказательство этой теоремы таким методом? Просто осознание доказательства помогает привыкнуть к новым идеям

(29 Авг '19 0:16) sapere aude
1

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

(29 Авг '19 1:47) falcao

@falcao Спасибо за ссылку!

(29 Авг '19 2:30) sapere aude
10|600 символов нужно символов осталось
Знаете, кто может ответить? Поделитесь вопросом в Twitter или ВКонтакте.

Ваш ответ

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

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

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

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

отмечен:

×1,483
×970

задан
28 Авг '19 20:58

показан
166 раз

обновлен
29 Авг '19 2:30

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

по почте:

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

по RSS:

Ответы

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

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