Предыдущая страница реферата | 1  2  3  4  5  6 | Следующая страница реферата

2                               ×           

3                                            

     1            2            3           

Доказав теорему Рамсея для арифметических прогрессий, Ван дер Варден применил эти знания к решению следующей задачи. Каково наименьшее значение n, гарантирующее существование одноцветной арифметической последовательности из, скажем, 10 членов, если каждое число от 1 до n напечатать любой произвольно выбранной из двух красок? Лучший ответ, который Ван дер Варден смог найти, выражался столь большим числом, что его невозможно было записать в обычном виде. Оно было больше миллиарда, больше чем 10 в степени миллиард.

В самом деле, чтобы выразить его результат, математики прибегают к последовательности функций, известной как иерархия Аккермана. Первая функция в этой иерархии называется просто DOUBLE(x). Как подсказывает название (double — значит, удвоить), эта функция удваивает значение x. Так DOUBLE(1) равно 2, DOUBLE(50) равно 100. Вторая функция, EXPONENT(x), может быть описана как 2 в степени x, и, следовательно, EXPONENT(3) равно 8. Можно также выразить EXPONENT через DOUBLE. Например, чтобы найти EXPONENT(3), мы удваиваем 1, затем удваиваем результат предыдущего действия и затем снова удваиваем результат. На самом деле любая функция в иерархии Аккермана определяется через предыдущую.

Итак, третью функцию этой иерархии, TOWER(x), можно выразить с помощью функции EXPONENT. TOWER(3), например, — это 2 в степени 2 в степени 2, что равно 2 в степени 4, т.е. 16. TOWER(x) иногда записывают в виде «башни» (tower — значит, башня) показателей степеней,

	2...2
2	2

где x — число двоек в этой башне. Но даже функция TOWER(x) растёт недостаточно быстро, чтобы можно было записать результат Ван дер Вардена.

Следующую функцию, известную под шуточным прозвищем WOW(x) (английское междометие WOW примерно соответствует русским «Ой!», «Ах!» и «Ну и ну!». — Перев.), можно найти, если начать с 1 и применить x раз функцию TOWER. Тогда,

WOW(1) = TOWER(1) = 2, WOW(2) = TOWER(2) = 4, WOW(3) = TOWER(4) = 65536.

Чтобы найти WOW(4), нужно вычислить TOWER(65536). Чтобы это сделать, нужно начать с 1 и применить функцию EXPONENT 65536 раз. Даже применение функции EXPONENT всего лишь пять раз даёт 265536, — число, которое, будучи записанным цифра за цифрой, заполнило бы две страницы этого журнала. На самом деле даже число, заполняющее все страницы всех книг и всю память всех компьютеров, всё же останется несравнимым с WOW(4).

Тем не менее, чтобы всё-таки записать результат Ван дер Вардена, придётся определить функцию, которая растёт ещё быстрее. Функция ACKERMANN(x) определяется последовательностью DOUBLE(1), EXPONENT(2), TOWER(3), WOW(4) и так далее. ACKERMANN(x) в конце концов растёт быстрее любой функции в этой иерархии. Доказательство Ван дер Вардена даёт следующий количественный результат: если числа 1, 2, ..., ACKERMANN(k) раскрашены двумя красками, то всегда существует одноцветная арифметическая прогрессия длиной k.

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

В 1987году, однако, израильский логик Саарон Шела из Еврейского университета в Иерусалиме добился крупного успеха. Шела широко признан как человек, лучше всех справляющийся с решением сложнейших задач в современной математике. Он сумел преодолеть барьер функции ACKERMANN и показал следующее: если целые числа от 1 до WOW(k) раскрасить в два цвета, то всегда найдётся одноцветная арифметическая прогрессия длиной k членов.

Несмотря на свою специализацию, Шела вовсе не использует в своём доказательстве каких-либо средств математической логики. В нём применены лишь элементарные (но чрезвычайно остроумные) математические идеи. Полностью выписанное, его доказательство занимает приблизительно четыре страницы, и большинство специалистов находит его более чётким, чем первоначальное доказательство Ван дер Вардена. Что самое важное, он обошёлся без двойной индукции. Он фиксирует число красок на двух (или любом другом конкретном значении) и затем проводит обычную индукцию: если утверждение верно для прогрессий длиной k членов, то оно также справедливо и для прогрессий длиной k+1.

Математики сейчас пытаются понять, можно ли улучшить доказательство Шелы, чтобы получить для теоремы Ван дер Вардена оценку порядка TOWER или даже EXPONENT. Один из нас (Грэм) предложил премию в размере 1000 долларов тому, кто докажет (или опровергнет) утверждение, что для всякого k раскрашенная в два цвета совокупность чисел от 1 до TOWER(k) содержит одноцветную арифметическую прогрессию из k членов.

Усилиями Рамсея, Эрдёша, Ван дер Вардена и многих других были заложены основы теории, носящей имя Рамсея. Пока что исследователи только начали изучать следствия этой теории. Она позволяет предположить, что структурная основа математики состоит из чрезвычайно больших чисел и множеств — объектов столь громадных, что их трудно даже выразить, а тем более постичь.

Когда мы научимся обращаться с этими большими числами, мы сможем найти математические соотношения, которые помогут инженерам создавать большие сети коммуникаций, а учёным распознавать упорядоченные структуры в крупномасштабных физических системах. Сегодня мы с лёгкостью прослеживаем в созвездиях на ночном небосводе следствие теории Рамсея. А какие структуры можно найти в множествах, размеры которых в ACKERMANN(9) раз больше?

Рис.4. Понятия теории Рамсея приложимы к геометрическим задачам вроде этой головоломки о шестиугольниках. Если длины всех сторон шестиугольников равны 0,45 единицы (единица длины может быть произвольной), то две точки внутри шестиугольника отстоят друг от друга самое большее на 0,9 единицы. Каждый шестиугольник окрашивается одним из семи цветов, так, что никакие два шестиугольника одного цвета не отстоят друг от друга меньше чем на 1,19 единицы. Никакие две точки одного цвета не находятся одна от другой на расстоянии, в точности равном единице. Пока что никто не смог определить, можно ли раскрасить плоскость шестью красками так, чтобы никакие две точки одного цвета не находились в точности на расстоянии одной единицы друг от друга.

Список литературы

Рекомендуем скачать другие рефераты по теме: антикризисное управление предприятием, allbest.





Предыдущая страница реферата | 1  2  3  4  5  6 | Следующая страница реферата