Bài toán 36 sĩ quan là gì?

Bài toán 36 sĩ quan bắt nguồn từ một truyền thuyết. Truyện kể rằng có lần một quốc vương nước Phổ tiến hành một cuộc duyệt binh lớn, truyền lệnh cho sáu chi đội lính tham gia để duyệt binh. Quốc vương quy định mỗi chi đội phải chọn sáu sĩ quan có quân hàm khác nhau (ví dụ có thể chọn sĩ quan thượng tá, trung tá, thiếu tá, và thượng uý, trung uý, thiếu uý). Vậy mỗi chi đội chọn sáu sĩ quan thì sáu chi đội sẽ có 36 sĩ quan. Quốc vương yêu cầu sĩ quan xếp thành đội hình sáu hàng ngang và sáu hàng dọc, ở mỗi hàng ngang và hàng dọc, các sĩ quan phải không cùng hàm và không cùng đơn vị. Viên sĩ quan điều hành bày đi, xếp lại vẫn không đạt được đội hình theo đúng yêu cầu của Quốc vương. Về sau, câu chuyện lan truyền ra ngoài, mọi người ai nấy cũng đều tìm các phương án sắp xếp đội hình nhưng rốt cuộc không ai thu được kết quả. Vấn đề này được gọi là “vấn đề 36 sĩ quan” và lưu truyền rộng rãi. Vấn đề khó này đã thu hút nhiều tâm lực của nhiều nhà toán học nổi tiếng.

Người ta tìm thấy rằng, nếu Quốc vương đề ra yêu cầu ít hơn hoặc nhiều hơn một chút, ví dụ yêu cầu bày thành năm hàng ngang, năm hàng dọc hoặc bảy hàng ngang bảy hàng dọc thì có thể được, nhưng với sáu hàng ngang sáu hàng dọc thì không thể được. Ta thử xét trường hợp xếp thành bảy hàng ngang bảy hàng dọc.

A, B, C, D, E, F, G, biểu diễn các đơn vị bộ đội, các chỉ số 1, 2, 3, 4, 5, 6, 7 chỉ các cấp quân hàm của các sĩ quan. Ở mỗi hàng ngang, hàng dọc đều có chữ cái A, B, C, D, E, F, G biểu diễn đó là các sĩ quan từ 7 đơn vị, các chỉ số 1, 2, 3, 4, 5, 6, 7 chỉ các cấp quân hàm của các cấp sĩ quan khác nhau.

Ngày nay bài toán 36 sĩ quan thuộc một bài toán của phép toán tổ hợp. Các đội hình sắp xếp được gọi là ma trận hoặc ma trận chữ nhật, ví dụ cách xếp sáu hàng ngang sáu hàng dọc gọi là ma trận vuông cấp sáu. Do từ ban đầu các yếu tố của ma trận đều biểu diễn nhờ các chữ cái Latinh A, B, C, D... nên các ma trận này thường được gọi là các ô vuông Latinh. Bảng vuông Latinh phù hợp với điều kiện trực giao gọi là “bảng vuông trực giao”. Bài toán 36 sĩ quan thuộc loại bài toán của phép toán tổ hợp của bảng vuông Latinh trực giao. Nhà toán học kiệt xuất ơle (L. Euler) đã chứng minh là ma trận vuông cấp sáu theo yêu cầu của Quốc vương Phổ là không thể được, kết luận này đã được nhà toán học Pháp Thali chứng minh vào năm 1901. Thế là bài toán 36 sĩ quan đã được giải quyết. Đó chính là các ma trận vuông Latinh trực giao. Các ma trận này được ứng dụng rộng rãi trong công tác thiết kế, thí nghiệm. Trong công nghiệp, nông nghiệp, trong khoa học kĩ thuật luôn cần phải tiến hành một số lớn việc sắp xếp tổ chức các tổ thực nghiệm. Việc sử dụng các bảng vuông Latinh trong công tác thiết kế, thực nghiệm có thể giảm đi nhiều công sức trong việc sắp xếp, tiết kiệm được nhiều sức người, sức của, tăng được hiệu quả công việc.