Tô màu mặt phẳng và định lý Van der Waerden về cấp số cộng

Kvant 1983, số 6 tr. 35-38 Thẻ V5S8

Bản dịch tự động sơ bộ, chất lượng thấp: có thể còn lỗi và câu chữ chưa tự nhiên. Bản này sẽ được thay bằng bản dịch tốt hơn. Bản gốc →

Định lý và tô màu mặt phẳng
Van der Waerden về sự tiến triển
S. N. BESPOMYATNYKH

Trong lưu ý này, chúng tôi sẽ chứng minh tính tổng quát hóa cực độ sau đây của kết quả bài toán M750.

Định lý tô màu. Hãy tô mỗi ô của một tờ giấy ca rô vô hạn bằng một trong N màu. Sau đó, đối với bất kỳ tập hợp ô $a_1, \dots, a_l$ nào cũng có một tập hợp các ô có màu giống hệt nhau $b_1, \dots, b_l$ , tương tự như tập hợp ô đầu tiên theo nghĩa (xem Hình 1) $B_i B_j = d A_i A_j$ với tất cả i, j=1, …, l, $e d e A_1, \dots, A_l, B_1, \dots, B_l$ lần lượt là tâm của các ô $a_1, \dots, a_l, b_1, \dots, b_l$ và d là một số tự nhiên nào đó; nói cách khác, các hình được tạo bởi tâm của các ô $b_1, \dots, b_l$ và $a_1, \dots, a_l$ tương ứng với d.

Hình 1.

Hơn nữa, một tập hợp ô như vậy có thể được tìm thấy trong bất kỳ hình vuông $m \times m$ nào, trong đó m là một số đủ lớn tùy thuộc vào số lượng màu N và tập hợp $a_1, \dots, a_l$ đã cho.

(Xin lưu ý: “sự giống nhau của các tập hợp ô” không có nghĩa hoàn toàn giống với khái niệm thông thường về “sự giống nhau của các hình”!).

Lịch sử của định lý này rất thú vị. Năm 1928, một nhà toán học làm việc tại một trung tâm toán học lớn - Göttingen, đã phải đối mặt với câu hỏi sau: liệu có thể nói rằng đối với bất kỳ phép chia nào của tập hợp số tự nhiên thành hai phần (hoặc thành một số hữu hạn các phần), mặc dù ở một trong số chúng sẽ có một cấp số cộng có độ dài cho trước lớn tùy ý? Gần như có vẻ rất tích cực rằng đáp số ở đây là tích cực. Tuy nhiên, không thể chứng minh được điều này, bất chấp sự đơn giản rõ ràng của bài toán, và chẳng bao lâu nó đã trở thành chủ đề được mọi người quan tâm. Người đầu tiên bổ sung mô-đun này là người Hà Lan B. L. Van der Waerden, người sau này trở thành nhà toán học nổi tiếng. Sau vài tuần làm việc, ông đã tìm ra một bằng chứng không đơn giản nhưng hoàn toàn cơ bản, dựa trên việc sử dụng khéo léo quy nạp toán học và “nguyên lý Dirichlet” (ví dụ, xem «Kvant», 1977, số 2, trang 17). Vào những năm 1940, định lý Van der Waerden được mở rộng cho trường hợp n chiều; định lý tô màu là trường hợp có chiều n=2.

Đây là một công thức của định lý Van der Waerden, phần nào khái quát hóa định lý bài toán ban đầu.

Đối với bất kỳ số N và l nào, người ta có thể chỉ định một số m=m (N, l) sao cho nếu một đoạn của chuỗi tự nhiên có độ dài m được phân chia tùy ý thành N lớp thì ít nhất một trong số chúng chứa cấp số cộng có độ dài l.

Chúng ta hãy chỉ ra cách suy ra định lý này từ định lý tô màu. Lấy m số tự nhiên liên tiếp bất kỳ và đánh số các cột của hình vuông $m \times m$ theo chúng; chia những số này thành N lớp là có thể so sánh được

