www.wikidata.uk-ua.nina.az

Число ван дер Вардена Теорема ван дер Вардена з теорії Рамсея стверджує що для будь яких натуральних чисел r displaystyl

Число ван дер Вардена

Теорема ван дер Вардена з теорії Рамсея стверджує, що для будь-яких натуральних чисел і існує таке додатне ціле число , що, якщо кожне з цілих чисел пофарбувати в один із різних кольорів, то знайдеться принаймні цілих чисел одного кольору, що утворюють арифметичну прогресію. Найменше таке називається числом ван дер Вардена . Названі на честь голландського математика ван дер Вардена.

Оцінка чисел ван дер Вардена Редагувати

Є два випадки, в яких число ван дер Вардена легко обчислити:

  1. коли число кольорів дорівнює 1, очевидно для будь-якого цілого , оскільки один колір виробляє тільки тривіальні розфарбування RRRR…RRR (якщо колір позначити ).
  2. якщо довжина необхідної арифметичної прогресії дорівнює 2, то , оскільки можна побудувати розфарбування, уникаючи арифметичних прогресій довжини 2, використовуючи кожен колір не більше одного разу, але використання будь-якого кольору двічі створює арифметичну прогресію довжини 2. (Наприклад, для найдовшим розфарбуванням, за якого не утворюється арифметична прогресія довжини 2, є RGB.)

Є тільки сім інших чисел ван дер Вардена, які відомі точно.

У таблиці наведено точні значення та межі значень .

k\r 2 кольори 3 кольори 4 кольори 5 кольорів 6 кольорів
3 9 27 76 >170 >223
4 35 293 >1048 >2254 >9778
5 178 >2173 >17 705 >98 740 >98 748
6 1132 >11 191 >91 331 >540 025 >816 981
7 >3703 >48 811  >420 217  >1 381 687 >7 465 909
8 >11 495  >238 400  >2 388 317    >10 743 258   >57 445 718
9 >41 265    >932 745    >10 898 729 >79 706 009 >458 062 329
10 >103 474   >4 173 724   >76 049 218 >542 694 970 >2 615 305 384
11 >193 941    >18 603 731  >30 551 357 >2 967 283 511 >3 004 668 671

Вільям Гауерс довів, що числа ван дер Вардена з обмежуються зверху

Елвін Берлекемп довів, що для простого числа , 2-колірне число ван дер Вардена обмежене знизу

Іноді також використовується позначення , яке означає найменше число таке, що будь-яке розфарбування цілих чисел в кольорів містить прогресію довжини кольору , для деяких . Такі числа називаються недіагональними числами ван дер Вардена.

Таким чином: .

Примітки Редагувати

  1. Gowers, Timothy. A new proof of Szemerédi's theorem : [ ][англ.] // Geometric and Functional Analysis : journal. — 2001. — Vol. 11, № 3. — С. 465—588. — DOI:10.1007/s00039-001-0332-9.
  2. Berlekamp, E. A construction for partitions which avoid long arithmetic progressions : [ ][англ.] // Canadian Mathematical Bulletin : journal. — 1968. — Vol. 11. — С. 409—414. — DOI:10.4153/CMB-1968-047-7.

