Kỷ niệm định lý Raisky

Kỷ niệm định lý Raisky

A.ROMANOV

50

NĂM TRƯỚC, một bài báo của học sinh trường Dmitry Raisky [1] với sự tiến bộ đáng kể trong bài toán do Hadwiger đặt ra [2] đã được gửi đến TẠP CHÍ “TOÁN HỌC GHI CHÚ”. Dmitry đã chứng minh định lý sau: Khi tô màu một mặt phẳng bằng ba màu (chia nó thành ba tập hợp riêng biệt), bạn luôn có thể chọn màu trong đó tất cả các khoảng cách được thực hiện, tức là với bất kỳ dương d nào, có hai điểm ở khoảng cách d được tô màu bằng màu đã chọn. Định lý Raisky là sự củng cố đáng chú ý của định lý được anh em Moser chứng minh năm 1961 rằng khi một mặt phẳng được tô bằng ba màu thì sẽ có hai điểm cùng màu cách nhau 1. Khi chuẩn bị bài báo [1] để xuất bản, định lý đã được khái quát hóa thành không gian N chiều và được chỉnh sửa đáng kể. Kết quả là, tác phẩm của sinh viên này trở nên khó đọc và không thể tiếp cận được đối với các nhà toán học trẻ. Ở đây tôi đã cố gắng tạo lại phiên bản gốc lời giải. Tôi biết ơn N.N. Konstantinov, người vào năm 1971 đã cho tôi biết cách chứng minh định lý Raisky. Konstantinov đã giúp Dmitry chuẩn bị bài báo và nếu không có sự tham gia của anh ấy thì việc xuất bản khó có thể thực hiện được.

Tích được xác định theo cách này chứa tối đa $n_{◊} k$ vectơ khác nhau, vì tổng vectơ cho các cặp khác nhau có thể là $совпадать.^{Лемма} 1.$ Nếu chúng ta xem xét phép quay của chùm tia k theo một góc tùy ý, thì chỉ với một số góc quay hữu hạn, tích của chùm tia n cố định và chùm tia k quay sẽ chứa ít hơn $n_{◊} k$ vectơ khác nhau. Thật vậy, có thể chọn hai vectơ khác nhau a, b từ chùm tia n và hai vectơ khác nhau c, d từ chùm tia k chỉ bằng một số hữu hạn cách. Đối với mỗi bộ bốn vectơ như vậy, hãy xem xét phép quay của chùm tia k qua một góc D và so sánh tổng của các vectơ $a_{+} c_{D}$ và $b_{+} d_{D}$. Vì các đường tròn cắt nhau ở nhiều nhất hai điểm, nên nhiều nhất hai góc D có thể cho các tổng này bằng nhau, điều này chứng tỏ Bổ đề $1.^{Лемма} 2.$ Nếu tích của tia n và tia k chứa n ◊ k vectơ khác nhau, thì n ◊ k đầu của các vectơ này tạo thành n hình thu được bằng cách dịch song song của con trỏ k và k hình thu được

Bổ đề phụ trợ

Cho một hình gồm n điểm khác nhau trên mặt phẳng—một con trỏ n. Hãy chọn một trong những điểm này và gọi chùm tia n là một tập hợp các vectơ đi từ điểm này đến tất cả các điểm của con trỏ n (một trong các vectơ của chùm tia n là vectơ rỗng). Chúng ta hãy định nghĩa tích của chùm tia n và chùm tia k là một tập hợp các vectơ a + c, trong đó vectơ a được lấy từ chùm tia n và c từ chùm tia k.

DOI: https://doi.org/10.4213/kvant20190702

Cơm. 1

được tính bằng cách chuyển song song điểm n (Hình 1).

Chứng minh định lý

Giả sử rằng tuyên bố đó là sai và có một cách tô màu mặt phẳng theo ba màu mà không thể chọn một màu trong đó tất cả các khoảng cách đều được thực hiện. Sau đó, đối với cuốn sách tô màu này, mỗi màu có