tô màu hình vuông bằng $N$ màu, trong đó tất cả các ô của tất cả các cột có số nằm trong cùng một lớp sẽ nhận cùng một màu (Hình 2). Bây giờ đặt $a_1, \dots, a_1$ là một hàng ngang gồm $l$ ô liên tiếp. Sau đó, theo định lý tô màu, đối với $m$ đủ lớn, trong hình vuông của chúng ta có một tập hợp các ô liên kết đơn $b_1, \dots, b_l$ , một tập hợp tương tự $a_1, \dots, a_l$ , tức là một hàng ngang các ô cách đều nhau. Rõ ràng là số cột chứa các ô $b_1, \dots, b_l$ tạo thành cấp số cần thiết (sự khác biệt $d$ của cấp số này bằng “hệ số tương tự” của các bộ $a_1, \dots, a_l$ và $b_1, \dots, b_l$ ).

Chuyển sang phần chứng minh định lý tô màu, các điều kiện cần xem xét không phải là các tập ô $a_1, \dots, a_l$ tùy ý mà là các lưới “chuẩn” - chẳng hạn như trong Hình 3. Rõ ràng là điều này sẽ không xây dựng tính tổng quát, bởi vì bất kỳ tập hợp ô nào cũng có thể được hoàn thành thành một “tiêu chuẩn” và nếu câu lệnh

Hình 2.

Hình 3.

Nếu định lý được chứng minh cho tập bổ sung - “tiêu chuẩn” - thì nó cũng sẽ hoàn chỉnh cho tập ban đầu. Tập hợp các ô tương tự như tập hợp “chuẩn”, gọi là hệ số tương tự - hệ số chuỗi; chuỗi hình vuông sẽ được gọi là tập hợp các ô vuông tắc nghẽn bao gồm các ô của bảng vô hạn của chúng ta, các ô phía dưới bên trái tạo thành một chuỗi (rõ ràng, bất kỳ ô tương ứng nào của các ô vuông như vậy cũng tạo thành một chuỗi). Cuối cùng, hai hình vuông có màu đồng nhất được gọi là có màu giống hệt nhau, nghĩa là màu sắc của chúng trùng nhau trong quá trình chuyển song song kết hợp các hình vuông.

Vì vậy, chúng ta phải chứng minh rằng, bất kể các số $N$ và $l$ , đối với một $m = m(N, l)$ đủ lớn trong hình vuông $m \times m$ , được tô màu tùy ý bằng các màu $N$ , sẽ luôn có một chuỗi đơn sắc $b_1, \dots, b_l$ có độ dài $l$ .

Việc chứng minh sẽ bằng quy nạp trên $l$ .

Rõ ràng, đối với $l=1$ , chúng ta có thể lấy $m(N, 1)=1$ và đối với $l=2-m(N, 2)=N+1$ (nguyên lý Dirichlet!). Bây giờ chúng ta giả sử rằng phát biểu của định lý đúng với chuỗi độ dài $l$ với mọi góc lớn hơn $N$ , và chúng ta sẽ chứng minh điều đó cho chuỗi độ dài $l+1$ .

Đầu tiên chúng ta hãy giải thích ý tưởng của bằng chứng. Giả sử có một chuỗi $l+1$ hình vuông $K_1, K_2, \dots, K_{l+1}$ và trong mỗi hình vuông $K_i$ , một chuỗi $l+1$ ô $b_{i,1}, b_{i,2}, \dots, b_{i,l+1}$ được chọn và các chuỗi này nằm ở vị trí bằng nhau trong các ô vuông (xem Hình 4, trong đó $l=4$ ). Sau đó, từ các ô $b_{i,j}$ có thể tạo thành một chuỗi $l+1$ khác có dạng $b_{1,j}, b_{2,j}, \dots, b_{l+1,j}$ ( $j=1, \dots, l+1$ ) - trong Hình 4, một chuỗi như vậy cho $j=l+1$ được hiển thị bằng màu hồng - và một chuỗi khác $b_{1,1}, b_{2,2}, \dots, b_{l+1,l+1}$ với hệ số lớn hơn một chút - những ô này được khoanh tròn trong hình. Nếu biết rằng các hình vuông $K_{1,b}, \dots, K_{l,b}$ cùng loại và các ô $b_{1,1}, b_{1,2}, \dots, b_{1,l}$ (và cùng với chúng là tất cả các ô $b_{i,j}$ , trong đó $i, j \leq l$ ) có cùng màu, thì trong mỗi chuỗi trong số ba chuỗi: $b_{1,1}, b_{1,2}, \dots, b_{1,l+1}$ (chuỗi trong hình vuông $K_1$ ), $b_{1,1},$