Посилання Редагувати

Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри
Дата публікації:
Teorema van der Vardena z teoriyi Ramseya stverdzhuye sho dlya bud yakih naturalnih chisel r displaystyle r i k displaystyle k isnuye take dodatne cile chislo N displaystyle N sho yaksho kozhne z cilih chisel 1 2 N displaystyle 1 2 ldots N pofarbuvati v odin iz r displaystyle r riznih koloriv to znajdetsya prinajmni k displaystyle k cilih chisel odnogo koloru sho utvoryuyut arifmetichnu progresiyu Najmenshe take N displaystyle N nazivayetsya chislom van der Vardena W r k displaystyle W r k Nazvani na chest gollandskogo matematika van der Vardena Ocinka chisel van der Vardena RedaguvatiYe dva vipadki v yakih chislo van der Vardena W r k displaystyle W r k nbsp legko obchisliti koli chislo koloriv r displaystyle r nbsp dorivnyuye 1 ochevidno W 1 k k displaystyle W 1 k k nbsp dlya bud yakogo cilogo k displaystyle k nbsp oskilki odin kolir viroblyaye tilki trivialni rozfarbuvannya RRRR RRR yaksho kolir poznachiti R displaystyle R nbsp yaksho dovzhina K displaystyle K nbsp neobhidnoyi arifmetichnoyi progresiyi dorivnyuye 2 to W r 2 r 1 displaystyle W r 2 r 1 nbsp oskilki mozhna pobuduvati rozfarbuvannya unikayuchi arifmetichnih progresij dovzhini 2 vikoristovuyuchi kozhen kolir ne bilshe odnogo razu ale vikoristannya bud yakogo koloru dvichi stvoryuye arifmetichnu progresiyu dovzhini 2 Napriklad dlya r 3 displaystyle r 3 nbsp najdovshim rozfarbuvannyam za yakogo ne utvoryuyetsya arifmetichna progresiya dovzhini 2 ye RGB Ye tilki sim inshih chisel van der Vardena yaki vidomi tochno U tablici navedeno tochni znachennya ta mezhi znachen W r k displaystyle W r k nbsp k r 2 kolori 3 kolori 4 kolori 5 koloriv 6 koloriv3 9 27 76 gt 170 gt 2234 35 293 gt 1048 gt 2254 gt 97785 178 gt 2173 gt 17 705 gt 98 740 gt 98 7486 1132 gt 11 191 gt 91 331 gt 540 025 gt 816 9817 gt 3703 gt 48 811 gt 420 217 gt 1 381 687 gt 7 465 9098 gt 11 495 gt 238 400 gt 2 388 317 gt 10 743 258 gt 57 445 7189 gt 41 265 gt 932 745 gt 10 898 729 gt 79 706 009 gt 458 062 32910 gt 103 474 gt 4 173 724 gt 76 049 218 gt 542 694 970 gt 2 615 305 38411 gt 193 941 gt 18 603 731 gt 30 551 357 gt 2 967 283 511 gt 3 004 668 671Vilyam Gauers doviv sho chisla van der Vardena z R 2 displaystyle R geqslant 2 nbsp obmezhuyutsya zverhu 1 W r k 2 2 r 2 2 k 9 displaystyle W r k leqslant 2 2 r 2 2 k 9 nbsp Elvin Berlekemp doviv sho dlya prostogo chisla p displaystyle p nbsp 2 kolirne chislo van der Vardena obmezhene znizu 2 p 2 p W 2 p 1 displaystyle p cdot 2 p leqslant W 2 p 1 nbsp Inodi takozh vikoristovuyetsya poznachennya w r k 1 k 2 k r displaystyle w r k 1 k 2 ldots k r nbsp yake oznachaye najmenshe chislo w displaystyle w nbsp take sho bud yake rozfarbuvannya cilih chisel 1 2 w displaystyle 1 2 ldots w nbsp v r displaystyle r nbsp koloriv mistit progresiyu dovzhini k i displaystyle k i nbsp koloru i displaystyle i nbsp dlya deyakih i displaystyle i nbsp Taki chisla nazivayutsya nediagonalnimi chislami van der Vardena Takim chinom W r k w r k k k displaystyle W r k w r k k ldots k nbsp Primitki Redaguvati Gowers Timothy A new proof of Szemeredi s theorem angl Geometric and Functional Analysis journal 2001 Vol 11 3 S 465 588 DOI 10 1007 s00039 001 0332 9 Berlekamp E A construction for partitions which avoid long arithmetic progressions angl Canadian Mathematical Bulletin journal 1968 Vol 11 S 409 414 DOI 10 4153 CMB 1968 047 7 Posilannya RedaguvatiZavdannya tipu Van Der Varden Teoriya Ramseya Otrimano z https uk wikipedia org w index php title Chislo van der Vardena amp oldid 38149183