跳至內容

范德瓦爾登定理

維基百科,自由的百科全書

范德瓦爾登定理數論中的一個定理,由荷蘭數學家范德瓦爾登發現。對於任意給定的正整數r和k,總存在正整數N,使得把數{1,2,……,N}染成r種顏色時, 對每一種染色方式,都存在k個數組成的等差數列染同一種顏色的。這個最小的N叫做范德瓦爾登數V(r,k)。這個定理與拉姆齊理論相關

例如,V(2,3)=9,因為可以把整數{1, 2, …, 8}塗成以下的顏色:

 1   2   3   4   5   6   7   8 
                       

但無論如何,都不能把數{1, 2, …, 9}染成兩種顏色,其中任何三個組成等差數列的正整數都不是同一種顏色的。

以下是一些已知的范德瓦爾登數:

V(2,3)=9
V(2,4)=35
V(2,5)=178
V(2,6)=1132
V(3,3)=27
V(4,3)=76