Hình 4.

$b_{2,2}, \dots, b_{l+1,l+1}$ (chuỗi có khung) và $b_{1,l+1}, b_{2,l+1}, \dots, b_{l+1,l+1}$ (“sê-ri màu hồng”) tất cả các ô, có lẽ ngoại trừ ô cuối cùng, đều được liên kết đơn và các ô ngoài cùng là hai trong số các ô $b_{1,1}, b_{1,l+1}$ và $b_{l+1,l+1}$ (chúng được đặt trong hình *)). Do đó, nếu trong số ba ô này, chúng ta tìm thấy hai ô được liên kết đơn, chúng ta sẽ nhận được một chuỗi liên kết đơn có độ dài $l+1$ . Điều này chắc chắn sẽ đúng, theo nguyên lý Dirichlet, trong trường hợp có hai màu. Trong trường hợp có $N$ màu, cần phải xem xét không phải thiết kế hai giai đoạn mà là thiết kế $N$ (trong các hình vuông lớn, chọn một loạt các hình vuông nhỏ hơn, trong các hình vuông đó - thậm chí là các hình vuông nhỏ hơn, v.v. $N$ lần cho đến khi bạn nhận được các ô). Trong trường hợp này, kích thước của hình vuông ban đầu sẽ cho phép ở mỗi “giai đoạn” xác định chuỗi hình vuông $l+1$ tiếp theo, trong đó có những hình vuông được liên kết đơn - đây là lúc mà giả định quy nạp sẽ hữu ích.

Bây giờ chúng ta hãy đưa ra một chứng minh công thức của định lý tô màu. Chúng ta hãy xác định dãy $(q_r)$ , $r=0, 1, \dots, N$ , bằng sự tương ứng

$q_0 = 1, \quad q_{r+1} = 2m(N^{q_r^2}, l) \cdot q_r$

và gọi $m(N, l+1) = q_N(N^{q_r^2})$ là số màu của hình vuông $q_r \times q_r$ có $N$ màu; sự tồn tại của số $m(N^{q_r^2}, l)$ được đảm bảo bởi giả định quy nạp, $l=1, 2, \dots$ ).