11

DỊP KỈ NIỆM

CÁC ĐỊNH LÝ

khoảng cách không thể tồn tại giữa hai điểm là màu sắc. Chúng ta hãy xem xét máy dò 7 điểm do anh em nhà Moser đề xuất, mà Raisky gọi là “máy dò” (Hình 2). Tất cả các đoạn được vẽ đều có độ dài 1. Bằng cách liệt kê đơn giản, bạn có thể xác minh rằng nếu từ

THIÊN ĐƯỜNG

trong mọi thăm dò màu 1 trên 7 điểm, không có nhiều hơn hai màu 1, trong bất kỳ thăm dò màu 2 trên 7 điểm nào, không có nhiều hơn hai màu 2, và trong mọi thăm dò màu 3 trên 7 điểm, không có nhiều hơn hai màu 3. Do đó, không quá $2_{◊} 7^{2}$ điểm có thể được tô màu trong mỗi màu, tổng cộng không quá $6_{◊} 7^{2}$ điểm trong số $7^{3}$ có ​​thể được tô màu. Bằng chứng đã hoàn tất.

trường hợp đa chiều

Cơm. 2

chọn ba điểm bất kỳ trong số bảy điểm này thì có hai điểm được chọn nối với nhau bằng một đoạn thẳng. Định lý Moser ngay lập tức suy ra từ điều này. Với mỗi màu chúng ta sẽ có đầu dò 7 điểm riêng, trong đó thay vì 1 sẽ là khoảng cách còn thiếu ở màu này. Hãy chọn một điểm tùy ý trên mặt phẳng và xem xét tất cả các vectơ của chùm tia đi ra từ điểm này. Hãy đánh số màu tùy ý và xem xét đầu dò cho màu 1. Trong mỗi đầu dò trong số ba đầu dò 7 điểm, hãy chọn một trong 7 điểm, ví dụ $A_{4}$. Sau đó, mỗi đầu dò có 7 tia riêng. Theo Bổ đề 1, chúng ta xoay đầu dò 7 điểm cho màu 2 theo một góc sao cho tích của 7 tia 1 và 2 chứa $7^{2}$ vectơ khác nhau (đó là 49 tia) và xoay đầu dò 7 điểm cho màu 3 theo một góc sao cho tích của 49 tia và 7 tia này chứa $7^{3}$ vectơ khác nhau. Theo Bổ đề 2, các đầu của các vectơ $7^{3}$ này - $7^{3}$ các điểm khác nhau trên mặt phẳng - tạo thành 49 đầu dò cho màu 3, chúng cũng tạo thành 49 đầu dò cho màu 2 và 49 đầu dò cho màu 1. Để hoàn thiện chứng minh, chỉ cần lưu ý rằng trong

Bài báo của Raisky đưa ra cách chứng minh định lý về không gian n chiều: Cho các tập hợp $A_{1}, A_{2},^{…}, A_{n} +_{1}$ tạo thành một lớp phủ của không gian Euclide n chiều $R^{n} (n >$ 1); thì trong số chúng có một tập hợp $A_{i}$ sao cho với mọi d > 0 tồn tại một cặp điểm từ tập hợp này, khoảng cách giữa chúng bằng d. Để chứng minh định lý ở dạng này, không cần có ý tưởng mới, ngoại trừ việc xây dựng thăm dò trong $R^{n}$ và chứng minh Bổ đề 1. Để không hy sinh khả năng trình bày, chúng ta xét trường hợp không gian ba chiều; đối với kích thước lớn, những khó khăn hoàn toàn là kỹ thuật. (Lưu ý rằng trong bài viết của Raisky, bằng chứng đã được chỉnh sửa đáng kể; ở đây tôi đã cố gắng tái tạo phiên bản gốc.) Hãy xây dựng một thăm dò cho $R^{3}$. Raisky gọi trục xoay là một đỉnh 5 điểm gồm 4 đỉnh của một tứ diện đều có cạnh d và một điểm b khác, đối xứng với một trong các đỉnh của nó - đỉnh a - so với mặt (Hình 3). Ông gọi đầu dò là đầu dò 9 điểm, thu được từ hai trục quay, kết hợp bởi các đỉnh a và quay sao cho khoảng cách giữa các điểm b của các trục quay này cũng bằng d (Hình 4). Cơm. 3

