Tổ hợp - nó là gì?

65

Tổ hợp - nó là gì?

Năm ngoái, một cuốn sách mới của nhà khoa học và nhà phổ biến khoa học nổi tiếng N. Ya. Vilenkin đã được xuất bản - “Kết hợp phổ biến” *).

Năm 1969, cuốn sách “Tổ hợp” của ông được xuất bản tại Tòa soạn chính Văn học Vật lý và Toán học của Nhà xuất bản Nauka. Nó đã nhận được sự công nhận trên toàn thế giới và được dịch sang nhiều ngôn ngữ (tiếng Anh, tiếng Đức, tiếng Tây Ban Nha, tiếng Ba Lan, tiếng Hungary, tiếng Séc, tiếng Estonia).

Cuốn sách đang được đánh giá bổ sung rất ít cho cuốn sách trước đó. Sáu trong số các chương được cho là của Zanyuvo, và ba chương còn lại là văn bản được sửa đổi hoàn toàn từ cuốn sách “Combinatorics”.

“Tổ hợp phổ biến” bắt đầu với câu chuyện chính về tổ hợp và các ứng dụng của nó. Ở đây chúng ta nói về những ma phương đầu tiên, về những con số, về các công trình tổ hợp của chiêm tinh học liên quan đến sự kết hợp của các hành tinh, về cách học giả Raymond Lully đang cố gắng tạo ra một cỗ máy khiến cho nhiều sự kết hợp khác nhau trở nên dễ hiểu và về các vấn đề tổ hợp nảy sinh trong cờ bạc. Tác giả nói về việc tổ hợp đã trở thành một nhánh độc lập của toán học như thế nào, về các công trình của Pascal, Fermat, Leibniz và Euler. Không còn nghi ngờ gì nữa, người đọc sẽ hứng thú hơn với những câu chuyện về ứng dụng của tổ hợp vào việc làm sáng tỏ các văn bản cổ, đến việc nghiên cứu mã di truyền,

*) Vilenkin N. Ya. Tổ hợp phổ biến. M., “Khoa học”, 1975.

đến việc phát hiện ra hệ thống tuần hoàn của Mendeleev. Điều đáng tiếc duy nhất là tác giả chưa hề tập trung vào ứng dụng của tổ hợp vào công nghệ và tổ hợp của mạng tinh thể.

Chương thứ hai dành cho việc phân loại tổ hợp bài toán.

Tiếp nối cuốn sách nổi tiếng của Berge, tác giả chia các bài toán tổ hợp như sau:

1. Tìm cấu hình của các phần tử có thuộc tính.
2. Chứng minh sự tồn tại (hoặc vắng mặt) của một cấu hình với các thuộc tính đã cho.
3. Tìm tổng số cấu hình có các thuộc tính đã cho.
4. Mô tả tất cả các phương thức lời giải của một tổ hợp bài toán cho trước, đưa ra thuật toán liệt kê chúng.
5. Từ tất cả lời giải của một tổ hợp bài toán nhất định, hãy chọn tổ hợp tối ưu (theo các tham số nhất định).

Lấy bình phương ma thuật và bài toán làm ví dụ, anh ấy chỉ ra cách tìm kiếm cấu hình với các thuộc tính nhất định, sau đó nói về nguyên tắc chung lời giải của các vấn đề tối ưu hóa: nếu lời giải là tối ưu về tổng thể thì nó phải tối ưu ở bất kỳ phần nào của nó (nguyên tắc này làm cơ sở cho cái gọi là lập trình đường kính*)). Sử dụng ví dụ về “trò chơi 15”, anh ấy cho thấy cách người ta có thể chứng minh sự bất khả thi của lời giải một số một số bài toán. Đã xem xét cuộc thi Olympic nổi tiếng bài toán về thư từ khoa học:

Sáu nhà khoa học trao đổi thư từ với nhau về hai chủ đề khoa học. Những loại thư từ với mỗi người về một chủ đề. Chứng minh rằng có những nhà khoa học khác viết lại cơ học về một chủ đề,

*) «Kvant», 1972, số 3, tr. 6.

66

sau đó tác giả phân tích các khái quát hóa và điều kiện khác nhau của nó: cuộc điều tra dân số 17 nghiên cứu về các chủ đề đó, đưa ra trọng số khác nhau cho từng chủ đề riêng lẻ, v.v., dẫn đến việc hình thành định lý tổng quát của Ramsey. Điều đáng tiếc là độ dài và tính chất của cuốn sách đã không thể đưa ra một chứng minh tổng quát cho định lý đáng chú ý này.

