Теорема ван дер Вардена з теорії Рамсея стверджує, що для будь-яких натуральних чисел і існує таке додатне ціле число , що, якщо кожне з цілих чисел пофарбувати в один із різних кольорів, то знайдеться принаймні цілих чисел одного кольору, що утворюють арифметичну прогресію. Найменше таке називається числом ван дер Вардена . Названі на честь голландського математика ван дер Вардена.
Оцінка чисел ван дер Вардена Є два випадки, в яких число ван дер Вардена легко обчислити:
коли число кольорів дорівнює 1, очевидно для будь-якого цілого , оскільки один колір виробляє тільки тривіальні розфарбування RRRR…RRR (якщо колір позначити ). якщо довжина необхідної арифметичної прогресії дорівнює 2, то , оскільки можна побудувати розфарбування, уникаючи арифметичних прогресій довжини 2, використовуючи кожен колір не більше одного разу, але використання будь-якого кольору двічі створює арифметичну прогресію довжини 2. (Наприклад, для найдовшим розфарбуванням, за якого не утворюється арифметична прогресія довжини 2, є RGB.)
Є тільки сім інших чисел ван дер Вардена, які відомі точно.
У таблиці наведено точні значення та межі значень . k\r2 кольори3 кольори4 кольори5 кольорів6 кольорів392776>170>223435293>1048>2254>97785178>2173>>>61132>>>>7>3703>>>>8>>>>>9>>>>>10>>>>>11>>>>> Вільям Гауерс довів, що числа ван дер Вардена з обмежуються зверху
Елвін Берлекемп довів, що для простого числа , 2-колірне число ван дер Вардена обмежене знизу
Іноді також використовується позначення , яке означає найменше число таке, що будь-яке розфарбування цілих чисел в кольорів містить прогресію довжини кольору , для деяких . Такі числа називаються недіагональними числами ван дер Вардена.
Таким чином: .
Примітки
Посилання
Завдання типу Ван Дер Варден Теорія Рамсея