12

KVANT 2019/№7

Bổ đề 2 thay đổi một chút. Tích của tia n và tia k chứa n k vectơ, có tính đến bội số và n k đầu của các vectơ này tạo thành n hình thu được bằng cách dịch song song của con trỏ k và k hình thu được bằng cách dịch song song của con trỏ n. Mỗi điểm của tích các ròng rọc xuất hiện trong những hình này nhiều lần bằng bội số của điểm. Với cách tiếp cận này, trường hợp nhiều chiều chỉ khác với trường hợp hai chiều ở thiết kế đầu dò.

Ước tính hàng đầu

Cơm. 4

Rõ ràng là có sự quay trục chính như vậy. Chứng minh Bổ đề 1 cần sửa đổi một chút. Đối với một n con trỏ cho trước, hãy chọn một mặt phẳng trong $R^{3}$ sao cho hình chiếu của n con trỏ lên mặt phẳng này chứa n điểm khác nhau. Chúng ta hãy chọn vị trí ban đầu (xoay) của con trỏ k so với mặt phẳng này sao cho hình chiếu của nó chứa k điểm khác nhau. Trên mặt phẳng, chúng ta có chùm tia n và chùm tia k, trong đó Bổ đề 1 hợp lệ. Chúng ta hãy xét chuyển động quay của chùm tia k ban đầu quanh một đường thẳng vuông góc với mặt phẳng đã chọn. Hình chiếu lên mặt phẳng chứa $n_{◊} k$ các vectơ khác nhau, điều này chứng tỏ Bổ đề 1 cho $R^{3}$. Phần còn lại của bằng chứng không thay đổi.

Trước khi bài báo của Raisky được xuất bản, người ta đã biết cách tô màu mặt phẳng bằng 7 màu, trong đó hai điểm bất kỳ cách nhau 1 đều được tô bằng các màu khác nhau. Màu sắc này dựa trên việc chia mặt phẳng thành các hình lục giác đều đều bằng nhau. S.B. Stechkin nhận thấy (và, với sự cho phép của Raisky, đã chèn nó vào bài viết) rằng mặt phẳng có thể được chia thành 6 tập hợp sao cho không phải tất cả các khoảng cách đều được thực hiện trên mỗi tập hợp đó. Yếu tố thiết kế bao gồm 4 hình lục giác đều và 8 hình tam giác đều. Bằng cách chuyển song song, toàn bộ mặt phẳng được lát bằng phần tử này, như trong Hình.

Tối ưu hóa chứng minh định lý Raisky

Chứng minh được đề xuất không sử dụng những ý tưởng còn thiếu trong phiên bản gốc của Raisky. Hóa ra là chúng ta có thể từ chối xét các phép quay làm cho các điểm không trùng nhau (Bổ đề 1). Thay vào đó, mỗi vectơ của tích của chùm tia n và chùm tia k có thể được gán một bội số - số tùy chọn để chọn một vectơ từ chùm tia n và một vectơ từ chùm tia k mà tổng của các vectơ trùng nhau.

Cơm. 5

Hình 5. Tất cả các hình tam giác đều mở, các đỉnh dưới và bên phải của hình lục giác không thuộc các hình này. Nếu chúng ta lấy cạnh của tam giác là 1 thì khoảng cách $d_{1} = 2$ không được nhận ra như nhau trên các bộ $A_{1},^{…}, A_{4}$

(Tiếp theo trang 23)