Tiếp theo, chúng ta xem xét định lý về các đại diện khác nhau (hay còn gọi là định lý về đám cưới ở làng), được chứng minh đầy đủ. Định lý này là lý do để tác giả nói về đồ thị và các bài toán tổ hợp trong lý thuyết đồ thị. Chương này kết thúc với nội dung nổi tiếng hơn của lý thuyết đồ thị - Đường đi Euler (đường đi qua đồ thị trong đó chúng không đi qua một cạnh hai lần), đường dẫn Hamlutonian (các đường đi khép kín đi qua mỗi đỉnh của đồ thị một lần), bài toán bốn màu, v.v. Giống như tất cả các chương tiếp theo, nó chứa nhiều bài toán khác nhau (tổng cộng, cuốn sách chứa hơn 400 bài toán). Thật không may, hầu hết bài toán của chương thứ hai đều có tính chất tối ưu hóa. Họ có thể tạo ấn tượng rằng các chương tiếp theo của bài toán sẽ khó, mặc dù điều này hoàn toàn không phải vậy - phần lớn các chương thứ ba, thứ tư và thứ năm của bài toán khá đơn giản.

Chương thứ ba phác thảo “tổ hợp cổ điển” - vị trí, hoán vị và kết hợp, cả có và không có sự lặp lại. Khi trình bày những câu hỏi này, tác giả sử dụng một cách có hệ thống ngôn ngữ của lý thuyết tập hợp và khái niệm bộ dữ liệu. Điều này cho phép ông xác định các khái niệm cơ bản. Mặc dù, như trong toàn bộ cuốn sách, việc trình bày được thực hiện bằng cách phân tích ít nhiều tưởng tượng bài toán, nhưng thực chất chương này là sách giáo khoa về tổ hợp, được viết khá rõ ràng và có hệ thống. Việc chuyển đổi sang ngôn ngữ lý thuyết-lý thuyết cho phép chúng ta phân tích công thức bao gồm và loại trừ (công thức chồng lấp), cho phép chúng ta tìm số phần tử trong hợp của một số tập hợp, nếu biết số phần tử trong mỗi tập hợp, cũng như trong giao điểm của bất kỳ tập hợp nào trong số các tập hợp này.

Chương tiếp theo có tên là “Kết hợp bố cục và phân vùng”. Những vấn đề này đã được thảo luận trong cuốn sách trước của tác giả, nhưng bây giờ cách trình bày đã trở nên rõ ràng và cô đọng hơn. Tài liệu mới đã xuất hiện, chẳng hạn, người ta kể về số Bell, tức là về số cách phân tách n đồ vật khác nhau thành m hộp không phân biệt sao cho tất cả các hộp đều không trống.

Ngoài ra còn có một chương trong cuốn sách trước “Tổ hợp bài toán với những hạn chế”. Nhưng bây giờ, cùng với phần phân tích riêng lẻ, hầu như không liên quan đến nhau bài toán, phần trình bày về các khái niệm và công thức chung được đưa ra. Đặc biệt, tác giả đưa ra một công thức chung để tính cái gọi là bội số xe. Ông khôi phục lại công bằng lịch sử, lưu ý rằng các số dade (số cách đặt n quân xe lên bàn cờ theo một hình thức nhất định để không có cặp quân xe nào có thể chiếm lấy nhau) đã được nhà toán học Liên Xô S. E. Arshon giới thiệu và nghiên cứu mười năm trước khi các nhà toán học Mỹ Kaplansky và Riordan bắt đầu mượn những con số này. Chương bài toán về câu châm ngôn của Vua Arthur và việc xếp hàng ở quầy thu ngân kết thúc.

Chương cuối cùng, thứ sáu của cuốn sách nói về các bài toán tổ hợp, kết nối mục nhập với lý thuyết nhóm - về tổ hợp quỹ đạo. Một bài toán điển hình thuộc loại này là tìm số cách sơn các đỉnh của hình lập phương bằng k màu. Phương pháp chung của lời giải như vậy bài toán dựa trên một số khái niệm của lý thuyết nhóm *). Mặc dù tác giả đã tìm được cách trình bày phương pháp này đơn giản hơn so với hầu hết các cuốn sách về tổ hợp (theo như chúng tôi biết, phương pháp này chưa bao giờ được trình bày trong văn học đại chúng), phần cuối của chương không được chứng minh trong cuốn sách.

Vì vậy, nhìn chung nó hóa ra là một cuốn sách viết rất thú vị và sinh động về tổ hợp. Tuy nhiên, chúng ta phải thừa nhận rằng bài toán được đưa ra trong sách không những không có lời giải mà còn không có đáp số.

N. Vâng. Cuốn sách mới về tổ hợp của Villenkon sẽ thu hút sự quan tâm của học sinh trung học quan tâm đến toán học, giáo viên và tất cả những người giải quyết cụ thể các vấn đề tổ hợp. Năm 1976, bà được trao giải nhì tại cuộc thi All-Union cho tác phẩm văn học khoa học đại chúng hay nhất.

Hiện tại, số lượng phát hành của cuốn sách đã được bán hết. Chúng tôi hy vọng rằng nhà xuất bản Nauka sẽ phát hành ấn bản thứ hai của cuốn sách hữu ích này, mở rộng phạm vi của nó, giúp nó có thể bao gồm lời giải bài toán được đưa ra trong đó và các tài liệu khác, cũng như dựa trên Vua Arthur và dòng chữ ở máy tính tiền.

*) Bạn có thể đọc về các nhóm trong «Kvant», 1976, số 10.