Hình vuông $q_r \times q_r$ được gọi là hình vuông bởi ranh giới $r$ . Chúng ta hãy chứng minh rằng đối với bất kỳ màu nào của hình vuông $K$ cấp $r+1$ với $N$ màu, có thể chọn một loạt các hình vuông $K_1, K_2, \dots, K_{l+1}$ cấp $r$ trong đó tất cả các hình vuông, ngoại trừ một ô, $K_{l+1}$ , đều có một màu. Hãy tưởng tượng rằng hình vuông $K$ được chia thành các “ô” lớn, mỗi ô là một hình vuông có hạng $r$ ; “Màu” của ô như vậy sẽ được coi là bất kỳ cách nào trong số $N' = N^{q_r^2}$ cách tô màu ô đó bằng $N$ màu. Hãy chia hình vuông $K$ thành 4 hình vuông bằng nhau và chọn hình vuông phía dưới bên trái trong số chúng - $Q$ (Hình 4). Nó bao gồm $m' \times m'$ “ô”, trong đó $m' = m(N', l)$ được tô màu bằng $N'$ “màu” và theo định nghĩa của số $m'$ thì có một chuỗi $l$ “ô” có cùng một “màu”, tức là một chuỗi các ô vuông một mảnh $K_1, \dots, K_l$ cấp bậc $r$ . Những gì còn lại là phần bù của nó cho một chuỗi $l+1$ hình vuông cạnh hình vuông $K_{l+1}$ , có thể không vừa với $Q$ , nhưng chắc chắn sẽ vừa với hình vuông $K$ .

Bây giờ chúng ta hãy chứng minh rằng chúng ta có thể lấy $q_N$ làm số $m(N, l+1)$ . Đặt $K$ là một hình vuông tùy ý ở cạnh $m=q_N$ , nghĩa là có hạng $N$ , được tô màu $N$ . Chúng ta hãy chọn trong đó các ô vuông $K(1), \dots, K(l+1)$ có thứ hạng $N-1$ , $l$ đầu tiên trong số đó là liên kết đơn. Gọi $d_1$ là hệ số của chuỗi này. Chúng ta hãy chọn trong hình vuông $K(1)$ một loạt các hình vuông $K(1, 1), K(1, 2), \dots, K(1, l+1)$ có thứ hạng $N-2$ , $l$ đầu tiên trong số đó là liên kết đơn. Đặt $d_2$ là hệ số của chuỗi này và đặt $K(i, j)$ là bình phương thu được từ $K(1, j)$ khi được chuyển, kết hợp $K(1)$ và $K(i)$ , $i=2, 3, \dots, l+1$ , tức là khi được chuyển sang vectơ $d_1A_1A_i$ (nhớ lại rằng $A_1, A_2, \dots$ là tâm của các ô được tập “chuẩn” $a_1, a_2, \dots$ ). Hãy tiếp tục quá trình này bằng cách chọn trong hình vuông $K(1, 1)$ một chuỗi $K(1, 1, 1), K(1, 1, 2), \dots, K(1, 1, l+1)$ các ô vuông xếp hạng $N-3$ với hệ số $d_3$ và “phân tán” nó giữa các ô vuông của chúng ta $K(i, j)$ , v.v. Sau $N$ bước, chúng ta sẽ thu được các ô vuông xếp hạng 0, tức là các ô - $K(i_1, i_2, \dots, i_N)$ ( $i_k=1, \dots, l+1$ ). Mỗi ô vuông này là liên kết cuối cùng trong chuỗi các ô vuông xếp chồng lên nhau có thứ hạng cao hơn: $K(i_1) \supset K(i_1, i_2) \supset \dots \supset K(i_1, i_2, \dots, i_N)$ . Xét quy tắc dựng dãy hình vuông từ đây

Dễ dàng suy ra các tính chất sau:

các hình vuông $K(i_1, i_2, \dots, i_s, i_{s+1}, \dots, i_r)$ và $K(i'_1, i'_2, \dots, i'_s, i_{s+1}, \dots, i_r)$ có chỉ số $s$ đầu tiên không vượt quá $l$ (và các hình còn lại giống nhau) có giá trị đơn; cụ thể là, đã cho các ô $p$ và $q$ ( $p, q \geqslant 0, p+q < N$ ) $b_i = K(1, \dots, 1, i, \dots, i, l+1, \dots, l+1)$ (1)

có cùng màu cho tất cả $i=1, \dots, l$ ;

vectơ nối tâm của các hình vuông $K(i_1, i_2, \dots, i_r)$ và $K(j_1, j_2, \dots, j_r)$ bằng $d_1 A_{i_1} \vec{A}_{j_1} + d_2 A_{i_2} \vec{A}_{j_2} + \dots + d_r A_{i_r} \vec{A}_{j_r}$ ; cụ thể, đối với các ô $b_i$ và $b_j$ (xem (1)) nó bằng $(d_{p+1} + d_{p+2} + \dots + d_{N-q}) A_i A_j$ .

Bây giờ chúng ta không còn xa mục tiêu nữa. Hãy xem xét các ô $N+1$ sau:

$K(l+1, l+1, l+1, \dots, l+1), K(1, l+1, l+1, \dots, l+1), K(1, 1, l+1, \dots, l+1), \dots, K(1, 1, 1, \dots, 1)$ . Theo nguyên lý Dirichlet, ít nhất hai trong số đó là rõ ràng. Để xác định điều này, hãy đặt các ô $b_1 = K(1, 1, 1, l+1, \dots, l+1)$ và $b_{l+1} = K(1, l+1, l+1, l+1, \dots, l+1)$ (xem (1) với $p=1, q=N-3$ ). Sau đó, từ thuộc tính 1) và 2), theo sau là các ô $b_1, b_2, \dots, b_{l+1}$ , trong đó $b_i = K(1, i, i, l+1, \dots, l+1)$ , tạo thành chuỗi một liên kết mong muốn (với hệ số $d_2 + d_3$ ). Định lý tô màu được chứng minh.

Nếu chủ đề này khiến bạn quan tâm, chúng tôi khuyên bạn nên tham khảo cuốn sách của A. Ya. Khinchin “Ba viên ngọc của lý thuyết số”, cung cấp bằng chứng chi tiết về định lý Van Waerden về cấp số nhân.

Bài tập

Chứng minh rằng định lý tô màu cho phép giải được mọi mệnh đề bài toán M750.
Chứng minh rằng nếu trong định lý Van Waerden thay từ “số học” bằng “hình học” thì nó vẫn đúng. (Nhân tiện, chính Van der Waerden đã chứng minh định lý của mình cụ thể cho cấp số nhân.)
Chứng minh rằng với bất kỳ $n$ nào và với bất kỳ phân vùng nào của chuỗi tự nhiên thành các lớp $N$ thì ít nhất một trong số chúng chứa $n$ cấp số cộng có độ dài $n$ , cấp số đầu tiên tạo thành một cấp số nhân.
Cho một ví dụ về cách chia một chuỗi tự nhiên thành hai tập con, không tập nào chứa:

a) cấp số cộng vô hạn;

b) không phải cấp số cộng vô hạn cũng không phải cấp số nhân vô hạn.

Cho một ví dụ về tô màu các ô bằng hai màu, trong đó không có vô số đường thẳng đứng và vô số đường ngang, tại giao điểm của chúng sẽ thu được tâm của các ô liên kết đơn.
Chứng minh rằng với bất kỳ cách tô màu ô nào với màu $k$ đều có vô số đường thẳng đứng $\{x_i\}$ và vô số đường ngang $\{y_i\}$ ( $i=1, 2, 3, \dots$ ) sao cho tại giao điểm của các đường $y_i$ và $x_j$ , trong đó thu được $i \geqslant j$ , tâm của các ô liên kết đơn.

Chuỗi xoắn DNA trái

(Để bắt đầu, xem trang 31)
khả năng tồn tại, như người ta nghĩ trước đây, ở dạng B.

Câu hỏi đặt ra, điều gì sẽ xảy ra nếu trong một phân tử DNA dài (hãy nhớ rằng một phân tử dài thông thường chứa các nucleotide thập phân) có một đoạn có trình tự … CHCH …?

Các thí nghiệm đã chỉ ra rằng khi xác định các điều kiện, vùng như vậy thực sự ở dạng Z, mặc dù xung quanh nó DNA vẫn ở dạng bình thường. Có bằng chứng cho thấy điều này cũng có thể xảy ra bên trong tế bào.

Việc phát hiện ra chuỗi xoắn trái và khả năng tồn tại của nó trong DNA “đang hoạt động” đã thu hút sự quan tâm lớn. Ở nhiều phòng thí nghiệm trên khắp thế giới, việc nghiên cứu một dạng mới hiện nay rất thú vị, các điều kiện để các phần DNA tương ứng được chuyển vào đó. Các nhà khoa học đang cố gắng tìm ra vai trò của dạng Z và cấu trúc chung của DNA làm thay đổi cấu trúc của nó đối với hoạt động của phân tử này trong tế bào.

Không còn nghi ngờ gì nữa, những năm tới sẽ còn có nhiều khám phá thú vị hơn nữa trong lĩnh vực này.