🔙 Quay lại trang tải sách pdf ebook Tạp chí Epsilon số 2 Ebooks Nhóm Zalo Toán yêu người những đồng cộng của online chí Tạp Người viết cho rằng hầu hết khái niệm tưởng như trừu tượng đều có cội nguồn ở những thao tác toán học cụ thể và thông dụng. Người viết cũng cho rằng chỉ khi được nâng lên tầm khái niệm, các thao tác toán học mới trở thành những công cụ tư duy thật sự mạnh mẽ Phương trình đại số một ẩn số Ngô Bảo Châu Phương trình đại số 1 ẩn số Ngô Bảo Châu Bài toán Frobenius về những đồng xu Trần Nam Dũng Bài toán đội nón Đặng Nguyễn Đức Tiến Khám phá toán học thông qua các định lý hình học. Đào Thanh Oai 13 apr 2015 Tạp chí online của cộng đồng những người yêu Toán Đại số tuyến tính VẠN TUẾ Nghịch đảo Möbius Ngô Quang Hưng Laurent Schwartz Hà Huy Khoái Giới thiệu đề Vietnam TST 2015, bình luận sơ bộ và tóm tắt cách giải. Trần Nam Dũng VÀ CÁC CHUYÊN MỤC KHÁC d Toán yêu người những đồng cộng của online chí Tạp Toán yêu người những đồng cộng của online chí Tạp Tạp chí online của cộng đồng những người yêu Toán EPSILON Chủ biên: abc TRẦN NAM DŨNG Biên tập viên: ĐẶNG NGUYỄN ĐỨC TIẾN Biên tập viên: VÕ QUỐC BÁ CẨN Biên tập viên: TRẦN QUANG HÙNG Biên tập viên: LÊ PHÚC LỮ Số 2, ngày 13 tháng 04 năm 2015 Toán yêu người những đồng cộng của online chí Tạp d 4 Tạp chí online của những người yêu Toán cộng đồng ToánLỜI NGỎ CHO EPSILON SỐ 2 yêu người những đồng cộng của online chí Tạp Ban biên tập Epsilon Epsilon số 1 ra mắt đã được đón nhận một cách nồng nhiệt của bạn đọc. Đó là một niềm động viên lớn lao dành cho Ban biên tập, giúp chúng tôi có thêm năng lượng, nhiệt huyết để bước tiếp trên con đường mà không hẳn chỉ có hoa hồng. Epsilon đã nhận được một vận tốc ban đầu và một gia tốc. Bé nhưng dương. Với sự đóng góp của cộng đồng, hy vọng Epsilon sẽ giữ được nhịp và đều đặt ra mắt vào ngày 13 các tháng chẵn để phục vụ cộng đồng, đem đến một món ăn tinh thần ý vị trong một cuộc sống đang vẫn rất nhiều những món ăn. Epsilon mong muốn sẽ là một nhịp cầu để kết nối những đối tượng vốn còn xa cách nhau: lý thuyết và thực tiễn, toán học và các môn khoa học khác, giáo viên và học sinh, các nhà toán học chuyên nghiệp và những người làm toán nghiệp dư, toán hàn lâm và toán giải trí, toán cao cấp và toán sơ cấp. Vì thế, Epsilon sẽ có sự hòa quyện của những bài viết với nội dung và phong cách rất khác nhau. Ban biên tập sẽ tôn trọng cách hành văn của các tác giả mà không áp đặt ý kiến của mình, chỉ chỉnh sửa để cho bài tốt hơn, chính xác hơn. Epsilon số 2 mà các bạn cầm trên tay sẽ có 12 bài viết của các tác giả đến từ nhiều quốc gia, nhiều thành phần và cấp độ chuyên nghiệp. Kể từ số này, Epsilon sẽ dành những trang viết của mình để giới thiệu về tiểu sử các nhà toán học nổi tiếng thế giới, lần này sẽ là bài viết của GS Hà Huy Khoái về Loran Schwarz, nhân kỷ niệm 100 năm ngày sinh của ông và bài viết về thiên tài đoản mệnh Evariste Galois song hành với bài viết về Phương trình đại số của GS Ngô Bảo Châu. Cầu nối giữa toán học và khoa học máy tính trong số này sẽ được thể hiện bằng bài viết của GS Ngô Quang Hưng, ĐH Buffalo, Mỹ về nghịch đảo Mobius. Hình học sơ cấp, môn học vốn được coi là cổ xưa và già cỗi nhất sẽ như lại tươi mới dưới góc nhìn của một người yêu 5 Toán yêu người những đồng cộng của online chí Tạp toán nghiệp dư, kỹ sư Đào Thanh Oai trong bài Phương pháp mở rộng và sáng tạo các định lý hình học cổ điển. Các bạn học sinh yêu toán chắc chắn sẽ tìm được nhiều điều bổ ích qua các bài viết về các bài toán thi chọn HSG quốc gia (VMO 2015) và chọn đội tuyển dự IMO 2015 (Vietnam TST 2015) của các tác giả Trần Nam Dũng, Nguyễn Tất Thu, Trần Quang Hùng. Bài bình luận của Nguyễn Văn Lợi (Budapest) và Nguyễn Hùng Sơn (Warsaw) về đề TST cũng sẽ giúp các bạn hiểu rõ hơn về các bài toán trong đề thi. Đặc biệt trong số này sẽ có bài viết Inequalities, A Journey into Fibonacci and Lucas numbers của hai tác giả nước ngoài là Vandanjav Adiyasuren và Bold Sanchir đến từ ĐH QG Mông Cổ. Những ai yêu toán học giải trí sẽ được tiếp tục cuộc phiêu lưu kỳ thú vào vương quốc của những chiếc nón đủ màu sắc với người hướng dẫn viên Đặng Nguyễn Đức Tiến (Trento, Italy). Một nhà ảo thuật độc đáo khác là Nguyễn Quốc Khánh sẽ ra mắt bạn đọc một chuyên mục lý thú và bổ ích: Giới thiệu sách. Hy vọng với những bài viết như thế, mỗi độc giả đều có thể tìm được ít nhất là 10% điều mình yêu thích ở trong số này. Như thế, Ban biên tập đã cảm thấy thật mãn nguyện và cho rằng nhiệm vụ đã hoàn thành. Và lại đủ năng lượng, nhiệt huyết để tiếp tục bước đi. Đi nhiều người, bạn sẽ đi rất xa ... 6 Tạp chí online của những người yêu Toán cộng đồng ToánMỤC LỤC yêu người những đồng cộng của online chí Tạp 1 Lời ngỏ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 2 Nhân 100 năm ngày sinh Laurent Schwartz Hà Huy Khoái . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9 3 Phương trình đại số một ẩn số Ngô Bảo Châu . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15 4 Évariste Galois Lưu Trọng Luân . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35 5 Nghịch đảo Mobius ¨ Ngô Quang Hưng . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41 6 Các bài toán đội nón Đặng Nguyễn Đức Tiến . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53 7 Bài toán Frobenius về những đồng xu Trần Nam Dũng - Nguyễn Tất Thu . . . . . . . . . . . . . . . . . . . . . 73 8 Việt Nam TST 2015 Trần Nam Dũng . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 89 9 Lời giải và bình luận hai bài hình thi chọn đội tuyển Việt Nam năm 2015 Trần Quang Hùng . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 97 10 Các vấn đề cổ điển và hiện đại 7 Toán yêu người những đồng cộng của online chí Tạp Trần Nam Dũng . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 115 11 Bất đẳng thức Shapiro . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 121 12 Phương pháp mở rộng và sáng tạo các định lý hình học cổ điển Đào Thanh Oai . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 125 13 A journey into Fibonacci and Lucas numbers V. Adiyasuren - B. Sanchir . . . . . . . . . . . . . . . . . . . . . . . . . . . 153 14 Toán học trong mắt ai Nguyễn Quốc Khánh . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 183 8 Tạp chí online của những người yêu Toán cộng đồng ToánNHÂN 100 NĂM NGÀY SINH yêu người những đồng cộng của online chí Tạp LAURENT SCHWARTZ Hà Huy Khoái Hà Nội “Tôi là nhà toán học. Toán học đầy ắp cuộc đời tôi“. Laurent Schwartz 1 viết như vậy trong lời mở đầu cuốn hồi ký của ông. Ông cũng nói rằng, ngoài toán học, ông giành rất nhiều thời gian của đời mình cho cuộc đấu tranh vì quyền con người, vì quyền của các dân tộc, ban đầu thì như một người Troskit, sau đó thì đứng ngoài tất cả các đảng phái! Việt Nam chiếm một vị trí quan trọng trong các hoạt động đó của ông. Trong nhiều năm, ông luôn đứng hàng đầu trong đội ngũ những trí thức lớn của Phương Tây đấu tranh ủng hộ cuộc kháng chiến của nhân dân Việt Nam. Trong cuốn hồi ký dày 500 trang của ông, có thể tìm thấy khoảng 100 trang có nhắc đến Việt Nam. Laurent Schwartz sinh ngày 5 tháng 3 năm 1915 tại Paris. Cha ông là một bác sĩ phẫu thuật, mẹ ông là người yêu thiên nhiên, như ông nói, suốt ngày chỉ quanh quẩn với mảnh vườn và ba đứa con. Tuổi thơ của ông đã trôi qua êm đềm ở làng quê Autouillet, mà ông gọi một cách trìu mến trong hồi ký của mình là “Khu vườn Eden”. Mãi sau này, ông vẫn thường xuyên trở về khu vườn đó, và như ông kể lại, những định lý hay nhất của ông được tìm thấy tại khu vườn Eden. Ngay từ khi còn nhỏ, Laurent Schwartz đã bộc lộ thiên hướng nghiên cứu. Nếu như hầu hết trẻ em hài lòng với những lời giải thích sơ lược của bố mẹ khi chúng hỏi “tại sao?”, thì cậu bé Laurent không như vậy. Cậu luôn đòi hỏi những lời giải thích cặn kẽ, mà ít khi được thoả mãn. Mẹ cậu rất lúng túng trước những câu hỏi: Tại sao khi cắm cái gậy vào nước thì thấy nó cong, tại sao trong cùng một nhiệt độ mà không khí lúc thì 1Nhà toán học người Pháp (05/03/1915 - 04/07/2002) 9 Toán yêu người những đồng cộng của online chí Tạp lạnh hơn, lúc thì nóng hơn nước, tại sao khi lật úp cái thìa cà phê thì không bao giờ hết cà phê, mà còn một ít dính lại ở thìa, và còn rất nhiều những câu hỏi khác. Ở các lớp tiểu học, Laurent Schwartz không phải là học sinh giỏi môn toán. Ông rất nhớ lời thầy Thoridenet, người dạy ông môn văn năm lớp 5 từng nói với mẹ ông: “Tôi chưa có học sinh nào giỏi như vậy về môn tiếng Latinh, nhưng về tiếng Pháp, ngôn ngữ và toán thì cậu ta kém hơn một chút. Tuy vậy, cho dù người ta nói với bà thế nào đi nữa, cậu ta sẽ trở thành nhà toán học!”. Laurent Schwartz nói rằng, nếu không có lời khuyên của ông thầy dạy văn đó thì có lẽ ông đã trở thành nhà ngôn ngữ học, chứ không phải nhà toán học! May mắn nữa cho Laurent là cậu gặp một thầy giáo dạy toán đầy nhiệt tâm, thầy Julien. Ông đã giải thích cho học sinh một cách rất vui vẻ và đơn giản những điều kì diệu của môn hình học, mở ra cho họ một thế giới toán học mà trước đó họ chưa được biết đến. Laurent Schwartz kể, sau khi suy nghĩ vài ba tuần, ông quyết định trở thành nhà toán học. Theo ông, thiên hướng đó có sẵn trong con người ông, nhưng đã trở thành hiện thực nhờ thầy giáo. Vì thế ông cho rằng, vai trò của người thầy đối với tương lai học sinh là có ý nghĩa quyết định. Laurent Schwartz thi đỗ vào trường Ecole Normale Supérieure (Paris) năm 1934. Ở Ecole Normale, ông được học với những giáo sư nổi tiếng nhất thời bấy giờ: Fréchet, Montel, Borel, Denjoy, Julia, Elie Cartan, Lebesgue và Hadamard. Trong khoá đó, ông cùng với Choquet, Marot là ba người xuất sắc nhất. Năm 1937, ông tốt nghiệp đại học Ecole Normale, làm nghiên cứu sinh tại trường đại học Strasbourg và bảo vệ luận án Tiến sĩ năm 1943. Giáo sư hướng dẫn luận án của ông là Valiron, một trong những nhà toán học nổi tiếng nhất thời đó về lý thuyết hàm. Vài năm sau, Valiron cũng là người hướng dẫn của giáo sư Lê Văn Thiêm. Trong các năm 1944 ´ 1945 ông giảng dạy tại khoa Khoa học ở Grenoble, sau đó chuyển về Nancy, nhận một chức giáo sư ở khoa Khoa học. Chính trong thời gian này, ông sáng tạo ra công trình nổi tiếng về lý thuyết các hàm suy rộng. Năm 1953 Laurent Schwartz trở về Paris, làm giáo sư cho đến 1959. Ông giảng dạy tại trường Ecole Polytechnique từ 1959 đến 10 Toán yêu người những đồng cộng của online chí Tạp 1980, rồi làm việc ở trường Đại học Paris 7 ba năm, cho đến ngày nghỉ hưu năm 1983. Cống hiến lớn nhất cho toán học của Laurent Schwartz là các công trình của ông về lý thuyết phân bố, được viết vào những năm 40. Những tư tưởng của ông theo hướng này được trình bày lần đầu tiên năm 1948 trong bài “Mở rộng khái niệm hàm, đạo hàm, biến đổi Fourier và các ứng dụng toán học, vật lý”. Lý thuyết phân bố là sự mở rộng đáng kể phép tính tích phân và vi phân. Do nhu cầu của Vật lý học, Heaviside và Dirac đã mở rộng phép tính với các ứng dụng đặc biệt. Tuy nhiên, phương pháp của họ, cũng như những phương pháp tương tự về các phép tính hình thức không được xây dựng trên một nền tảng toán học chặt chẽ. Để những nghiên cứu của họ có thể trở thành một lý thuyết mới thực sự của vật lý học, cần trang bị cho nó một cơ sở toán học vững chắc. Chính Dirac đã có lần nói: Khi bạn định xây dựng một lý thuyết mới nào trong vật lý, cái duy nhất mà bạn có thể tin tưởng là toán học. Laurent Schwartz đã phát triển một lý thuyết làm cơ sở cho các phương pháp tính toán nêu trên trong vật lý, làm cho những phương pháp đó tìm được ứng dụng hết sức rộng rãi trong những lĩnh vực khác nhau. Francois Treves đã nói về công trình của Laurent Schwartz như sau: “Tư tưởng của Laurent Schwartz đã cho một cách lý giải thống nhất tất cả các hàm suy rộng thâm nhập trong giải tích như là những phiếm hàm tuyến tính liên tục trên không gian các hàm khả vi vô hạn triệt tiêu ngoài một tập compắc. Ông đã cho một cách mô tả có hệ thống và chặt chẽ, hoàn toàn dựa trên giải tích hàm trừu tượng và lý thuyết đối ngẫu. Cũng cần nhắc lại rằng, một cách lý giải như vậy đã có trước đây trong công trình của André Weil về tích phân các nhóm compắc địa phương ... Do sự đòi hỏi của tính khả vi trong lý thuyết phân bố, không gian các hàm thử và đối ngẫu của chúng đôi khi rất phức tạp. Điều này dẫn đến những nghiên cứu sôi nổi về các không gian vector topo không thuộc các phạm trù quen thuộc như không gian Hilbert và không gian Banach. Những nghiên cứu này, đến lượt mình, chiếu rọi những ánh sáng mới lên nhiều lĩnh vực của Giải tích thuần tuý, như Phương trình đạo hàm riêng, hoặc Hàm số biến số phức.” Những tư tưởng của Laurent Schwartz có thể áp dụng cho nhiều không gian hàm thử khác nhau, như chính ông và nhiều người khác đã chỉ rõ ... Herald Bohr, người giới thiệu công trình 11 Toán yêu người những đồng cộng của online chí Tạp của Laurent Schwartz trong buổi trao Giải thưởng Fields ngày 30 tháng 8 năm 1950 tại Harvard đã mô tả các công trình của Laurent Schwartz viết năm 1948 như sau: “Chúng chắc chắn sẽ trở thành những công trình kinh điển của toán học thời đại chúng ta ... Tôi nghĩ rằng, những người trích dẫn công trình của ông, cũng giống như tôi, sẽ phải kìm nén một niềm phấn khích dễ chịu, để nhìn thấy sự hài hoà tuyệt vời của một cấu trúc tính toán mà lý thuyết này dẫn chúng ta đến, và để hiểu tầm quan trọng và ưu việt của chúng đối với nhiều phần của giải tích cao cấp, như Lý thuyết phổ, Lý thuyết thế vị, và toàn bộ lý thuyết phương trình đạo hàm riêng.” Ngoài giải thưởng Fields, Laurent Schwartz còn nhận được giải thưởng của Viện hàn lâm khoa học Paris các năm 1955, 1964, 1972. Năm 1972 ông được bầu làm Viện sĩ Viện hàn lâm Pháp. Ông được phong tiến sĩ danh dự của nhiều trường đại học, trong đó có Humboldt (1960), Brussels (1962), Lund (1981), Tel-Aviv (1981), Montreal (1985) và Athens (1993). Không chỉ là nhà toán học nổi tiếng, Laurent Schwartz còn được biết đến như là một trong những trí thức lớn suốt đời đấu tranh vì tự do của các dân tộc. Laurent Schwartz nói rằng, những năm ở Ecole Normale đã xác định hoàn toàn khuynh hướng chính trị của ông: Chống chiến tranh và bảo vệ những giá trị của con người. Cuốn sách “Đông Dương cấp cứu” (Indochine SOS) của Andrée Viollis đã cho ông thấy rõ tội ác của chủ nghĩa thực dân Pháp ở Đông Dương. Quan điểm chính trị của ông thể hiện rõ nhất trong phong trào chống chiến tranh xâm lược của đế quốc Mỹ ở Việt Nam. Ông đề xướng khẩu hiệu “Mặt trận dân tộc giải phóng sẽ chiến thắng” thay cho khẩu hiệu mà ông cho là mơ hồ của phong trào chống chiến tranh Việt Nam ở Pháp thời đó “Hoà bình ở Việt Nam“. Hoạt động của Uỷ ban quốc gia Việt Nam do ông sáng lập đã gây được tiếng vang lớn. Ông hết sức tự hào khi vào khoảng lễ Noel năm 1966, nhận được bức điện cám ơn và chúc mừng của Chủ tịch Hồ Chí Minh. Ông đến Việt Nam nhiều lần trong thời kì còn chiến tranh, với tư cách là thành viên trong Toà án quốc tế xét xử tội ác chiến tranh của Mỹ ở Việt Nam (một tổ chức quốc tế do nhà toán học, nhà triết học nổi tiếng người Anh, giải thưởng Nobel về văn học năm 1950, huân tước Bertrand Russell sáng lập). Những chuyến đi về các làng quê Việt Nam đã làm cho ông thấy yêu mến đặc biệt đất nước và con người Việt Nam. Không gì có thể nói đầy đủ hơn 12 Toán yêu người những đồng cộng của online chí Tạp tình cảm của ông với Việt Nam bằng chính những lời ông viết trong hồi ký của mình: “Việt Nam đã ghi dấu ấn trong cuộc đời tôi. Tôi từng biết đến Đông Dương thuộc địa, qua cuốn sách của André Viollis viết năm 1931, mà tôi đọc năm 1935. Lúc đó tôi vừa tròn 20 tuổi. Cuộc đấu tranh của tôi cho tự do của đất nước này là cuộc đấu tranh dài nhất của cuộc đời tôi. Tôi đã yêu, và mãi mãi yêu Việt Nam, những phong cảnh, những con người tuyệt vời, những chiếc xe đạp. Trong tôi, có một chút nào đó là người Việt Nam. Gặp người Việt Nam, nghe tiếng họ nói chuyện với nhau trong xe buýt (mà tất nhiên là tôi không hiểu), tôi cảm thấy một niềm hạnh phúc không cắt nghĩa được. Sợi giây tình cảm đã nối liền tôi với đất nước này.” Năm 1998, khi Viện Toán học tổ chức Hội nghị quốc tế nhân 80 năm ngày sinh của Giáo sư Lê Văn Thiêm, Laurent Schwartz đã rất xúc động thông báo cho Ban tổ chức rằng ông rất muốn sang Việt Nam thêm một lần nữa, nhưng tiếc là sức khoẻ không cho phép. Khi ông qua đời năm 2002, tờ Thông tin toán học của Hội toán học Việt Nam có đăng một bài viết để tưởng nhớ ông. Dường như ông biết trước điều đó, nên đã viết trong hồi kí của mình: “Les Vietnamiens ne m’oublient pas” (Người Việt Nam không quên tôi). 13 Toán yêu người những đồng cộng của online chí Tạp 14 Tạp chí online của những người yêu Toán cộng đồng ToánPHƯƠNG TRÌNH ĐẠI SỐ yêu người những đồng cộng của online chí Tạp MỘT ẨN SỐ Ngô Bảo Châu Đại học Chicago, Mỹ Tóm tắt Từ thế kỷ 20 trước Công nguyên, người dân thành Babylon đã biết giải phương trình bậc hai. Nhưng phải đến thế kỷ 16 sau Công nguyên, các nhà toán học của thời Phục hưng: Tartaglia, Cardano, Ferrari, mới tìm ra lời giải cho phương trình bậc ba và bậc bốn. Đầu thế kỷ 19, Abel và Galois, hai thiên tài toán học bạc mệnh, chứng minh nghiệm của phương trình đại số tổng quát bậc từ năm trở đi, không thể biểu diễn được như một biểu thức đại số với căn thức như trong trường hợp đa thức bậc không quá bốn. Công trình của Galois, viết ra như lời trăng trối trước giờ đấu súng, sau đó được xem như mốc khai sinh của Đại số hiện đại. Lý thuyết Galois hiện đại được phát biểu trên cơ sở các khái niệm mở rộng trường và nhóm Galois. Những khái niệm này không dễ nắm bắt. Mục đích của bài viết này là giúp những người mới học nắm bắt những khái niệm đó, thông qua việc tìm hiểu mô thức mà chúng xuất hiện trong quá trình tìm nghiệm của những phương trình đại số cụ thể. Người viết cho rằng hầu hết khái niệm tưởng như trừu tượng đều có cội nguồn ở những thao tác toán học cụ thể và thông dụng. Người viết cũng cho rằng chỉ khi được nâng lên tầm khái niệm, các thao tác toán học mới trở thành những công cụ tư duy thật sự mạnh mẽ. Câu chuyện sắp kể về ý thuyết Galois có thể xem như một minh chứng. Để hiểu bài viết này, người đọc cần một số kiến thức cơ bản về đại số tuyến tính, trong đó đặc biệt quan trọng là khái niệm chiều của không gian vector. 15 Toán yêu người những đồng cộng của online chí Tạp 1. Lịch sử của bài toán Vào thế kỷ thứ bảy trước công nguyên, lời giải cho phương trình bậc hai tổng quát x2 + ax + b = 0, (3.1) đã được nhà toán học Brahmagupta, người Ấn độ, trình bày một cách tường minh ở dạng x =´a ˘?d 2, (3.2) với d = a2 ´ 4b là biệt thức của phương trình bậc hai. Trước đó, từ khoảng thế kỷ 20 trước công nguyên, người Babylon đã tìm lời giải hình học cho bài toán tương đương tìm hai cạnh của hình chữ nhật biết trước chu vi và diện tích của nó. Dấu vết của những phương pháp hình học khác nhau để giải phương trình bậc hai đã được phát hiện trong hầu hết các nền văn minh cổ đại từ Babylon, Ai cập, Hy lạp, Ấn độ, Trung Hoa ... Phương trình bậc ba tổng quát cũng được người Babylon nghiên cứu. Người Hy lạp cổ đại đã thử xây dựng nghiệm phương trình bậc ba bằng thước kẻ và compa nhưng không thành công. Nhà toán học Trung Hoa Wang Xiaotong đưa ra lời giải cho 27 phương trình bậc ba khác nhau, nhưng không đưa ra phương pháp để giải phương trình bậc ba tổng quát. Đáng kể nhất là phát hiện của nhà thơ người Ba tư Omar Khayyam sống vào thế mười một. Ông chứng minh rằng nghiệm có thể xây dựng nghiệm phương trình bậc ba bằng cách lấy giao hai đường conic. Ngoài ra, ông phát biểu rằng không thể xây dựng nghiệm phương trình bậc ba chỉ bằng thước kẻ và compa. Omar Khayyam không đưa ra một công thức cho nghiệm của phương trình bậc ba giống như công thức (3.2) cho phương trình bậc hai. Phải chờ đến thời kỳ phục hưng, nhà toán học Tartaglia, sống ở Ý vào thế kỷ thứ mười sáu, mới đưa ra công thức tổng quát đầu tiên cho nghiệm của phương tình bậc ba ax3 + bx2 + cx + d = 0, (3.3) ở dạng x = ´13a b + C +∆0 C 16 , (3.4) trong đó Toán d C =3 ∆1 +a∆21 ´ 4∆30 2, (3.5) yêu người những đồng cộng của online chí Tạp với ∆0, ∆1 là các đa thức tường minh với biến số a, b, c, d. Lời giải cho phương trình bậc ba quả là rắc rối, nhưng lời giải cho phương trình bậc bốn của Ferrari còn rắc rối hơn nhiều. Nhà toán học Joseph Lagrange, người Ý, là người đưa ra một phương pháp chung để giải cả phương trình bậc ba và bậc bốn. Phương pháp của Lagrange dưạ trên khái niệm giải thức mà chúng ta sẽ xem xét kỹ lưỡng. Ruffini đã nghiên cứu phương pháp của Lagrange và nhận thấy rằng nó không thể mở rộng ra cho phương trình có bậc năm và bậc cao hơn nữa. Abel là người đầu tiên đưa ra chứng minh chặt chẽ và khẳng định phương trình bậc năm tổng quát không thể giải được bằng căn thức. Định lý Abel-Ruffini cũng được Galois, một nhà toán học người Pháp, chứng minh một cách độc lập. Nhưng ông đi xa hơn Abel và đưa ra một khái niệm có tính chất cách mạng, đó là nhóm Galois. 2. Về phát biểu của bài toán Bài toán ta quan tâm chính là việc biểu diễn nghiệm của phương trình đa thức a0xn + a1xn´1 + ¨ ¨ ¨ = 0, (3.6) dưới dạng một biểu thức với biến số a0, a1, . . . , mà trong đó ta được quyền dùng bốn phép toán thông thường và căn thức. Để hiểu rõ thế nào là biểu diễn được dưới dạng một biểu thức như thế, ta sẽ cần khái niệm trường và mở rộng trường. Ví dụ như các biểu thức với biến số a0, a1, . . . , an mà chỉ dùng bốn phép toán thông thường và với hệ số hữu tỉ, là trường sinh ra bởi a0, a1, . . . , an. Câu hỏi biểu diễn nghiệm bằng căn thức thực ra vẫn không chuẩn. Thật vậy phương trình bậc n có thể có tới n nghiệm cho nên để hết mập mờ cần làm rõ ta muốn biểu diễn nghiệm nào trong số n nghiệm đó. Dĩ nhiên trong công thức (3.2), dấu ˘ cho 17 Toán yêu người những đồng cộng của online chí Tạp phép ta biểu diễn cả nghiệm của (3.1). Trong khi đó, công thức của Tartaglia (3.5) dường như cho ta sáu nghiệm khác nhau của phương trình bậc ba, cái rõ ràng là không thể. Thực ra ta không có cách nào để chọn một trong n nghiệm của phương trình (3.6). Khái niệm nhóm Galois sinh ta chính là để lượng hoá sự mập mờ này. Ngược lại, như ta sẽ phân tích, cấu trúc của nhóm Galois sẽ quyết định việc phương trình (3.6) có thể giải được bằng căn thức hay không. 3. Mở rộng bậc hai Để giải phương trình bậc hai (3.1), ta thực hiện phép đổi biến y = x +a2. Sau khi đổi biến, phương trình (3.1) để quy về dạng đơn giản hơn y2 ´ d = 0. (3.7) Ta có thể coi đây là một cái mẹo để quy phương trình bậc hai tổng quát (3.1) về phương trình bậc hai rút gọn (3.7). Ta cũng có thể thay đổi quan điểm: Không quan tâm đến việc tìm ra dạng chính xác (3.2) của nghiệm nữa, mà chỉ quan tâm đến việc nghiệm có thể biểu diễn dưới dạng biểu thức đại số của ?d. Lập luận có thể sẽ phức tạp hơn, nhưng sẽ mở ra cho ta một tầm nhìn mới. Để làm đơn giản vấn đề, giả sử các hệ số a, b là số hữu tỉ. Ta biết rằng trong C, phương trình (3.1) có hai nghiệm. Ta sẽ ký hiệu α1 P C là một trong hai nghiệm của nó. Giả sử α1 R Q, khi đó tập các số phức có dạng L = tm + nα1 | m, n P Qu, là một không gian vector hai chiều trên Q. Từ đẳng thức α21 = ´(aα1 + b), ta suy ra rằng nếu u, v P L thì uv P L. Ta cũng có thể chứng minh rằng nếu u P L ´ t0u, thì u´1 P L. Như vậy L là một trường con của C. Nếu xem như không gian vector trên Q, nó có chiều bằng 2. Vì thế ta nói rằng L là một mở rộng bậc hai của Q. Ta để ý thấy nghiệm còn lại, ký hiệu là α2, của đa thức P = x2 + ax + b, 18 Toán yêu người những đồng cộng của online chí Tạp cũng nằm trong L. Thật vậy, đa thức bậc hai P đã có một nghiệm α1 P L, nghiệm còn lại α2 cũng phải nằm trong L và cũng không là số hữu tỉ. Nói cách khác, mở rộng bậc hai sinh bởi α1, trùng với mở rộng bậc hai sinh bởi α2 tm + nα2 | m, n P Qu. Suy từ (3.2) ra thì cả mở rộng bậc hai sinh bởi α1 hay α2 đều trùng với mở rộng bậc hai sinh bởi căn bậc hai của biệt thức Q[?d] = tm + n?d | m, n P Qu. (3.8) Đây cũng là một cách để diễn đạt việc cả α1 và α2 đều có thể viết được dưới dạng có dạng m +?d với m, n P Q. Định lý 3.1. Cho P P Q[x] là một đa thức bậc hai bất khả quy, L là mở rộng bậc hai của Q sinh bởi một trong các nghiệm của P. Khi đó L = Q[?d] với d = a2 ´ 4b. Dễ thấy rằng, nếu L là mở rộng bậc hai của Q, khi đó mỗi phần tử α P L ´ Q là nghiệm của một phương trình bất khả quy bậc hai nào đó. Vì thế ta có thể phát biểu lại định lý trên ở dạng cô đọng hơn: Định lý 3.2. Mọi mở rộng bậc hai của Q đều có dạng L = Q[?d] với d là một số hữu tỉ nào đó. Mở rộng ra phương trình bậc cao hơn, ta có thể định nghĩa rành rọt khái niệm phương trình giải được bằng căn thức. 4. Phương trình giải được bằng căn thức Từ nay trở đi, ta sẽ thay trường các số hữu tỉ bởi một trường K bất kỳ. Thay cho trường các số phức, ta cho trước một trường đóng đại số chứa K. Xin nhắc lại rằng trường K được gọi là đóng đại số nếu mọi đa thức P P K[x] bậc n đều có đúng n nghiệm trong K, nếu ta đếm cả bội. Ta sẽ chỉ xét tới các mở rộng của K chứa trong K. Đa thức bậc n P = xn + a1xn´1 + ¨ ¨ ¨ + an P K[x], 19 Toán yêu người những đồng cộng của online chí Tạp được gọi là bất khả quy nếu nó không thể phân tích được thành tích của hai đa thức có bậc nhỏ hơn. Giả sử P là một đa thức bậc n bất khả quy. Với mỗi nghiệm α P K của P, ta đặt K[α] = tm0 + m1α + ¨ ¨ ¨ + mn´1αn´1| m0, . . . , mn´1 P Ku. (3.9) Sử dụng đẳng thức αn = ´(a1αn´1+¨ ¨ ¨+an), ta chứng minh được rằng nếu u, v P K[α] thì uv P K[α]. Ngoài ra, nếu u P K[α] ´ t0u thì u´1 P K[α]. Nói cách khác, K[α] là một trường con của K. Sử dụng giả thiết P là đa thức bất khả quy, ta chứng minh được rằng K[α], xem như không gian vector trên trường K, có chiều bằng n. Nói cách khác, K[α] là một mở rộng bậc n của K. Ta nói nghiệm α có thể biểu diễn được bằng biểu thức đại số với căn thức nếu tồn tại một chuỗi mở rộng trường liên tiếp K = K0 Ă K1 Ă K2 Ă ¨ ¨ ¨ Ă Kr, (3.10) sao cho với mọi i P t1, 2, . . . , ru, Ki là một mở rộng bậc ni của Ki´1 có dạng Ki » Ki´1[x]/(xni ´ βi), và sao cho K[α] Ă Kr. Khái niệm mở rộng trường đã cho phép ta phát biểu rành rọt câu hỏi liệu nghiệm α của P có thể biểu diễn dưới dạng tổ hợp đại số và căn thức hay không. Nó còn cho phép ta đặt ra những câu hỏi khác, sâu sắc hơn, về nghiệm của đa thức. 5. Phụ thuộc đại số giữa các nghiệm Như ở trên, ta vẫn ký hiệu P P K[x] là một đa thức bất khả quy bậc n, và α là một nghiệm của P trong K, K[α] là mở rộng bậc n của K bao gồm các tổ hợp đại số của α như (3.9). Khác với trường hợp bậc 2, khi n ě 3, nếu α1 và α2 là hai nghiệm khác nhau của P, các trường con K[α1] và K[α2] của K, có thể là khác nhau, như ta thấy trong ví dụ sau đây. Xét trường hợp K = Q và đa thức P = x3 ´ 2. Nếu α P K là một nghiệm của P thì hai nghiệm còn lại sẽ là jα và j2α. Ở đây ta sử dụng ký hiệu j = cos2π3+ isin2π3, (3.11) 20 Toán yêu người những đồng cộng của online chí Tạp là căn bậc ba nguyên sơ của đơn vị. Dễ thấy Q[α] ‰ Q[jα] vì nếu dấu bằng xảy ra thì ta sẽ có j P Q[α]. Mặt khác, mở rộng Q[j] là mở rộng bậc 2 của Q vì j là nghiệm của đa thức bậc hai x2+x+1, cho nên nó không thể nằm trong một mở rộng bậc ba. Thật vậy, nếu Q[j] Ă Q[α] thì Q[α] sẽ là một không gian vector trên trường Q[j], cho nên chiều của nó như không gian vector trên Q phải là một số chẵn. Trong trường hợp này, các mở rộng bậc ba ứng với 3 nghiệm của P = x3 ´ 2 là đôi một khác nhau: Q[α] ‰ Q[jα] ‰ Q[j2α]. (3.12) Khi K = Q[j], P = x3 ´ 2 vẫn là đa thức bậc ba bất khả quy trong K[x]. Nhưng khi đó các mở rộng bậc ba của K ứng với 3 nghiệm của P = x3 ´ 2 là trùng nhau: K[α] = K[jα] = K[j2α]. (3.13) Ta nhận thấy ở trường hợp đầu, α và jα không phụ thuộc đại số với nhau so với trường cơ sở K = Q. Nói cách khác jα không thể biểu diễn được như tổ hợp đại số của α với hệ số hữu tỉ. Tuy vậy, nếu ta mở rộng trường cơ sở thành K = Q[j], thì α và jα trở nên phụ thuộc đại số. Ví dụ này đưa ta đến với khái niệm trường phân rã của một đa thức bất khả quy. Trường phân rã của một đa thức là công cụ để đo sự phụ thuộc đại số giữa các nghiệm của nó. Trường phân rã sẽ lớn nếu các nghiệm có ít quan hệ đại số, trường phân rã sẽ nhỏ nếu các nghiệm có nhiều quan hệ đại số. Đa thức bất khả quy P P K[x] bậc n được gọi là tách được nếu nó có n nghiệm đôi một khác nhau trong K. Trong trường hợp đặc số không, mọi đa thức bất khả quy đều tách được. Trong trường hợp đặc số p ą 0, có những đa thức bất khả quy nhưng không tách được. Trong bài này, ta sẽ chỉ xét đến những đa thức bất khả quy tách được. Cho P P K[x] là một đa thức bất khả quy bậc n tách được có hệ số đầu bằng một. Ta ký hiệu α1, α2, . . . , αn P K là các nghiệm của P, và gọi trường phân rã của K là trường con của K sinh bởi α1, α2, . . . , αn. Trong vành đa thức L[x], đa thức P phân rã hoàn toàn P = (x ´ α1). . .(x ´ αn), thành tích các thừa số bậc một. 21 Toán yêu người những đồng cộng của online chí Tạp Để làm rõ ý này, ta thực hiện một khảo sát. Ký hiệu L là trường phân rã của P, khi đó L là trường con cực tiểu chứa tất cả các trường con K[α1], K[α2] . . . , K[αn], còn gọi là compositum của K[α1], K[α2] . . . , K[αn]. Ký hiệu Li là compositum của K[α1], K[α2] . . . , K[αn], khi đó ta có chuỗi mở rộng trường liên tiếp K = L0 Ă L1 Ă ¨ ¨ ¨ Ă Ln = L. Ký hiệu li là bậc của mở rộng Li/Li´1. Trường phân rã L là mở rộng bậc l1l2 . . .ln của K. Các số nguyên l1, l2, . . . , ln phản ánh mức độ phụ thuộc đại số giữa các nghiệm α1, α2, . . . , αn. Ta có thể khảo sát chúng tuần tự như sau • Vì P là một đa thức bất khả quy bậc n cho nên L1 là mở rộng bậc l1 = n của L0. • Xét mở rộng tiếp theo L2/L1. Đa thức P xem như phần tử của L1[x] không còn bất khả quy nữa, mà có thể phân tích được thành P = (x ´ α1)Q. Thành phần Q có thể là đa thức bất khả quy, có thể không. • Nếu Q là một đa thức bất khả quy, bậc n ´ 1, thì L2 sẽ là một mở rộng bậc l2 = n ´ 1 của L1. Trong trường hợp này, α1 và α2 không có quan hệ đại số gì với nhau. • Nếu Q P L1[x] không phải đa thức bất khả quy, ta có thể phân tích nó thành Q = Q2Q3 với Q2 là đa thức bất khả quy có nghiệm là α2. Khi đó L2 là mở rộng của L1 có bậc l2 bằng với bậc của đa thức Q2. Trong trường hợp này α1 và α2 có phụ thuộc đại số. • Tiếp tục với mở rộng L3/L2 . . . Qua khảo sát này ta thấy l1 ą l2 ą ¨ ¨ ¨ là một dãy số nguyên giảm thật sự và từ đó suy ra l1 ¨ ¨ ¨ln ď n!. Dãy số này đo mức độ phụ thuộc đại số giữa các nghiệm α1, α2, . . . , αn của P. 6. Nhóm Galois của một đa thức Cho P P K[x] là một đa thức bất khả quy bậc n tách được. Nghiệm của nó trong K là α1, α1, . . . , αn đôi một khác nhau. 22 Toán yêu người những đồng cộng của online chí Ta ký hiêu L là trường phân rã, trường con của K sinh ra bởi α1, α1, . . . , αn. Nhóm Galois ΓL/K là nhóm các tự đẳng cấu mở rộng L/K : Các tự đẳng cấu của mở rộng L/K là các song ánh σ : L Ñ L bảo toàn cấu trúc vành và cấu trúc không gian vector của L trên trường K. Nếu không có nguy cơ nhầm lẫn, ta viết giản lược chỉ số và ngầm hiểu Γ = ΓL/K. Để nhấn mạnh sự phụ thuộc vào P, chúng ta cũng sẽ gọi Γ là nhóm Galois của đa thức P. Cho σ P Γ và α P L là một nghiệm của P, khi đó σ(α) cũng là một nghiệm của P. Vì vậy nhóm Galois Γ tác động lên tập hợp các nghiệm của P. Với ký hiệu đã chọn tα1, . . . , αnu, các nghiệm của P đã được đánh số, tác động của Γ lên chúng được cho bởi đồng cấu nhóm ρP : Γ Ñ Υn vào trong nhóm các hoán vị cấp n. Định lý 6.1. Đồng cấu ρP : Γ Ñ Υn là đơn ánh. Tác động của Γ lên tập t1, 2, . . . , nu là tác động bắc cầu. Số phần tử của Γ đúng bằng với bậc của mở rộng L/K. Chứng minh khẳng định thứ nhất không khó. Nếu σ nằm trong hạch của ρP, thì σ(αi) = αi với mọi nghiệm của P. Trong hoàn cảnh này, σ tác động tầm thường lên toàn bộ L vì L được sinh ra bởi α1, α1, . . . , αn. Chứng minh khẳng định thứ hai và thứ ba khó hơn một chút. Trước hết ta chứng minh rằng mọi đồng cấu K - đại số ξ : L Ñ K đều có ảnh là L. Thật vậy mọi đồng cấu như vậy đều bảo toàn tập tα1, α1, . . . , αnu, mà tập này sinh ra L, cho nên ξ(L) = L. Như vậy ta đã chứng minh rằng AutK(L) = HomKL, K (3.14) Để chứng minh khẳng định thứ ba, ta chỉ còn cần chứng minh rằng |HomKL, K | = degK(L). (3.15) Một mở rộng hữu hạn L của K gọi là mở rộng tách được nếu Tạp nó thoả mãn tính chất này. Nếu L = K[x]/P với P P K[x] là một đa thức bất khả quy bậc n tách được thì L là mở rộng tách được. Thật vậy, trong trường 23 Toán yêu người những đồng cộng của online chí Tạp hợp này, cho một đồng cấu σ : L Ñ K tương đương với cho σ(x) là một nghiệm của P trong K và có đúng n nghiệm khác nhau như vậy. Có thể chứng minh được rằng compositum của mở rộng tách được K1, K2, . . . , Kn với K Ă Ki Ă K là mở rộng tách được. 1 Vì thế, trường phân rã của một đa thức tách được là một mở rộng tách được. Ta quay lại chứng minh khẳng định thứ hai: Tác động của Γ lên tập các nghiệm tα1, α2, . . . , αnu là tác động bắc cầu. Ta sẽ chứng minh tồn tại σ P AutK(L) sao cho σ(α1) = α2. Trước hết ta có đẳng cấu σ : K[α1] Ñ K[α2] cho bởi α1 ÞÑ α2 vì α1 và α2 có cùng đa thức cực tiểu là P. Ta cần chứng minh rằng σ có thể thác triển thành một tự đẳng cấu σ : L Ñ L. Để kết thúc chứng minh, ta cần sử dụng thêm một tính chất nữa của mở rộng tách được: Nếu L/K là một mở rộng tách được, thì tồn tại β P L là phần tử sinh của L. Nói cách khác tồn tại β P L sao cho L = K[β].2 Mở rộng L/K[α1] cũng là mở rộng tách được, cho nên tồn tại β1 P L sao cho L = K[α1][β1]. Ta có thể phát triển σ : K[α1] Ñ K[α2], thành một đồng cấu có dạng σ : K[α1][β1] Ñ K[α2][β2], với β2 P K được lựa chọn thích hợp. Sử dụng (3.14), ta có K[α2][β2] = L, và σ là một tự đẳng cấu của L như ta mong muốn. Ta có thể tóm tắt các thông tin trong mục này như sau. Mỗi đa thức bất khả quy P ứng một nhóm Galois Γ . Nếu các nghiệm của P trong K được đánh số thì có thể coi Γ như một nhóm con của nhóm đối xứng cấp n, có tác động bắc cầu lên tập t1, 2, . . . , nu. Số phần tử của Γ đúng bằng bậc của trường phân rã. 1Xem chứng minh trong sách Algebra của Lang. 2Xem chứng minh trong sách Algebra của Lang. 24 Toán yêu người những đồng cộng của online chí Tạp 7. Tương ứng Galois Như ta đã thấy trong mục trước, nếu L là trường phân rã của đa thức bất khả quy tách được P P K[x], thì mở rộng L/K có tính chất số phần tử của nhóm AutK(L) đúng bằng với bậc của mở rộng. Mở rộng L/K được gọi là mở rộng Galois nếu tính chất này được thoả mãn. Trường phân rã của một đa thức bất khả quy luôn luôn là mở rộng Galois. Mở rộng L/K gọi là mở rộng tách được nếu tồn tại một đa thức bất khả quy P P K[x] tách được sao cho L » K[x]/(P), tất nhiên có thể có nhiều đa thức P như thế. Dễ thấy nếu L = K[x]/(P) là mở rộng tách được như trên và là mở rộng Galois, thì L là trường phân rã của P. Nói cách khác mở rộng Galois là trường phân rã của một đa thức nào đó. Mặt khác, nó có thể đồng thời là trường phân rã của nhiều đa thức khác nhau. Không phải mở rộng nào cũng là mở rộng Galois. Quay lại ví dụ (3.12) mở rộng bậc ba Q[α] của Q, với α là một nghiệm của x3 ´ 2. Nếu σ P AutQ(Q[α]) thì σ(α) cũng phải là một nghiệm của x3 ´ 2. Theo (3.12) thì σ không thể là một tự đẳng cấu của Q[α] trừ trường hợp σ = 1. Nói cách khác Q[α] không phải biểu diễn Galois. Ngược lại, theo (3.13) thì K[α]/K là mở rộng Galois với K = Q[j] với j là căn nguyên sơ bậc ba của đơn vị (3.11). Tổng quát hơn Định lý 7.1. Nếu xn ´ a P K[x] là một đa thức bất khả quy tách được, khi đó nếu K chứa căn nguyên sơ bậc n của đơn vị, thì với mọi nghiệm α P K của đa thức xn ´ a, mở rộng L = K[α] của K là mở rộng Galois. Các mở rộng trung gian giữa K và L có thể được phân loại dựa vào Γ . Đây thường được coi là mệnh đề quan trọng nhất trong lý thuyết Galois, và được gọi tương ứng Galois. Vấn đề cái gì quan trọng nhất luôn luôn có thể bàn cãi. Định lý 7.2. Mỗi mở rộng trung gian K Ă L1 Ă L ứng với một nhóm con Γ1của Γ bao gồm các phần tử γ P Γ tác động lên L như một ánh xạ L1-tuyến tính. Tương ứng ngược lại được cho bởi L1 = LΓ1. Hơn nữa, L1là mở rộng Galois của K khi và chỉ khi Γ1là nhóm con chuẩn tắc của Γ .3 3Nhóm con Γ1 Ă Γ được gọi là nhóm con chuẩn tắc nếu với mọi γ P Γ , ta có γΓ 1γ´1 = Γ1. 25 Toán yêu người những đồng cộng của online chí Tạp Trong trường hợp đó, ta có ΓL1/K = Γ/Γ 1. Trong mục 5, ta đã khảo sát trường phân rã L của một đa thức bất khả quy P P K[x] thông qua chuỗi mở rộng liên tiếp K = L0 Ă L1 Ă L2 Ă ¨ ¨ ¨ Ă Ln = L, với Li là compositum của K[α1], K[α2], . . . , K[αi]. Chuỗi mở rộng tương ứng với chuỗi các nhóm con của Γ Γ = Γ0 Ą Γ1 Ą ¨ ¨ ¨ Ą Γn = 0. (3.16) Có thể chứng minh được rằng Γi = ΓXΥn´i với mọi i = 1, 2, . . . , n, trong đó Υn´i là nhóm con các phần tử của Υn cố định các phần tử 1, 2, . . . , i trong tập t1, 2, . . . , nu. Các nhóm con Γ1, Γ2, . . . nói chung không phải là nhóm con chuẩn tắc của Γ , và L1, L2, . . . không phải là mở rộng Galois của K. Trong một mục sau, mục 8, chúng ta sẽ khảo sát kỹ trường hợp chuỗi mở rộng Galois. 8. Tiêu chuẩn để giải được phương trình bằng căn thức Xét ví dụ cho bởi chuỗi các mở rộng căn thức như ở (3.10) K = K0 Ă K1 Ă ¨ ¨ ¨ Ă Kr, (3.17) với Ki » Ki´1[x]/(xni ´ βi). Giả thiết rằng K chứa các căn nguyên sơ của đơn vị bậc n1, n2, . . . , nr. Khi đó với mọi i, Ki là mở rộng Galois của Ki´1, và từ đó ta có thể suy ra Kr là mở rộng Galois của K. Ký hiệu Γi = ΓKr/Ki, ta sẽ có chuỗi các nhóm con chuẩn tắc như sau: Γ = Γ0 Ą Γ1 Ą Γ2 Ą ¨ ¨ ¨ với Γi´1/Γi = ΓKi/Ki´1 » Z/niZ. Nói cách khác, nhóm Γ là nhóm giải được. Định lý 8.1. Cho P P K[x] là một đa thức bất khả qui bậc n tách được với hệ số trong trường K có căn nguyên sơ của đơn vị ở mọi cấp r ď n. Điều kiện cần và đủ để nghiệm của P có thể biểu diễn như một biểu thức đại số với căn thức là nhóm Galois của P là nhóm giải được. 26 Toán yêu người những đồng cộng của online chí Tạp Cho α P K là một nghiệm của P. Như đã phân tích trong mục 4, α biểu diễn được dưới dạng biểu thức đại số có căn thức tương đương với việc tồn tại một chuỗi mở rộng liên tiếp như (3.17), với Ki » Ki´1[x]/(xni ´ βi), và K[α] Ă Kr. Vì trường phần rã L của P là mở rộng Galois nhỏ nhất chứa K[α] cho nên: K Ă L Ă Kr. Điều này kéo theo ΓP = ΓL/K là thương của Γ . Với điều kiện trường cơ sở Γ chứa đủ căn nguyên sơ của đơn vị, ta đã chỉ ra ở trên là Γ là nhóm giải được. Vì vậy nhóm Galois ΓP của đa thức P cũng là nhóm giải được. ΓP là nhóm giải được là điều kiện cần để α biểu diễn được như một biểu thức đại số với căn thức. Để chứng minh điều kiện này cũng là điều kiện đủ, ta cần chứng minh rằng nếu K là một trường có nghiệm nguyên sơ cấp n của đơn vị và nếu L/K là mở rộng Galois có nhóm Galois đẳng cấu với Z/nZ, thì tồn tại β P K để sao cho L » K[x]/(xn ´ β). Giả sử mở rộng L là trường phân rã của một đa thức bất khả qui P P K[x] có bậc n. Nếu α1, α1, . . . , αn là các nghiệm của P ở trong K thì L là mở rộng của K sinh bởi các nghiệm này. Chọn một phần tử sinh σ của nhóm Galois ΓL/K = Z/nZ. Vì tác động của ΓL/K lên tập α1, , α1, . . . , αn là tác động bắc cầu, cho nên σ tương ứng với một hoán vị n - chu trình. Ta có thể giả sử σ(α1) = α2, σ(α2) = α3, . . . , σ(αn) = α1. Chọn ζ P K là một căn nguyên sơ cấp n của đơn vị và thiết lập giải thức Lagrange: ξ = α1 + ζα2 + ¨ ¨ ¨ + ζn´1αn. Lập luận như trong trường hợp n = 3, ta thấy ξn = β là một phần tử của K và từ đó suy ra rằng L » K[x]/(xn ´ β). Để biết một phương trình có thể giải được bằng căn thức hay không, ta “chỉ cần” biết xem nhóm Galois của nó có thể giải được hay không. Tính nhóm Galois của một đa thức P tuỳ ý 27 Toán yêu người những đồng cộng của online chí Tạp hoàn toàn không dễ. Quy trình khảo sát trình bày trong mục 5, cho ta một số thông tin về nhóm Galois, trong đó có một chuỗi nhóm con (3.16), nhưng đó thường là những nhóm con không chuẩn tắc. Trong trường hợp của đa thức tổng quát P = xn + a1xn´1 + ¨ ¨ ¨ + an P K[x], (3.18) với K = k(a1, a2, . . . , an) là trường các phân thức với biến số a1, a2, . . . , an, lập luận như trong 9, ta thấy ΓP = Υn. Như vậy đối với phương trình tổng quát, ta cần tìm hiểu với n nào thì nhóm đối xứng Υn là nhóm giải được. Ta sẽ chỉ ra rằng các nhóm Υ3, Υ4 là giải được và nhờ đó có thể tìm ra công thức biểu diễn nghiệm của phương trình bậc ba và bậc bốn. Trong khi đó Υn là nhóm không giải được với mọi n ě 5. 9. Phương trình bậc ba Lời giải phương trình bậc ba của Tartaglia khá phức tạp và nó giống như một cái gì từ trên trời rơi xuống. Lời giải phương trình bậc bốn của Ferrari còn phức tạp hơn nữa. Sau này, Lagrange đưa ra phương pháp rất đẹp để tìm ra phương pháp chung cho lời giải của Tartaglia, Cardano và Ferrari. Ông sáng tạo ra một công cụ mới, gọi là resolvent, mà chúng ta sẽ tạm chuyển ngữ thành “giải thức”. Để minh hoạ cho công dụng của phương pháp Lagrange, ta sẽ trình bày lời giải phương trình bậc ba tổng quát theo phương pháp này với chút ít hỗ trợ của lý thuyết Galois. Mặc dù phương pháp giải thức của Lagrange có thể diễn giải dễ dàng bằng lý thuyết Galois, ta cũng nên lưu ý là nhóm Galois sinh ra sau phương pháp giải thức Lagrange. Trong đại số hiện đại, ta có thể gán cho chữ tổng quát một nghĩa chính xác: Ta chọn trường cơ sở K = k(a, b, c) Ą R = k[a, b, c], là trường các biểu thức hữu tỉ với biến số a, b, c và hệ số nằm trong một trường k nào đó. Đa thức bậc ba tổng quát là đa thức P = x3 + ax2 + bx + c P R[x]. 28 Toán yêu người những đồng cộng của online chí Tạp Ta sẽ giả sử rằng trường k có căn nguyên sơ bậc ba của đơn vị. Nói cách khác đa thức x3 ´ 1 P k[x] phân rã hoàn toàn thành: x3 ´ 1 = (x ´ 1)(x ´ j)(x ´ j2), với j P k là căn nguyên sơ bậc ba của đơn vị. Lấy ví dụ, ta có thể chọn k = Q[j] với j như trong (3.11). Cho K là một trường đóng đại số chứa K, và gọi α1, α2, α3 là các nghiệm của P ở trong K. Trường phân rã của K : L = k(α1, α2, α3) Ą S = k[α1, α2, α3], là trường các thương của các đa thức có biến số α1, α2, α3 thoả ´a = α1 + α2 + α3 b = α1α2 + α2α3 + α3α1 ´c = α1α2α3 Có thể chứng minh được rằng S là module tự do cấp sáu trên vành R và L là không gian vector có chiều bằng sáu trên trường K. Như vậy nhóm Galois Γ của P có sáu phần tử và vì vậy nó chỉ có thể là toàn bộ nhóm đối xứng Υ3. Để giải phương trình bậc ba tổng quát, ta sẽ khảo sát nhóm đối xứng Υ3. Ta sẽ thể hiện một hoán vị cấp ba như trong ví dụ sau: (2, 3, 1) là hoán vị 1 Ñ 2, 2 Ñ 3, 3 Ñ 1. Các phần tử của Υ3 có thể được phân loại như sau • Phần tử đơn vị (1, 2, 3). • Phần tử có 2-chu trình (2, 1, 3), (1, 3, 2), (3, 2, 1). • Phần tử 3-chu trình (2, 3, 1), (3, 1, 2). Đồng cấu dấu sgn : Υ3 Ñ t˘1u gán cho ba phần tử có 2-chu trình dấu ´1 và gán cho ba phần tử còn lại dấu +1. Hạch của đồng cấu dấu sgn : Υ3 Ñ t˘1u là nhóm luân phiên Θ3. Nhóm này có 3 phần tử: Θ3 = t(1, 2, 3),(2, 3, 1),(3, 1, 2)u và đẳng cấu với nhóm xích Z/3Z. Tóm lại ta có dãy khớp 0 Ñ Θ3 Ñ Υ3 Ñ Z/2Z Ñ 0 (3.19) 29 Toán yêu người những đồng cộng của với Θ3 » Z/3Z. Nhóm Υ3 là nhóm giải được. Nhóm con Θ3 tương ứng với mở rộng trung gian K+ = LΘ3 bao gồm các phần tử của L cố định dưới tác động của Θ3. Ta có chuỗi các mở rộng liên tiếp K Ă K+ Ă L. với K+/K là mở rộng Galois cấp hai có nhóm Galois Z/2Z, và L/K+ là mở rộng Galois cấp ba có nhóm Galois Z/3Z. Quá trình biểu diễn nghiệm của phương trình bậc ba phổ quá như biểu thức đại số có căn thức có thể chia thành hai bước: • Sử dụng dãy khớp (3.19) để xây dựng mở rộng trung gian. K Ă K+ Ă L với K+/K là mở rộng Galois cấp hai có nhóm Galois Z/2Z, và L/K+ là mở rộng Galois cấp ba có nhóm Galois Z/3Z. • Biểu diễn các mở rộng trung gian K+/K dưới dạng K+ = K[x]/(x2 ´ β1), và L/K+ dưới dạng L = K+[x]/(x3 ´ β2). Ta có thể viết tường minh một phần tử của K+ : δ = (α1 ´ α2)(α2 ´ α3)(α3 ´ α1). Dễ thấy δ là ổn định dưới tác động của Θ3. Ta cũng để ý ngay online thấy δ2 = ´d với d =ź i‰j (αi ´ αj), là biệt thức của P. Biệt thức d là một phần tử của K và ta có K+ » K[x]/(x2 + d). (3.20) chí Thật vậy, ta có đồng cấu trường: K[x]/(x2 + d) Ñ K+, Tạp xác định bởi x ÞÑ δ. Vì cả hai vế đều là không gian vector hai chiều trên K, vì đồng cấu trường luôn là đơn ánh, cho nên nó bắt buộc phải là song ánh. 30 Toán yêu người những đồng cộng của online chí Tạp Nói cách khác, mọi phần tử của K+ đều có thể biểu diễn một cách duy nhất dưới dạng m + nδ với m, n P K. Để chứng tỏ phương trình tổng quát bậc ba có thể giải được bằng căn thức, ta chỉ còn cần chứng minh rằng mở rộng L/K+ có thể biểu diễn được dứới dạng phương trình L = K+[x]/(x3 ´ β), với một phần tử β P L+ nào đó. Ký hiệu σ = (2, 3, 1) là hoán vị tác động lên các nghiệm của P như sau: σ(α1) = α2, σ(α2) = α3 và σ(α3) = α1. Giải thức Lagrange có dạng: ξ = α1 + jα2 + j2α3. Ta nhận thấy rằng: σ(ξ) = j´1ξ và σ2(ξ) = j´2ξ, và từ đó suy ra β = ξσ(ξ)σ2(ξ) = ξ3. Phần tử β biểu diễn như tích ξσ(ξ)σ2(ξ) hiển nhiên có tính ổn định dưới tác động của σ. Vì vậy β P K+. Ta khẳng định rằng L » K+[x]/(x3 ´ β). (3.21) Thật vậy ta có đồng cấu vành φ : K+[x]/(x3 ´ β) Ñ L, xác định bởi x ÞÑ ξ vì ξ3 = β. Vì σ(ξ) ‰ ξ, cho nên ξ R K, và ảnh của đồng cấu φ là một mở rộng trung gian K Ă im(φ) Ă L với K ‰ im(φ). Ta nhận thấy chiều của im(φ) như không gian vector trên K phải bằng ba vì mở rộng bậc ba L không thể chứa trong nó một mở rộng bậc hai. Nói cách khác, đồng cấu φ là toàn ánh. Vì không gian nguồn và đích có cùng số chiều, φ là đẳng cấu. Như vậy mọi phần tử của L, trong đó có α1, α2, α3, có thể biểu diễn một cách duy nhất dưới dạng m0 + m1ξ + m2ξ2, với m0, m1, m2 P K+. 31 Toán yêu người những đồng cộng của online chí Tạp Bản thân ξ thoả mã phương trình ξ3 = β với β P K+. Mọi phần tử của K+ đều có thể biểu diễn một cách duy nhất dưới dạng m + nδ với m, n P K và δ2 = d. Chịu khó tường minh hoá các hệ số m, n, m0, m1, m2, ta sẽ tìm lạo được công thức Tartaglia (3.5) cho nghiệm của phương trình bậc ba tổng quát x3 + ax2 + bx + c = 0. 10. Phương trình bậc bốn Định lý 10.1. Nhóm Υ4 là nhóm giải được. Ký hiệu S là tập t1, 2, 3, 4u và Ψ2(S) là tập các tập con của S có đúng hai phần tử. Tập này có 6 phần tử chia thành ba cặp các tập con đối nhau: t1, 2u, t3, 4u t1, 3u, t2, 4u t1, 4u, t2, 3u và gọi Φ2(S) là tập các cặp tập con đối nhau như trên. Ta có ánh xạ 2-1 Ψ2(S) Ñ Φ2(S). (3.22) Nhóm Υ4 các hoán vị của S, tác động một cách tương thích lên Φ2(S) và Ψ2(S). Tác động của Υ4 lên Φ2(S) cho ta một đồng cấu Υ4 Ñ Υ3. Khảo sát kỹ hơn tác động Υ4 lên Φ2(S) và Ψ2(S) ta có dãy khớp 0 Ñ (Z/2Z)2 Ñ Υ4 Ñ Υ3 Ñ 0 (3.23) và từ đó suy ra rằng nhóm Υ4 là nhóm giải được. Bạn đọc có thể dùng giải thức Lagrange để tìm ra biểu thức căn thức cho nghiệm phương trình bậc bốn tổng quát, giống như trường hợp phương trình bậc ba đã trình bày ở mục 9. 11. Phương trình bậc năm trở lên Định lý 11.1. Với mọi n ě 5, Υn không phải là nhóm giải được. Nhóm đối xứng Υn có đồng cấu dấu với hạch là nhóm luân phiên Θn 0 Ñ Θn Ñ Υn Ñ t˘1u Ñ 0 (3.24) 32 Toán yêu người những đồng cộng của online chí Tạp Có thể chứng minh rằng với mọi n ě 5, nhóm luân phiên Θn là nhóm đơn, tức là một nhóm không có nhóm con chuẩn tắc, ngoài nhóm tầm thường và chính nó. Nhóm con chuẩn tắc là hợp của một số lớp liên hợp và số phần tử của nhóm con bằng với tổng số phần tử của một số lớp liên hợp. Mặt khác, tổng số này phải là ước của số phần tử của Θ5. Bằng cách liệt tất cả các lớp liên hợp của Θ5 và lực lượng của chúng, ta nhận ra rằng tổng lực lượng của một số lớp liên hợp của Θ5 không thể đúng bằng một ước thực sự của 60. Vì thế nhóm Θ5 không có nhóm con chuẩn tắc nào ngoài chính nó và nhóm tầm thường. Bạn đọc có thể chứng minh bằng qui nạp rằng Θn là nhóm đơn với mọi n ě 5 xuất phát từ trường hợp n = 5. 33 Toán yêu người những đồng cộng của online chí Tạp 34 Tạp chí online của những người yêu Toán cộng đồng ToánÉvariste Galois yêu người những đồng cộng của online chí Tạp Người dịch: Lưu Trọng Luân 1 Đại học FPT Évariste Galois 2 sinh tại Bourg La Reine (gần Paris) là con ông Nicholas Gabriel Galois và bà Adelaide Marie Demante. Cha mẹ Galois đều là những trí thức được giáo dục kỹ về triết học, văn học cổ điển và tôn giáo. Tuy nhiên, không ai trong gia đình Galois bộc lộ khả năng toán học. Mẹ của Galois là người thầy duy nhất dạy dỗ ông cho đến năm 12 tuổi. Bà dạy ông tiếng Hy Lạp, La tinh và tôn giáo, cũng là lúc bà bắt đầu gieo tư tưởng hoài nghi của mình cho con. Cha của Galois là người có ảnh hưởng trong cộng đồng và năm 1815 được bầu làm thị trưởng Bourg-la-Reine. Thời điểm bắt đầu những sự kiện lịch sử đóng vai trò quan trọng trong cuộc đời Galois chính là cuộc đánh chiếm nhà tù Bastille ngày 14/07/1789. Từ lúc đó, vương triều Louis 16 bị lung lay dữ đội khi đông đảo người dân Pháp đoàn kết lại nhằm lật đổ sự cai trị đặc quyền của giáo hội và nhà nước. Bất chấp những nỗ lực thỏa hiệp, vua Louis 16 đã bị mang ra xét xử sau khi tìm cách trốn khỏi đất nước. Sau khi nhà vua bị hành hình vào ngày 21/01/1973, nước Pháp rơi vào tình trạng kinh hoàng với nhiều phiên xét xử chính trị. Đến cuối năm 1793, có tới 4595 tù nhân chính trị bị giam giữ ở Paris. Tuy nhiên, tình hình đất nước cũng bắt đầu sáng sủa hơn sau khi quân đội nước này, dưới sự chỉ huy của Napoleon đã giành hết chiến thắng này đến chiến thắng khác. Napoleon trở thành Đệ nhất Tổng tài vào năm 1800 rồi lên ngôi Hoàng đế vào năm 1804. Quân đội Pháp tiếp tục chinh phục châu Âu trong khi quyền lực của Napoleon ngày càng được củng cố. Năm 1811, Napoleon đạt đến đỉnh cao quyền lực. Nhưng đến 1Nguồn: www-history.mcs.st-andrews.ac.uk/Biographies/Galois.html 2Nhà toán học người Pháp (25/10/1811 - 31/05/1832) 35 Toán yêu người những đồng cộng của online chí Tạp năm 1815 thì quyền lực đó sụp đổ. Cuộc tấn công Nga năm 1812 thất bại kéo theo những cuộc bại trận khác. Quân liên minh tiến vào Paris ngày 31/03/1814. Napoleon thoái vị ngày 6/4 và Louis XVIII được liên minh đưa lên làm vua. Năm 1815 chứng kiến 100 ngày nổi tiếng. Napoleon tiến vào Paris ngày 20/3, bị đánh bại tại Waterloo ngày 18/6 và thoái vị lần thứ hai ngày 22/6. Louis XVIII được khôi phục ngôi vua nhưng mất vào tháng 9/1824. Charles X trở thành vị vua mới. Galois lúc này đang đi học. Ông vào học lớp 4 nội trú trường Lycée of Louis-le-Grand ngày 06/10/1823. Trong học kỳ đầu tiên, một cuộc nổi loạn nhỏ nổ ra và 40 học sinh bị đuổi học. Galois không liên quan đến sự việc này. Năm học 1824 ´ 1825, ông đạt học lực giỏi và nhận nhiều giải thưởng. Tuy nhiên, năm 1826, Galois phải học lại vì môn hùng biện không đạt yêu cầu. Tháng 2/1827 là thời điểm mang tính bước ngoặc trong cuộc đời Galois. Ông vào lớp toán đầu tiên của mình, lớp của M. Vernier. Ngay lập tức, ông đã bị toán học cuốn hút và giáo viên hướng dẫn nhận xét: Niềm đam mê toán học đã chi phối cậu ấy, tôi nghĩ tốt nhất là ba mẹ cậu ấy nên cho phép cậu không học bất kỳ môn gì khác ngoại trừ môn này. Cậu ấy đang lãng phí thời gian ở đây, làm phiền các giáo viên và chuốc lấy nhiều hình phạt. Học bạ của Galois bắt đầu xuất hiện các từ cá biệt, kỳ dị, lập dị và hướng nội. Có lẽ đây là nhà toán học lập dị nhất của mọi thời đại. Thầy giáo M. Vernier nhận xét: Thông minh, tiến bộ đáng kể nhưng chưa đủ phương pháp. Năm 1828, Galois thi vào trường Bách khoa Paris nhưng trượt. Đây là trường đại học danh tiếng ở Paris và Galois muốn thi vào trường để thuận lợi cho việc học. Đồng thời ông cũng muốn vào trường vì lúc này phong trào chính trị trong giới sinh viên ở đây đang diễn ra rất mạnh mẽ trong khi Galois muốn theo bước cha mẹ ông trở thành người tích cực ủng hộ phe cộng hòa. Trở về lại Louis-le-Grand, Galois ghi danh vào lớp chuyên toán của Louis Richard. Tuy nhiên ông lại tập trung ngày càng nhiều vào những nghiên cứu của riêng mình và ít để ý đến việc học tại trường hơn. Ông nghiên cứu môn hình học của Legendre và các luận án của Lagrange. Richard nhận xét: 36 Toán yêu người những đồng cộng của online chí Tạp Cậu sinh viên này chỉ thích tập trung vào những vấn đề đỉnh cao của toán học. Tháng 4/1829 Galois công bố công trình toán học đầu tiên về liên phân số trên Annales de mathématiques. Ngày 25/5 và 1/6 ông gửi các bài viết về phương pháp giải các phương trình đại số cho Viện hàn lâm Khoa học. Cauchy là người được phân công đánh giá công trình này. Bi kịch ập đến với Galois vào ngày 02/07/1829 khi cha ông tự tử. Linh mục xứ Bourg-la-Reine đã giả mạo tên của thị trưởng Galois trên những bài châm biếm nhằm vào những người thân của gia đình Galois. Cha của Galois là người tốt và vụ scandal đã vượt quá sức chịu đựng của ông. Ông đã treo cổ tự sát trong căn hộ của mình ở Paris, cách Louis-le-Grand, nơi con mình đang học chỉ vài bước chân. Galois đã bị tác động nghiêm trọng bởi cái chết của cha mình và nó đã ảnh hưởng lớn đến hướng đi sau này của ông. Vài tuần sau cái chết của cha mình, Galois tiếp tục đăng ký thi vào trường Bách khoa Paris lần thứ hai. Lần này ông lại trượt, có lẽ một phần do nó rơi vào thời điểm tồi tệ nhất ngay sau cái chết của cha ông, một phần do ông chưa bao giờ giỏi việc diễn đạt những ý tưởng toán học sâu sắc của mình. Vì thế Galois đành phải vào học tại École Normale, một nhánh của trường Louis-le-Grand. Để vào được đây, ông đã phải dự kỳ thi tú tài mà nếu vào được trường Bách khoa Paris thì Galois đã không cần đến nó. Ông thi đậu và nhận bằng tốt nghiệp ngày 29/12/1829. Người đánh giá môn toán nhận xét: Sinh viên này đôi khi diễn đạt ý kiến khó hiểu nhưng cậu ta thông minh và bộc lộ tinh thần nghiên cứu đặc biệt. Giám khảo môn văn thì nhận xét: Đây là sinh viên duy nhất có kết quả rất tệ, cậu ta tuyệt đối chẳng biết gì. Họ nói với tôi cậu ta có khả năng toán phi thường. Thật ngạc nhiên vì sau buổi thi này, tôi tin là cậu ta chỉ có một chút thông minh. Galois gửi thêm cho Cauchy bài nghiên cứu về lý thuyết phương trình nhưng sau đó nhận ra nó trùng với một phần trong công trình được đăng sau khi mất của Abel. Sau đó, Galois theo lời khuyên của Cauchy gửi một bài nghiên cứu mới về điều kiện phương trình giải được bằng căn thức vào tháng 2/1830. Bài 37 Toán yêu người những đồng cộng của online chí Tạp báo được gửi cho Fourier, thư ký của Viện hàn lâm Paris để xét duyệt Giải thưởng lớn về toán học. Fourier mất tháng 4/1830 và công trình này của Galois không bao giờ được tìm thấy nữa. Galois, sau khi đọc công trình của Abel và Jacobi đã bắt tay vào việc nghiên cứu lý thuyết hàm eliptic và tích phân Abel. Với sự hỗ trợ của Jacques Sturm, ông đã công bố 3 bài báo trên Bulletin de Férussac vào tháng 4/1830. Tuy nhiên, tháng 6, ông biết được rằng giải thưởng của học viện sẽ được đồng trao cho Abel (sau khi mất) và Jacobi và công trình của ông đã không hề được xem xét. Tháng 7/1830 nổ ra cuộc cách mạng. Vua Charles X phải trốn khỏi nước Pháp. Bạo động diễn ra trên các đường phố Paris và giám đốc trường École Normale, M. Guigniault, đóng cổng trường để ngăn sinh viên ra ngoài tham gia bạo động. Galois tìm cách trèo tường để tham gia nhưng không thành. Tháng 12/1830 M. Guigniault viết một số bài báo chỉ trích sinh viên và Galois viết thư đáp trả trên Gazette des Écoles, chỉ trích M. Guigniault vì hành động giam sinh viên bên trong trường. Vì lá thư này mà Galois bị đuổi học và gia nhập đội pháo binh của Vệ binh quốc gia, một nhánh dân quân tự vệ theo phe cộng hòa. Ngày 31/12/1830, đội pháo binh của Vệ binh quốc gia bị hoàng gia ra lệnh giải tán vì vua mới Louis-Phillipe lo ngại đây là một mối đe dọa đối với ngai vàng. Hai bài công bố nhỏ, một bản tóm tắt đăng trên trên Annales de Gergonne (12/1830) và một lá thư về việc giảng dạy khoa học trên Gazette des Écoles (2/1/1831) là những ấn phẩm cuối cùng trong đời ông. Tháng 1/1831 Galois nỗ lực quay trở lại với toán học. Ông tổ chức vài lớp về đại số cao cấp thu hút 40 sinh viên đến dự buổi đầu tiên nhưng sau đó con số này nhanh chóng giảm xuống. Ông được Poisson mời gửi phiên bản thứ ba của công trình của mình về phương trình cho Viện hàn lâm và ông đã thực hiện ngày 17/1. Ngày 18/4, Sophie Germain viết một lá thư cho bạn cô, nhà toán học Libri kể về tình hình của Galois ... cái chết của M. Fourier, là mất mát quá lớn cho sinh viên Galois người mà cho dù tính tình kỳ quặc, đã bộc lộ thiên hướng thông minh. Những bất hạnh này quá lớn đến nổ đã khiến Galois bị đuổi khỏi École Normale. Anh ta không tiền bạc. Họ nói anh ta sẽ bị điên hoàn toàn. Tôi sợ điều này là thật... 38 Toán yêu người những đồng cộng của online chí Tạp Cuối năm 1830, tất cả 19 sĩ quan thuộc đội pháo binh của Vệ binh quốc gia bị bắt và bị kết tội âm mưu lật đổ chính quyền. Họ được tuyên trắng án và ngày 09/05/1831, có 200 người theo phe cộng hòa tập trung ăn tối mừng việc này. Trong bữa tiệc, Galois nâng ly trong khi tay cầm con dao găm đang mở ra như vẻ hăm dọa nhà vua, Louis-Phillipe. Sau bữa ăn tối, Galois bị bắt và giam tại nhà tù Sainte-Pélagie. Ông được thả ra sau phiên xử ngày 15/6. Ngày 14/7, ngày diễn ra cuộc tấn công nhà tù Bastille và Galois bị bắt trở lại vì đã mặc đồng phục của đội pháo binh của Vệ binh quốc gia vốn đã bị giải tán. Lúc đó ông cũng đang mang trong người một khẩu súng trường đã nạp đạn, vài khẩu súng ngắn và một dao găm. Galois bị đưa trở lại nhà tù Sainte-Pélagie. Thời gian này, ông nhận được tin công trình của mình đã bị bác bỏ. Poisson nhận xét: Lập luận của Galois chưa đủ rõ ràng và chưa được phát triển đầy đủ để cho phép chúng tôi đánh giá được tính chính xác của nó. Tuy nhiên, ông đã khuyến khích Galois công bố một bản tóm tắt đầy đủ hơn công trình của mình. Ở trong nhà tù Sainte-Pélagie, Galois đã cố dùng dao tự tử nhưng những bạn tù khác đã ngăn ông lại. Khi say rượu trong tù, ông bộc lộ tâm hồn mình: Bạn có biết tôi thiếu gì không? Tôi chỉ tiết lộ với bạn thôi: Đó là người mà tôi chỉ có thể yêu thương và yêu thương trong tâm khảm. Tôi đã mất cha tôi và không ai có thể thay thế được ông, bạn có hiểu không? Tháng 3/1832, một trận dịch tả quét qua Paris và những tù nhân, trong đó có Galois, được chuyển đến trại Sieur Fault rier. Nơi đây, dường như ông đã phải lòng Stephanie-Felice du Motel, con gái một bác sĩ địa phương. Sau khi ra tù ngày 29/4, Galois viết thư qua lại với Stephanie và rõ ràng là cô này đã tìm cách né tránh cuộc tình. Cái tên Stephanie xuất hiện nhiều lần bên lề các bản ghi chép của Galois. Galois đấu súng với Perscheux d’Herbinville ngày 30/5 mà lý do không ai rõ nhưng chắc chắn việc này có liên quan đến Stephanie. Một trong số những ghi chép này có câu: Có gì đó cần bổ sung trong chứng minh này. Nhưng tôi lại không có thời gian. 39 Toán yêu người những đồng cộng của online chí Tạp Chính điều này đã dẫn đến huyền thoại rằng ông đã dành đêm cuối cùng viết lại tất cả những gì ông biết về lý thuyết nhóm. Câu chuyện này có vẻ như đã được phóng đại lên. Galois bị thương trong cuộc đấu súng và bị d’Herbinville và những người đi theo bỏ mặc cho đến khi một nông dân tìm thấy. Ông mất tại bệnh viên Cochin ngày 31/5 và đám tang được tổ chức ngày 2/6. Nó trở thành tâm điểm của cuộc nổi loạn của phe cộng hòa kéo dài nhiều ngày. Em trai Galois và bạn ông, Chevalier, đã sao chép lại các bài viết liên quan đến toán học của ông và gửi cho Gauss, Jacobi cùng những người khác. Galois cũng từng mơ ước được Jacobi và Gauss nhận xét công trình của mình. Người ta không tìm thấy nhận xét của những người này. Tuy nhiên, các bài báo đã đến tay Liouville, người vào tháng 9/1843 công bố trước viện hàn lâm rằng ông đã tìm thấy trong các bài báo của Galois một lời giải chính xác. ... vừa chính xác vừa sâu sắc cho bài toán tuyệt vời sau: Cho một phương trình bất khả quy với bậc nguyên tố, xét xem nó có giải được bằng căn thức không? Liouville xuất bản những bài báo của Galois trên tạp chí của mình năm 1846. Lý thuyết mà Galois phác thảo trong những bài báo này ngày nay được gọi là lý thuyết Galois. 40 Tạp chí online của những người yêu Toán cộng đồng ToánNGHỊCH ĐẢO MOBIUS ¨ yêu người những đồng cộng của Ngô Quang Hưng (Đại học Buffalo, Mỹ) Phép nghịch đảo Mobius khởi nguyên là một công thức trong lý ¨ thuyết số. Đến những năm 1960 thì Giáo sư Gian-Carlo Rota cho chúng ta thấy công thức trong lý thuyết số là một trường hợp đặc biệt của một công thức áp dụng trên các tập thứ tự bán phần (poset). Công thức Mobius tổng quát có nhiều ứng dụng ¨ trong Toán và Máy Tính. Trong bài này ta rảo qua chứng minh của phép nghịch đảo Mobius trên các tập thứ tự bán phần và ¨ một vài ứng dụng của nó. 1. Ba ví dụ 1.1. Toán tổ hợp Công thức inclusion-exclusion nói rằng, để đếm tổng số nhóc tì có Chí Phèo là bố hoặc thị Nở là mẹ, thì ta cộng số con của chí Phèo với số con của thị Nở trừ đi số con chung. Nói cách khác, cho n tập hợp hữu hạn A1, ¨ ¨ ¨ , An thì ta có thể tính lực lượng của hội của chúng bằng công thức: online ˇˇˇˇŤni=1 Aiˇˇˇˇ =řni=1|Ai| ´ř1ďiăjďn|Ai X Aj| + ř 1ďiăjăkďn|Ai X Aj X Ak| ´ ¨ ¨ ¨ + (´1)n´1|A1 X ¨ ¨ ¨ X An| Công thức này một số sách nói là của Abraham de Moivre; nhưng có vẻ nó xuất hiện năm 1854 từ một bài báo của Daniel da Silva, và lần nữa năm 1883 trong một bài báo của Joseph chí Sylvester [11]. Bài tập 1.1. Năm 1891, Franc¸ois Édouard Anatole Lucas (cha đẻ bài toán tháp Hà Nội) đặt câu hỏi sau đây: “cho một cái bàn Tạp tròn và m cặp vợ chồng, có bao nhiêu cách để xếp họ ngồi nam nữ xem kẽ sao cho không cặp vợ chồng nào ngồi kề nhau?" Ta có thể dùng công thức IE để trả lời câu hỏi của Lucas. 41 Toán 1.2. Lý thuyết số Trong lý thuyết số có một công thức gọi là công thức nghịch đảo Mobius ¨ [10], xinh hơn hoa hậu! Công thức này phát biểu như sau: Cho 2 hàm số f, g bất kỳ trên miền số nguyên dương, ta có yêu người g(d), @n ě 1 tương đương với f(n) = ÿ d|n g(n) = ÿ d|n µ(d)f(n/d), @n ě 1 những trong đó µ(d) là hàm Mobius ¨ định nghĩa như sau µ(d) = đồng $’& 1 d là tích của một số chẵn các số nguyên tố khác nhau ´1 d là tích của một số lẻ các số nguyên tố khác nhau ’% 0 d có ước số là bình phương của một số nguyên tố cộng của online chí Tạp August Ferdinand Mobius là một nhà thiên văn người Đức, từng ¨ là trợ lý của Gauss; ông cũng là tác giả của cái băng Mobius ¨ lừng danh trong hình học Tô-pô. 1.3. Hình tô-pô Công thức đa diện Euler phát biểu rằng v ´ e + f = 2, trong đó v, e, f là tổng số đỉnh, cạnh, và mặt của một khối đa diện ba chiều. Euler khám phá ra công thức này năm 1752, nhưng có vẻ như Descartes cũng đã biết nó từ 1640. Trăm năm sau, năm 1852, Schlafli phát biểu công thức tổng quát cho các đa diện ¨ lồi trong không gian n-chiều, nhưng chứng minh đúng phải chờ đến người khổng lồ Henry Poincaré (1893, [4]). Công thức Euler tổng quát, cũng gọi là công thức Euler-Poincaré, phát biểu như sau. Gọi Fi là tổng số “mặt” i-chiều của đa diện n chiều (“mặt” 0-chiều là đỉnh, mặt 1-chiều là cạnh, vân vân). Ta quy ước Fn = 1 và F´1 = 1 để viết cho tiện. Thì ta có công thức Euler-Poincaréÿn i=´1 (´1)iFi = 0. 42 Toán yêu người những đồng cộng của online chí Tạp 1.4. Gian-Carlo Rota Năm 1964, trong bài đầu tiên của một chuỗi bài báo kinh điển đặt nền móng cho lý thuyết tổ hợp đại số [5], Gian-Carlo Rota cho chúng ta biết cả ba công thức trên chẳng qua là trường hợp đặc biệt của phương pháp tính nghịch đảo Mobius trên các ¨ tập hợp thứ tự một phần (partially ordered set, hay poset). Mà phương pháp nghịch đảo Mobius trên posets thì chẳng qua chỉ ¨ là phát biểu sau đây: nếu A là một ma trận vuông khả nghịch, thì x = Ay tương đương với y = A´1x. Đại số tuyến tính muôn năm! Rota có quyển sách rất thú vị có nhiều giai thoại nổi tiếng trong giới chuyên môn tên là “Indiscrete Thoughts” [6]. Dưới đây chúng ta duyệt qua phương pháp của Rota, chứng minh cả ba công thức trên, và chứng minh bổ đề Sauer-Shelah để tự thưởng công. 2. Nghịch đảo Mobius trên posets ¨ 2.1. Tập hợp thứ tự bán phần (Poset) Poset đại khái là một tập hợp mà ta có thể so sánh lớn nhỏ giữa một số cặp phần tử nhưng không nhất thiết là so được tất cả các cặp. Thứ tự lớn nhỏ này có tính bắc cầu (transitive) và không tạo ra thứ tự luẩn quẩn. Cụ thể hơn, một poset (tập thứ tự bán phần) là một cặp (P, ĺ) trong đó P là một tập hợp và ĺ là một quan hệ nhị phân (hay quan hệ hai ngôi) giữa các phần tử của P thỏa mãn 3 tính chất 1. x ĺ y và y ĺ z suy ra x ĺ z, với mọi x, y, z P P (tính bắc cầu – transitive) 2. x ĺ x, @x P P (tính phản xạ – reflexive) 3. x ĺ y và y ĺ x suy ra x = y (tính phản xứng – antisymmet ric) Ví dụ 2.1. P = Bn là tập tất cả các tập con của [n] và quan hệ nhị phân là Ď, nghĩa là X ĺ Y nếu và chỉ nếu X Ď Y. Cái poset này gọi là đại số Bool (Boolean algebra). Xem ví dụ trên Hình 5.1. 43 Toán yêu người những đồng cộng của online chí Tạp t1, 2, 3u t1, 2u t1, 3u t2, 3u t1u t2u t3u H Hình 5.1: Đại số Bool B3 Ví dụ 2.2. P = Dn là tập tất cả các ước số dương của n, quan hệ nhị phân là quan hệ “chia hết”, nghĩa là i ĺ j nếu và chỉ nếu i|j. Ký hiệu i|j nghĩa là j chia hết cho i (hay i chia hết j). Xem ví dụ trên Hình 5.2. 60 12 20 30 4 6 10 15 2 3 5 1 Hình 5.2: Poset các ước số của 60 Ví dụ 2.3. P là tập tất cả các “mặt” (faces) của một đa điện (polytope) trong không gian n chiều; và x ĺ y nếu mặt x chứa trong mặt y. Mặt rỗng cũng là một mặt với chiều ´1, và toàn 44 Toán yêu bộ đa diện là một mặt với số chiều bằng n. Poset này còn gọi là face lattice của polytope. Xem ví dụ trên Hình 5.2. abcde e eab ecb ead ecd abcd người những b a c d ea ad ab eb ec ed cb cd a e c d b H đồng cộng của online Hình 5.3: Face lattice của hình Pyramid 2.2. Hàm Mobius của poset ¨ Những điều ta viết sau đây đúng cho một trường K tùy hỉ và các posets vô hạn (miễn là nó hữu hạn địa phương1). Để cho đơn giản, ta phát biểu các kết quả với K = C và các posets hữu hạn thôi. Gọi (P, ĺ) là một poset hữu hạn. Ta xét các ma trận α kích thước |P| ˆ |P| sao cho α(x, y) = 0 nếu x ł y. Khi x ĺ y thì α(x, y) P C tùy hỉ. Tập các ma trận này gọi là đại số kề (incidence algebra) của P, ký hiệu là I(P). Trong đại số kề thì ma trận δ định nghĩa chí bằng δ(x, y) = là ma trận đơn vị. # 1 x = y 0 x ‰ y Định lý 2.4. Cho trước poset (P, ĺ) trong đó P hữu hạn. Xét một ma trận α P I(P) tùy ý thì α khả nghịch nếu và chỉ nếu α(x, x) ‰ Tạp 0, @x P P. 1Nghĩa là số các thành viên nằm giữa một cặp x và y là hữu hạn với mọi cặp x, y. 45 Toán yêu người Chứng minh. Nếu ta vẽ “đồ thị" của P bằng cách xem P như tập các đỉnh và vẽ một mũi tên từ x đến y nếu x ĺ y (như trong Hình 5.1 và 5.2) thì ta có một đồ thị có hướng nhưng không có vòng tròn (directed acyclic graph). Do đó, tồn tại một cách liệt kê tất cả các phần tử của P từ trái sang phải sao cho tất cả các mũi tên đều trỏ sang phải hoặc trỏ vào chính nó (loop trong đồ thị). Thứ tự này gọi là trật tự tô-pô (topological ordering) của đồ thị, là một bài tập cơ bản khi học các thuật toán duyệt đồ thị. Nếu ta viết các ma trận α P I(P) mà các hàng và cột đánh chỉ số theo thứ tự này thì ta có các ma trận tam giác trên (upper triangular). Do đó α khả nghịch nếu và chỉ nếu α(x, x) ‰ 0, @x, nghĩa là các phần tử trên đường chéo khác không. Lưu ý rằng ma trận nghịch đảo cũng là ma trận tam giác trên, và do đó những cũng thuộc về đại số kề. Một thành viên quan trọng của đại số kề I(P) là ma trận ζ, gọi là hàm zeta của P, định nghĩa bằng # đồng ζ(x, y) = 1 x ĺ y 0 x ł y cộng của Định nghĩa 2.5 (Hàm Mobius của một poset) ¨ . Hàm Mobius ¨ của poset (P, ĺ), ký hiệu là µ, chính là ma trận nghịch đảo của hàm zeta ζ. (Theo Định lý 2.4 thì ζ khả nghịch.) Kế đến ta mô tả một công thức đệ quy để tính hàm Mobius của ¨ một poset. Từ định nghĩa của phép nhân ma trận, với α, β P I(P) bất kỳ ta có online (αβ)(x, y) = ÿ zPP α(x, z)β(z, y) = ÿ xĺzĺy α(x, z)β(z, y), tại vì nếu x ł z thì α(x, z) = 0, còn nếu z ł y thì β(z, y) = 0. Do đó, từ µζ = δ ta suy ra chí δ(x, y) = ÿ xĺzĺy µ(x, z)ζ(z, y) = ÿ xĺzĺy µ(x, z). Tạp Hay viết cụ thể hơn thì với mọi x, y P P ta có ÿ xĺzĺy µ(x, y) = # 1 nếu x = y 0 nếu x ‰ y.(5.1) 46 Đẳng thức (5.1) suy ra công thức quy nạp để tính µ(x, y): Toán µ(x, y) = $’& ’% 1 x = y ´řxĺzăy µ(x, z) x ă y 0 x ł y yêu Từ công thức này ta suy ra giá trị hàm Mobius cho ba posets ở ¨ trên. Hai đẳng thức đầu thì dễ (làm bài tập), cái thứ ba thì khó. người 1. Nếu P = Bn là tập tất cả các tập con của [n] (đại số Bool), thì µ(A, B) = # (´1)|B|´|A| A Ď B 0 A Ę B những 2. Nếu P = Dn là tập tất cả các ước số của n, thì # µ(x, y) = (´1)r nếu y/x là tích của r số nguyên tố khác nhau 0 nếu không phải thế. đồng 3. Nếu P là face-lattice của một đa điện n chiều thì # (´1)dim(B)´dim(A)if A Ď B cộng µ(A, B) = 0 nếu không. (5.2) của online chí Tạp 2.3. Nghịch đảo Mobius ¨ Xét hai hàm số f, g : P Ñ C bất kỳ. Ta có thể xem chúng như hai vectors trong không gian C|P|. Công thức nghịch đảo Mobius ¨ trên poset nói hai điều rất đơn giản: f = ζg ô g = µf, (5.3) và, xoay ngang các vectors ra thì f = gζ ô g = fµ. (5.4) Để hiểu ý nghĩa tổ hợp của sự tương đương này, ta viết rõ ràng hơn một chút vì ta biết ζ(x, y) và µ(x, y) bằng 0 nếu x ł y. Quan hệ (5.3) nói rằng: f(x) = ÿ xĺy g(y), @x P P ô g(x) = ÿ xĺy 47 µ(x, y)f(y), @y P P. (5.5) Toán Đẳng thức này ta hiểu như sau. Giả sử ta có hàm g gán một con số g(y) vào mỗi thành viên y P P, và f gán vào mỗi x P P một con số là tổng của các g(y) sao cho x ĺ y, thì vế phải của (5.3) cho ta cách tính g dựa trên f. Đối ngẫu lại, quan hệ (5.4) nói rằng: yêu f(x) = ÿ xľy g(y), @x P P ô g(x) = ÿ xľy µ(y, x)f(y), @y P P. (5.6) người Ví dụ 2.6. Để có công thức Euler-Poincaré, ta áp dụng (5.5) trong đó g(y) = 1 với y = P và g(y) = 0 với mọi y còn lại trong P. Khi đó, rõ ràng là tất cả các f(x) đều bằng 1. Dùng (5.2), ta có những 0 = g(H) = ÿ mặt B (´1)dim(B)´dim(H)f(B) = ÿ mặt B (´1)dim(B)+1 = ´ÿn i=´1 (´1)iFi. đồng cộng Ví dụ 2.7. Áp dụng (5.6) cho poset P = Dn, ta có ngay công thức nghịch đảo Mobius cổ điển trong lý thuyết số ở trên. ¨ Ví dụ 2.8. Còn công thức inclusion-exclusion thì sao? Cách hiểu sau đây sẽ hữu dụng trong nhiều trường hợp. Giả sử ta có một tập “bi ve" U = A1 Y ¨ ¨ ¨ Y An. Mỗi viên bi có nhiều màu. Các màu được đánh số từ 1 đến n. Gọi Ai là tập các viên bi có màu i. Với X Ď [n] tùy ý, gọi g(X) là tập tất cả các viên bi chỉ có đúng các màu trong X mà thôi. Khi đó, của f(X) = ÿ XĎY g(Y) online chính là số các viên bi mà mỗi viên có ít nhất các màu trong X, và f(H) = |U|. Do đó, f(X) = ˇˇˇˇˇč iPX Ai ˇˇˇˇˇ. chí Áp dụng (5.5) cho poset P = Bn ta kết luận Tạp 0 = g(H) = ÿ YĎ[n] (´1)|Y| ˇˇˇˇˇč iPY Ai ˇˇˇˇˇ. Chuyển f(H) = |U| sang một vế là ta có công thức inclusion exclusion. 48 Toán yêu người những 3. Bổ đề Sauer–Shelah Chúng ta tự thưởng công bằng cách chứng minh một bổ đề tổ hợp quan trọng gọi là bổ đề Sauer-Shelah [7, 8]. Bổ đề này có ứng dụng sâu sắc trong lý thuyết học máy, cụ thể là lý thuyết “chiều Vapnik-Chervonenkis” (VC dimension) [13, 12]. Gọi F là một bộ các tập con của [n]. Với S Ď [n] bất kỳ, định nghĩa “hình chiếu” của F lên S là tập ΠF(S) = tF X S | F P Fu. Ta nói F “băm nát” S nếu ΠF(S) = 2|S|. Bổ đề 3.1 (Bổ đề Sauer-Shelah). Cho trước F là một bộ các tập con của [n]. Gọi d là kích thước lớn nhất của một tập S Ď [n] bị F đồng băm nát, thì |F| ď Φd(n) = ÿd i=0 n i . Chứng minh. Ta chứng minh bổ đề này bằng “phương pháp chiều” (Đại Số tuyến tính van tuế!). Gọi [n] ďd là tập tất cả các tập con của [n] với kích thước bé hơn hoặc bằng d. Với mỗi F P F, cộng định nghĩa một hàm số hF :[n] ďd Ñ R như sau: của hF(X) = # 1 X Ď F 0 X Ę F. Các hàm hF là các vectors trong không gian RΦd(n). Có tất cả |F| vectors hF, do đó nếu chúng độc lập tuyến tính thì |F| ď Φd(n). online Giả sử chúng không độc lập tuyến tính, nghĩa là tồn tại các hệ số αF sao choÿ FPF αFhF = 0 (5.7) và các hệ số này không cùng bằng 0. Để cho tiện, ta mở rộng chí định nghĩa và gán αX = 0 với mọi X P 2[n]zF. Từ (5.7), với X P[n] ďd bất kỳ ta có řFPF αFhF(X) = 0, hay nói tùy ý ta có řXĎY αY = 0. Định nghĩa Tạp cách khác với X P[n] ďd . βX =řXĎY g(Y), thì ta vừa thấy rằng βX = 0, @X P[n] ďd Gọi Y là tập con nhỏ nhất của [n] sao cho βY ‰ 0. (Nếu ta lấy tập F P F có kích thước lớn nhất sao cho αF ‰ 0 thì αF = βF ‰ 0, do 49 Toán đó tồn tại tập Y nhỏ nhất như định nghĩa.) Dĩ nhiên |Y| ě d + 1. Ta chứng minh rằng Y bị F băm nát, từ đó dẫn đến điều vô lý. Để chứng minh Y bị băm nát thì ta cần chứng minh, với Z Ď Y tùy ý, tồn tại F P F sao cho F X Y = Z. Để chứng minh điều này thì chỉ cần chứng minh yêu ÿ AĎ[n],AXY=Z αA ‰ 0. người là xong, tại vì αA = 0, @A R F. Đến đây ta xét poset Bm gồm tất cả các tập con của Y ´ Z (đặt m = |Y ´ Z|). Poset này là đại số Bool bậc m. Với mỗi phần tử W Ď Y ´ Z, định nghĩa những g(W) = ÿ X:XXY=ZYW Và định nghĩa, với mọi V Ď Y ´ Z, αX. đồng f(V) = ÿ VĎWĎY´Z g(W). (Lưu ý rằng ta sẽ dùng dạng (5.5) của nghịch đảo Mobius.) Dễ ¨ thấy rằng cộng f(V) = βZYV, @V P Bm. Do Y là tập nhỏ nhất với βY = 0, ta có f(V) = 0, @V ‰ Y ´ Z, và f(Y ´ Z) = βY ‰ 0. Theo nghịch đảo Mobius ta có ¨ của online ÿ AĎ[n],AXY=Z αA = g(H) = ÿ VĂY´Z (´1)|V|f(V) = (´1)|Y´Z|βY ‰ 0. 4. Chú thích chí Bộ sách của Stanley [10, 9] là tham khảo quan trọng nhất cho toán tổ hợp đếm bao gồm nghịch đảo Mobius, tổ hợp tô-pô. Sách ¨ của Vapnik [12] nói về lý thuyết học máy xác suất và lý thuyết Tạp chiều Vapnik-Chervonenkis. Một tham khảo tuyệt vời khác cho toán Tổ hợp là quyển sách của van Lint và Wilson [11]. Trong ngành máy tính, nghịch đảo Mobius có ứng dụng trong cơ sở ¨ dữ liệu [2], thuật toán [3, 1]. 50 Toán yêu người những đồng cộng của online chí Tạp Tài liệu tham khảo [1] BJORKLUND ¨ , A., HUSFELDT, T., KASKI, P., AND KOIVISTO, M. Trimmed moebius inversion and graphs of bounded degree. Theory Comput. Syst. 47, 3 (2010), 637–654. [2] DALVI, N. N., AND SUCIU, D. The dichotomy of probabilistic inference for unions of conjunctive queries. J. ACM 59, 6 (2012), 30. [3] NEDERLOF, J. Fast polynomial-space algorithms using mobius inversion: Improving on steiner tree and related ¨ problems. In Automata, Languages and Programming, 36th International Colloquium, ICALP 2009, Rhodes, Greece, July 5-12, 2009, Proceedings, Part I (2009), S. Albers, A. Marchetti-Spaccamela, Y. Matias, S. E. Nikoletseas, and W. Thomas, Eds., vol. 5555 of Lecture Notes in Computer Science, Springer, pp. 713–725. [4] POINCARÉ, H. Sur la généralisation d’un théorème d’Euler relatif aux polyèdres. Comptes rendus hebdomadaires de l’Académie des sciences de Paris 117 (1893), 144–145. [5] ROTA, G.-C. On the foundations of combinatorial theory. I. Theory of Mobius functions. ¨ Z. Wahrscheinlichkeitstheorie und Verw. Gebiete 2 (1964), 340–368 (1964). [6] ROTA, G. C., AND PALOMBI, F. Indiscrete thoughts. Birkhauser, 1996. [7] SAUER, N. On the density of families of sets. J. Combinato rial Theory Ser. A 13 (1972), 145–147. [8] SHELAH, S. A combinatorial problem; stability and order for models and theories in infinitary languages. Pacific J. Math. 41 (1972), 247–261. [9] STANLEY, R. P. Enumerative combinatorics. Vol. 2, vol. 62 of Cambridge Studies in Advanced Mathematics. Cambridge University Press, Cambridge, 1999. With a foreword by Gian-Carlo Rota and appendix 1 by Sergey Fomin. 51 Toán yêu người những đồng cộng của online chí Tạp [10] STANLEY, R. P. Enumerative combinatorics. Volume 1, sec ond ed., vol. 49 of Cambridge Studies in Advanced Mathe matics. Cambridge University Press, Cambridge, 2012. [11] VAN LINT, J. H., AND WILSON, R. M. A course in combina torics, second ed. Cambridge University Press, Cambridge, 2001. [12] VAPNIK, V. N. The Nature of Statistical Learning Theory. Springer-Verlag New York, Inc., New York, NY, USA, 1995. [13] VAPNIK, V. N., AND CHERVONENKIS, A. Y. Theory of uniform convergence of frequencies of events to their probabilities and problems of search for an optimal solution from em pirical data. Avtomat. i Telemeh., 2 (1971), 42–53. 52 Tạp chí online của những người yêu Toán cộng đồng ToánCÁC BÀI TOÁN ĐỘI NÓN yêu người những đồng Đặng Nguyễn Đức Tiến (Đại học Trento, Italy) Trong số 1 của Epsilon, chúng tôi đã giới thiệu với độc giả 15 bài toán đội nón được sưu tập trong hơn 50 năm (từ 1961 đến 2013), phân bố ở những mức độ khó và thể loại khác nhau. Để tiếp tục cuộc hành trình, trong chuyên mục phần này chúng tôi chọn lọc và trình bày những lời giải đẹp cho các bài toán đã được trình bày. Chúng tôi cũng giới thiệu với độc giả những lời giải tổng quát cũng như những ứng dụng thực tế cho các vấn đề từ những bài toán giải trí này. 1. Bài toán 3 chiếc nón cộng của online chí Tạp Để bắt đầu cuộc hành trình, chúng tôi mời quý độc giả cùng quay lại nhóm 3 bài toán đội nón số 4, số 5, và số 6. Chúng ta bắt đầu bởi bài toán số đội nón số 4 trước. Theo luật chơi, ta có thể thấy rằng nếu như cả 3 đều chọn ‘bỏ qua’ thì họ sẽ thua trong mọi tình huống, vì vậy, trong các cách trả lời dễ thấy phải có ít nhất một người gọi lên màu nón. Xét trường hợp nếu cả 3 người chơi đều cùng chọn một màu, hoặc cùng chọn ngẫu nhiên mà không ‘bỏ qua’ thì xác suất để cả 3 cùng thắng là 1/8, tức 12.5% vì có tất cả 8 khả năng khác nhau cho 3 người. Một Nhắc lại đề: Có 3 người chơi, mỗi người được đội ngẫu nhiên một nón có màu đỏ hoặc xanh dương. Họ nhìn thấy màu nón của 2 bạn mình nhưng không biết màu của mình. Mỗi người cần phải đoán ra màu nón của mình, hoặc chọn bỏ qua nếu không đoán được. Nếu ít nhất một người đoán đúng màu nón và những người còn lại không đoán sai, họ thắng trò chơi. Họ sẽ thua nếu có người đoán sai hoặc cả 3 cùng chọn bỏ qua. Họ được trao đổi chiến thuật với nhau trước khi chơi nhưng trong khi tham gia thì không được trao đổi bất cứ thông tin gì. Tìm chiến thuật có xác suất thắng cao nhất. chiến thuật tốt hơn có thể dễ dàng được tìm thấy là 1 người chọn ngẫu nhiên, và 2 người chọn bỏ qua. Lúc này ta có xác 53 Toán yêu người những đồng cộng của online chí Tạp suất thắng là 1/2 = 50%. Liệu đây có phải là chiến thuật tốt nhất? Như gợi ý của bài toán đội nón số 6, chiến thuật này chưa phải là chiến thuật tốt nhất. Lời giải sau cho ra xác suất thắng lợi cao hơn: nếu một người thấy 2 người đội nón khác màu nhau, họ sẽ chọn “bỏ qua" và nếu thấy 2 người đội nón trùng màu nhau, sẽ chọn màu ngược lại. Với cách này, họ sẽ luôn đoán đúng 6/8 trường hợp và chỉ sai trong 2/8 trường hợp khi cả 3 nón cùng màu nhau (xem ví dụ ở Hình 6.1). Hình 6.1: Mỗi người nếu thấy 2 nón khác màu sẽ chọn ’bỏ qua’ và nếu thấy 2 nón cùng màu, sẽ chọn màu ngược lại. Trong ví dụ này, người đội nón đỏ sẽ đoán màu đỏ (do thấy 2 nón xanh) và 2 người đội nón xanh sẽ chọn bỏ qua (do họ thấy 2 nón khác màu nhau). Lời giải này cho khả năng thắng lợi là 6/8 = 75% nếu như nón được đội thật sự là ngẫu nhiên. Tuy nhiên, trong thực tế (như mô tả trong bài toán đội nón số 6), người dẫn trò sẽ nhanh chóng nhận ra chiến thuật của họ và sẽ đội nón cho họ cùng màu nhau với tần suất nhiều hơn, hoặc thậm chí luôn luôn đội cùng màu. Khi đó khả năng chiến thắng từ 75% sẽ giảm xuống thành 0%! Vậy người chơi phải đối phó thế nào với người dẫn trò “xảo quyệt”? Một đối sách có thể nghĩ ra cho chiến thuật chơi dài hạn là khi người quản trò đổi qua đội nón cùng màu, khi thấy 2 nón giống màu nhau, họ sẽ chọn màu đó. Như vậy với trường hợp này họ sẽ thắng 100%. Và tất nhiên, người quản trò lại học được cách này và quay lại phân bố với 6 trường hợp kia hoặc quay lại với phân bố ngẫu nhiên nón. Xác suất chiến thắng khi đó sẽ thay đổi 75% —> 0% —> 100% —> 75% —> ... lặp đi lặp lại như một 54 Toán yêu người những cuộc chiến giữa những người chơi và người dẫn trò. Trung bình chiến thắng do vậy là 58%. Liệu có cách làm tốt hơn 58% để đối phó với người dẫn trò xảo quyệt? Rất thú vị là chúng ta có thể nâng cấp chiến thuật cũ để bảo toàn khả năng chiến thắng 75%. Chiến thuật này như sau: Chúng ta có 8 cách đội nón khác nhau và các cách này có thể ghép thành từng cặp “đối xứng" nhau, đỏ đối với xanh. Ví dụ 3 nón đỏ-đỏ-đỏ ĐĐĐ, sẽ đối với 3 nón xanh-xanh-xanh XXX, hoặc ĐXĐ sẽ đối với XĐX. Tưởng tượng trên một hình lập phương với tọa độ các đỉnh tương ứng lần lượt với các cách đội nón, và 2 đỉnh nối với nhau khi chỉ có 1 nón khác màu nhau. Các cấu hình đội nón “đối xứng" chính là các đỉnh đối xứng nhau trên hình lập phương này. đồng cộng ĐĐX ĐĐĐ ĐXX ĐXĐ XĐX XĐĐ XXX XXĐ ĐĐX ĐĐĐ ĐXX ĐXĐ XĐX XĐĐ XXX XXĐ của Chiến thuật chọn hi sinh cặp đỉnh đồng màu. Chiến thuật chọn hi sinh 2 đỉnh XĐX và ĐXĐ. Hình 6.2: Chiến thuật đối phó với người dẫn trò “xảo quyệt". online Với cách thể hiện này, nhiệm vụ của người chơi là xác định nhóm mình ở đỉnh nào trên hình lập phương! Với mỗi người chơi, khi thấy được 2 màu nón của người chơi đối diện, người này sẽ xác định được mình đang ở cạnh nào và nhiệm vụ là hoặc bỏ qua, hoặc đoán xem mình ở đỉnh nào. Với cấu hình chí này, nếu chấp nhận “hi sinh" một cặp đỉnh đối xứng bất kỳ, ta sẽ luôn xác định được đỉnh cần tìm bằng cách luôn trả lời hướng về các đỉnh màu xanh khi tình trạng đang ở một cạnh Tạp nối giữa đỉnh “xanh" và đỉnh “xám", ngược lại sẽ chọn bỏ qua. Chiến thuật này chỉ sai khi nhóm người chơi có đỉnh rơi vào cặp đỉnh đã được chọn “hi sinh", lúc đó cả 3 người đều là 3 cạnh nối ra từ các đỉnh “xám" này. Như vậy, cách chơi theo chiến 55 Toán yêu người những đồng cộng của online chí Tạp thuật ở câu hỏi 1 là chọn cặp đỉnh XXX và ĐĐĐ và có thể dễ dàng bị “bắt bài" bởi người dẫn trò chơi (Hình 6.2). Nhưng ta có thể chọn các cặp đỉnh như (XĐX và ĐXĐ), hay (XXĐ và ĐĐX)... và đều có xác suất thắng lợi là 75% cho trường hợp đội nón ngẫu nhiên. Lúc này, người dẫn chương trình không thể "bắt bài" vì nhóm người chơi luôn linh động thay đổi được cặp đỉnh “hi sinh" ngầm định, và buộc người dẫn trò phải đội nón một cách ngẫu nhiên cho họ, và chiến thắng đến với xác suất 75%! Một chiến thuật ví dụ cho trường hợp nếu chọn cặp XĐX và ĐXĐ (xem Hình 6.2 bên phải) như sau: • Người 1: nếu gặp xanh - đỏ sẽ chọn xanh, điều này tương ứng với cạnh ĐXĐ - XXĐ (màu đỏ trên hình), và vì cặp đỉnh “hi sinh” có chứa ĐXĐ nên ta chọn xanh. Nếu gặp đỏ - xanh sẽ chọn đỏ, điều này tương ứng với cạnh màu xanh lá cây trên hình. Người 1 chọn bỏ qua nếu thấy 2 nón cùng màu (vì các cạnh này nối các đỉnh không thuộc tập “hi sinh"). • Người 2: nếu gặp nón cùng màu, sẽ chọn màu đó, ngược lại sẽ chọn bỏ qua. • Người 3: nếu gặp xanh - đỏ sẽ chọn đỏ; nếu gặp đỏ - xanh sẽ chọn xanh, và bỏ qua nếu cùng màu. Xét cụ thể 8 cách đội nón có thể có, ta có kết quả như sau: Nón 1 Nón 2 Nón 3 Đoán 1 Đoán 2 Đoán 3 Kết quả Xanh Xanh Xanh Bỏ qua Xanh Bỏ qua Đúng Xanh Xanh Đỏ Xanh Bỏ qua Bỏ qua Đúng Xanh Đỏ Xanh Đỏ Xanh Đỏ Sai Xanh Đỏ Đỏ Bỏ qua Bỏ qua Đỏ Đúng Đỏ Xanh Xanh Bỏ qua Bỏ qua Xanh Đúng Đỏ Xanh Đỏ Xanh Đỏ Xanh Sai Đỏ Đỏ Xanh Đỏ Bỏ qua Bỏ qua Đúng Đỏ Đỏ Đỏ Bỏ qua Đỏ Bỏ qua Đúng Với 2 trường hợp còn lại (XXĐ - ĐĐX và XĐĐ - ĐXX) cũng không khó để tìm ra chiến thuật tương tự với khả năng thắng 6/8. Như vậy, với cách làm ngẫu nhiên chọn cặp đỉnh "hi sinh" người chơi đã buộc người dẫn trò phải đội nón ngẫu nhiên, và do vậy, xác suất thắng lợi bảo toàn với tỉ lệ 75%. 56 Toán yêu người những đồng cộng của online chí Tạp Tổng quát hóa cho 2n ´ 1 người chơi Tiếp theo, chúng tôi xin mời độc giả cùng xem lời giải mở rộng cho bài toán với trường hợp N = 2n ´ 1 người chơi, và đây cũng chính là câu trả lời cho bài toán đội nón số 5 khi thay n = 4. Lưu ý rằng hiện nay lời giải đẹp chỉ mới được tìm thấy ở trường hợp tổng quát nhưng đặc biệt này, tức N = 2n ´1. Với các trường hợp khác, lời giải vẫn còn đang bỏ ngõ. Chúng tôi sẽ trình bày cách làm cụ thể cho trường hợp này và sau đó sẽ liên kết cách làm này với mã Hamming, một mã sửa lỗi tuyến tính nổi tiếng và được sử dụng rộng rãi trong viễn thông. Cách làm như sau: gán thứ tự cho người chơi từ 1 đến N, và đổi các số này sang nhị phân. Chúng ta sẽ sử dụng phép sánh khác (XOR)1trên các chuỗi nhị phân này. Đặc tính quan trọng của phép XOR là với số k bất kỳ, k ‘ k = 0, bởi vì k khớp với chính nó trên mọi bit. Gọi T là tổng (XOR) của tất cả người chơi có nón màu đỏ. Chiến thuật của người chơi là đoán sao cho T khác 0 và khi đó, họ sẽ thắng nếu T thật sự khác 0 (tất nhiên, họ sẽ sai khi T = 0). Cụ thể chiến thuật như sau: Gọi tk là tổng XOR các người đội nón đỏ mà người thứ k thấy được. • Nếu tk = 0, anh ta sẽ đoán “đỏ" (vì nếu anh ta đoán xanh, T sẽ không cập nhật và sẽ bằng 0). • Nếu tk = k, anh ta sẽ đoán “xanh” (vì nếu anh ta đoán đỏ thì T = tk ‘ k = k ‘ k = 0). • Ngược lại, nếu tk ‰ 0 và tk ‰ k, anh ta chọn bỏ qua. Lúc này như ta thấy, nếu T thật sự bằng 0, tất cả đều sẽ đoán sai. Nếu T = k ‰ 0, người thứ k sẽ đoán đúng và tất cả những người khác đều chọn bỏ qua, nên họ sẽ chiến thắng. Vì T có giá trị từ 0 đến N nên xác suất thắng lợi là N/(N + 1). Liệu chiến thuật này có thể nâng cấp lên để đối phó với người dẫn trò “xảo quyệt"? Câu trả lời là có với cách làm tương tự như phần trình bày ở trên. 1Phép sánh khác (thuật ngữ tiếng Anh là “Exclusive OR", hay còn gọi là phép OR có loại trừ, và cũng còn gọi là tổng NIM), ký hiệu là ‘, thực hiện "cộng" 2 chuỗi nhị phân bằng cách so sánh các bit từ phải sang trái. Ứng với mỗi cặp bit sẽ cho kết quả là 1 nếu 2 bit này khác nhau và kết quả là 0 nếu 2 bit này giống nhau. Ví dụ: 0110010 ‘ 1010111 = 1100101. 57 ToánMà HAMMING VÀ BÀI TOÁN ĐỘI NÓN SỐ 5 Giả sử tôi muốn gửi một thông điệp cho bạn và thông điệp này được mã hóa thành các bit nhị phân (ký số 0 hoặc 1). yêu người những đồng cộng của online chí Tạp Tuy nhiên ở giữa đường truyền có kẻ can thiệp, và thay đổi một bit nào đó trước khi bạn nhận được thông điệp. Vì vậy, tôi phải tìm ra cách thêm vào một số thông tin bổ sung cho thông điệp sao cho khi nhận được, bạn có thể phát hiện thông điệp đã bị thay đổi và hơn nữa, bạn có thể khôi phục lại thông điệp gốc. Một trong những phương pháp cơ bản để phòng chống việc sửa đổi này là sử dụng “mã tái diễn”: tôi sẽ gửi một lần 3 bit giống nhau cho cùng 1 bit mà tôi muốn gửi cho bạn: 000 hoặc 111. Lúc này, dù kẻ can thiệp có thay đổi bất kỳ bit nào, tôi cũng sẽ khôi phục lại được. Cách làm này tuy đạt mục đích, nhưng hiệu quả không cao, vì nội dung thừa chiếm đến 2 lần nội dung thông tin cần gửi. Mã Hamminga đưa ra cách tốt hơn cho việc sửa lỗi này, trong đó cứ 2k–1 bit thông tin gửi đi chỉ có k bit bổ sung, còn lại 2k–k–1 bit là dữ liệu. Ví dụ với k = 4, khi gửi một thông điệp có chiều dài 15 bit thì trong đó 11 bit là dữ liệu (so với chỉ 5 bit là dữ liệu ở phương pháp sử dụng mã tái diễn). Chi tiết cách hoạt động của mã Hamming độc giả có thể dễ dàng tìm thấy tại Wikipedia. Ở đây, chúng tôi chỉ chỉ ra mối quan hệ giữa Hamming và bài toán đội nón số 5. Một đặc tính đáng chú ý của mã Hamming là bất kỳ chuỗi (có chiều dài 2k ´ 1) nào cũng hoặc là một thông điệp đúng, hoặc chỉ bị sai ở một bit. Điều này khác biệt với mã tái diễn vì ở mã tái diễn có một số thông điệp sẽ không bao giờ xuất hiện. Ví dụ, bạn sẽ không bao giờ nhận được mã 001011 vì ở đây có đến 2 bit bị thay đổi. Ở mã Hamming, mọi chuỗi đều có khả năng xuất hiện. Bây giờ, giả sử ta mã hóa những người đội nón xanh là 0 và nón đỏ là 1, khi đó một cách đội nón cho N người trở thành một "thông điệp" N bit. Lúc này, mỗi người sẽ có thể thấy toàn bộ những bit khác, trừ bit của anh ta, và tất nhiên chỉ có 2 khả năng hoặc anh ta là bit 0 (xanh), hoặc là bit 1 (đỏ). Người chơi sẽ dùng chiến thuật là luôn giả định chuỗi N bit 58 Toán yêu người những đồng cộng của online chí Tạp hiện tại KHÔNG PHẢI là một "thông điệp" đúng. Cụ thể: nếu một người chơi thấy rằng nếu bit tương ứng với anh ta có giá trị 0 sẽ biến chuỗi thành một thông điệp đúng, anh ta sẽ chọn "đỏ" (ứng với bit 1), và ngược lại. Nếu anh ta thấy rằng cả 0 và 1 đều có thể làm thành một "thông điệp" đúng, anh ta chọn bỏ qua. Chiến thuật này chỉ gặp thất bại khi "thông điệp" ban đầu đúng và thành công nếu "thông điệp" sai. Vì cứ mỗi thông điệp đúng sẽ có tương ứng N thông điệp sai, nên xác suất thắng lợi là N/(N + 1), tương tự như chiến thuật đã nêu ở bài toán đội nón số 5. aMã Hamming được đặt theo tên của nhà toán học người Mỹ, Richard Wesley Hamming (1915 - 1998). 2. Các bài toán của Konstantin Knop Chúng tôi mời độc giả tiếp tục đi đến phần lời giải của 2 bài toán tuyệt đẹp do Konstantin Knop đề xuất: bài toán đội nón số 7 và bài toán đội nón số 9. Như đã đề cập đến ở Epsilon số 1, đây là nhóm các bài toán mà người chơi xếp thành hàng nên số lượng nón mà người chơi quan sát được gặp giới hạn. Điều này không xảy ra ở nhóm bài toán đội nón ở trên là mỗi người chơi đều thấy được nón của mọi người chơi khác (trừ nón của mình). Tuy nhiên, ở nhóm bài toán trước, người chơi không biết được những người khác sẽ đoán màu gì, còn ở nhóm bài toán này, thứ tự nêu lên màu nón cũng thuộc về chiến thuật chơi. Để tiện theo dõi, chúng tôi nhắc lại đề của bài toán đội nón số 7 cho trường hợp 3 màu: Có 100 người được xếp thành một hàng, mỗi người được đội một nón chọn ngẫu nhiên trong 3 màu cho trước. Mỗi người chỉ nhìn thấy màu nón của những người đứng trước mình mà không thấy nón của mình và những người đứng sau. Lần lượt mỗi người sẽ phải đoán màu nón của mình và hô to cho những người khác nghe. Người đứng cuối cùng (là người thấy màu nón của toàn bộ 99 người trước) là người bắt đầu phải đoán. Người chơi không được trao đổi bất kỳ thông tin gì với nhau ngoại trừ lắng nghe màu nón từ người đoán trước. Đúng sai cũng chỉ được biết khi người cuối cùng đã đoán xong. Hãy tìm chiến chuật sao cho số người đoán sai là ít nhất. 59 Toán yêu người những đồng cộng của online chí Tạp Ở đây, sau khi đã quen thuộc với nhóm bài toán ở phần 1, ta thấy đây cũng là một dạng mã sửa sai. Cụ thể trong bài toán này, chiến thuật sử dụng modulo được áp dụng. Chúng tôi trình bày ở đây chiến thuật tổng quát cho bài toán với M người chơi và N màu nón, chiến thuật như sau: • Gán mỗi màu tương ứng với một con số từ 0 đến N ´ 1. • Người đầu tiên tính tổng tất cả những màu nón mà anh ta quan sát được, lấy modulo theo N và hô màu nón tương ứng. • Những người tiếp theo, căn cứ vào lời hô của những người trước đó, và tổng của những người đứng trước mình sẽ đoán đúng màu nón của mình. Như vậy, cách làm này chỉ có người đầu tiên là có khả năng đoán sai, và vì có N màu khác nhau, nên khả năng tất cả mọi người đều đoán đúng chỉ phụ thuộc vào khả năng người đầu đoán đúng, và khả năng này là 1/N. Hãy thử xét một ví dụ đơn giản với 5 người chơi, 3 màu nón và mỗi người lần lượt đội các nón là (1, 2, 0, 2, 1): • Người đầu tiên, quan sát được trước mình có các nón (2, 0, 2, 1), có tổng bằng 2 + 0 + 2 + 1 ” 2 (mod 3), người này sẽ hô mình có màu 2 (và sai). • Người tiếp theo, quan sát thấy trước mình có (0, 2, 1) và căn cứ vào lời đoán của người trước đó 2, nên sẽ đoán là 2 ´ 0 ´ 2 ´ 1 ” 2 (mod 3) (đúng). • Người thứ 3, quan sát thấy (2, 1) và căn cứ vào lời đoán của 2 người trước (2, 2), nên đoán là 2´2´2´1 ” 0 (mod 3) (đúng). • Người thứ 4, quan sát thấy (1) và căn cứ vào lời đoán của 3 người trước (2, 2, 0), nên đoán là 2 ´ 2 ´ 0 ´ 1 ” 2 (mod 3) (đúng). • Người cuối cùng, căn cứ vào lời đoán của 4 người trước (2, 2, 0, 2), nên đoán là 2 ´ 2 ´ 0 ´ 2 ” 1 (mod 3) (đúng). Kết quả là 4 người sau đều luôn luôn đoán đúng và người đầu tiên xác suất đúng là 1/3. Tiếp theo, chúng tôi trình bày lời giải cho bài toán đội nón số 9. Để tiện theo dõi, chúng tôi nêu lại đề ở đây. 60 Toán yêu người những đồng cộng của online chí Tạp Có 100 người xếp thành hàng, mỗi người được đội một nón trong số 101 nón khác màu nhau. Mỗi người chỉ thấy nón của những người đứng trước mình và không thấy nón của mình cũng như những người đứng sau. Lần lượt mỗi người từ sau ra trước phải đoán màu nón của mình và hô to cho mọi người cùng nghe. Màu nào đã hô rồi sẽ không được hô lại nữa. Người chơi không được trao đổi thông tin với nhau. Tìm chiến thuật sao cho khả năng tất cả đều đoán đúng là cao nhất. Thoạt nhìn, 2 bài toán này khá giống nhau, nhưng khi thật sự giải chúng ta sẽ thấy đây là một bài khác, và mỗi bài có vẻ đẹp riêng biệt. Trước khi đi vào phân tích lời giải cho bài này, chúng tôi xin nhắc lại hai khác biệt cơ bản giữa bài toán đội nón số 9 so với bài toán số 7: • N người chơi, mỗi người đội một nón trong số N + 1 nón khác màu nhau. Điều này có nghĩa là màu nón mỗi người đều khác nhau. Ở bài số 7, ta không có ràng buộc giữa số người chơi và số màu nón, hơn nữa họ có thể đội nón giống màu nhau. • Màu hô rồi không được hô lại. Ở bài số 7, điều kiện này không có. Như đã phân tích ở trên, ta thấy rằng có thể áp dụng chiến thuật cũ với modulo 101, nhưng vì điều kiện không cho phép màu hô rồi được dùng lại nên chiến thuật gặp trở ngại! Vì người chơi đầu tiên (đứng cuối hàng) sau khi đã chọn 1 màu nón (theo modulo), thì khả năng trùng với màu của một trong những người đứng trước là rất cao, lên đến 99/101, nên có thể nói rằng gần như sẽ có một người tuy biết rõ màu nón của mình, nhưng không thể hô! Và chúng ta gặp bế tắc ở đây! Konstantin Knop, tác giả của bài toán, đưa ra gợi ý như sau: Hãy để người chơi không may mắn hô lên màu nón của người xếp đầu hàng (người không thấy nón của ai). Lúc này, tất cả những người chơi chưa đoán màu nón của mình nếu thấy có người nào đó (trừ người đầu tiên) đoán màu của người đầu hàng, sẽ biết rằng đó là kẻ "không may mắn". Những người tiếp theo, căn cứ vào đó sẽ tính được màu nón của mình (và không trùng lại nữa), và chỉ có người đứng đầu hàng (người đoán cuối cùng) là đoán sai, do màu nón của anh ta đã bị sử dụng. 61 Toán yêu người những đồng cộng của online chí Tạp Như vậy với chiến thuật này, không quá 3 người phải hi sinh để cứu mọi người khác. Trong số này, không phải ai cũng là "anh hùng", vì người cuối hàng (người đoán đầu tiên) biết màu nón của mình với xác suất 1/2. Bằng cách thông báo những gì mình thấy, anh ta hi sinh cơ hội của mình. Hai người còn lại "ra đi" trước cả khi họ phải đoán. Liệu phương án trình bày ở trên là tối ưu? Câu trả lời là chưa. Bạn đọc hẵn sẽ đặt câu hỏi vì sao chúng tôi (và cả tác giả của bài toán) bàn về phương án này, mặc dù nó chưa phải lời giải cần tìm? Đơn giản là vì nó đẹp và nó có thể giải quyết tổng quát với M > N nón. Để đi đến đến lời giải tối ưu cho bài toán này, chúng tôi xin mời độc giả rời xa modulo mà chuyển sang một phương thức khác: sử dụng hoán vị! Hãy tưởng tượng, ta có thêm một người chơi "ảo", đội chiếc nón còn lại và đứng sau người cuối hàng. Như vậy, toàn bộ cách đội nón trở thành hoán vị của 101 số! Làm thế nào để người chơi (không ảo) đầu tiên có thể truyền tải thông tin cho các người khác đoán ra hoán vị của tất cả bọn họ? Trước mặt anh ta là 99 người, nên chỉ có 2 hoán vị có thể có khi quan sát từ vị trí này. Với chỉ một bit thông tin (ứng với 2 hoán vị) như vậy, làm sao họ có thể chiến thắng? Câu trả lời là anh ta sẽ chọn màu sao cho hoán vị tương ứng là một hoán vị chẵn (even permutation)2. Căn cứ vào đó những người chơi tiếp theo sẽ đoán ra màu nón của mình, nằm trong số 2 màu mà họ chưa nghe thấy hoặc chưa quan sát thấy. Nhờ vào hoán vị chẵn, họ sẽ chọn đúng màu nón của mình! Một lời giải đơn giản và tuyệt đẹp! Chúng ta hãy cùng xét ví dụ cụ thể như sau: Giả sử có 3 người chơi và 4 nón: • Giả sử người đứng cuối hàng thấy nón người đứng đầu tiên là 2 và người tiếp theo là 4, nghĩa là các hoán vị có thể có sẽ có dạng [* * 4 2]. Cụ thể, có 2 hoán vị có thể có 2Hoán vị chẵn (even permutation) là một hoán vị có số lượng nghịch thế (inversion), tức số cặp mà ở đó số lớn xuất hiện trước số nhỏ, là chẵn. Ví dụ [1 3 4 2] có 2 nghịch thế là (3, 2) và (4, 2) nên là hoán vị chẵn. 62 Toán yêu người những đồng cộng của online chí Tạp là [1 3 4 2] và [3 1 4 2]. Vì [1 3 4 2] là hoán vị chẵn ([3 1 4 2] là hoán vị lẻ), nên người đầu tiên sẽ hô mình có màu 3 (và gán 1 cho người "ảo"). • Lúc này, người tiếp theo có thông tin cho anh ta là [* 3 * 2], nên có 2 hoán vị tương ứng là [1 3 4 2] và [4 3 1 2], nên anh ta sẽ chọn [1 3 4 2] do [1 3 4 2] là hoán vị chẵn và [4 3 1 2] là hoán vị lẻ (có 5 nghịch thế). Vì vậy, anh ta hô màu 4 cho mình. Và đây là kết quả đúng. • Người cuối cùng, lắng nghe thông tin từ 2 người trước, nên có [* 3 4 *] và có 2 hoán vị để anh ta có thể chọn là [1 3 4 2] và [2 3 4 1]. Ở đây một lần nữa anh ta sẽ chọn [1 3 4 2] vì đó là hoán vị chẵn ([2 3 4 1] có 3 nghịch thế, nên là hoán vị lẻ) nên sẽ hô màu 2 cho mình. Vậy theo chiến thuật này, chắc chắn N ´ 1 người sau sẽ đoán đúng màu nón của mình và người đầu tiên có 2 khả năng để chọn nên khả năng chiến thắng cho tất cả mọi người là 1/2. Tiếp theo, để kết thúc cho chuyên mục "Các bài toán đội nón", chúng tôi trình bày phần lời giải cho một trường hợp rất khó với bài toán vô hạn nón, trong đó phần lớn phải sử dụng đến sự hỗ trợ của máy tính. 3. Bài toán vô hạn nón Trong phần này, chúng tôi tham khảo và gần như dịch lại phần lớn những ghi chú từ bài toán #1179 trong chuyên mục “Câu đố hàng tuần” của nhà toán học Stan Wagon (đại học Macalester). Như 2 phần trước, chúng tôi đăng lại đề bài ở đây để độc giả tiện theo dõi. Bài toán này được đề ra bởi Lionel Levine (đại học Cornell) vào năm 2011 như sau: Bốn người cùng tham gia một trò chơi đoán nón như sau: Người dẫn trò sẽ đội vô hạn các nón có màu trắng hoặc đen lên đầu mỗi người với xác suất nón trắng và đen là như nhau và bằng 12. Các nón của mỗi người được đánh số lần lượt 1, 2, . . . Mỗi người chơi chỉ thấy được toàn bộ nón của 3 người khác nhưng nón của mình thì họ không thấy. Mỗi người sẽ được phát một tờ giấy và họ được phép ghi vào đó một con số, ứng với chỉ số của nón của họ mà họ đoán là màu đen. Sau khi nhận đủ trả lời, người dẫn trò sẽ kiểm tra số được 63 Toán yêu người những đồng cộng của online chí Tạp ghi trên giấy của mỗi người. Nếu cả 4 người cùng đoán đúng (tức là 4 người đều ghi được con số ứng với nón màu đen của mình), họ thắng trò chơi, ngược lại, chỉ cần một người đoán không đúng, họ thua. Bốn người được thảo luận trước chiến thuật trước khi chơi và không có bất kỳ trao đổi nào sau đó. Họ cũng không biết được thời điểm mà những người khác đưa giấy cho người dẫn trò. Hãy tìm chiến thuật để xác suất thắng là cao nhất. Ví dụ: họ đều ghi số 2015 vào các mảnh giấy. Khi đó, cơ hội chiến thắng sẽ là 1/16 vì xác suất nón thứ 2015 của mỗi người là 1/2. 3.1. Chiến thuật New Zealand Lời giải đầu tiên trình bày ở đây được Stan Wagon gọi là chiến thuật New Zealand (vì đội bóng bầu dục của New Zealand có tên và biểu tượng là ALL-BLACKS). Chiến thuật như sau: Người thứ j sẽ tìm ra chỉ số #j nhỏ nhất sao cho toàn bộ nón thứ #j của tất cả những người quan sát được đều có màu đen. Người này sẽ đoán màu nón thứ #j của mình cũng là màu đen. Chiến thuật này sẽ thành công nếu tại vị trí nào đó tất cả đều đội nón đen và thất bại nếu như có 1 người đội nón trắng. Vì có n khả năng có 1 người đội nón trắng và 1 khả năng tất cả đều đội nón đen, nên xác suất thành công của chiến thuật sẽ là 1/(n + 1). Hãy thử phân tích cho trường hợp đơn giản với 2 người chơi: ta thấy nếu các nón đầu tiên có màu là Đen-Đen, họ sẽ thành công. Nếu có màu Trắng-Trắng họ sẽ đi lên cặp tiếp theo, nếu 64 Toán yêu người những đồng cộng của online chí Tạp là Đen-Trắng hoặc Trắng-Đen, họ sẽ thất bại. Như vậy xác suất để chiến thắng là 1/3. Stan Wagon, sau đó nhận ra rằng nếu như chiến thuật là tìm ra chỉ số #j nhỏ nhất trong đó có đúng k nón trắng cũng sẽ thành công với xác suất 1/(n + 1) với k ă n bất kỳ. Chiến thuật New Zealand với mở rộng này đồng nghĩa với k = 0. Tư tưởng này khá gần với phần 1 của bài trong chiến thuật đối phó với người dẫn trò "xảo quyệt". Đây có phải là chiến thuật tốt nhất? Câu trả lời là chưa phải, nhưng đây là một chiến thuật đơn giản có hiệu quả rất tốt. Theo Stan Wagon, với n = 2 và n = 3, hiệu quả của chiến thuật có thể so sánh với các chiến thuật phức tạp hơn. Tuy nhiên với n tổng quát, chiến thuật được đưa ra bởi Peter Winkler sẽ thành công với xác suất xấp xỉ 1/log(n), khi n lớn sẽ vượt trội chiến thuật New Zealand. 3.2. Chiến thuật Winkler (2011) Chiến thuật này như sau: tất cả người chơi sẽ thống nhất với nhau một số t và mỗi người sẽ đoán dựa trên 2 tiêu chí sau đây: • Tiêu chí (A). Trong số t nón đầu tiên của mỗi người đều có ít nhất một nón đen. • Tiêu chí (B). Tổng các chỉ số của nón đen đầu tiên trên đầu mọi người chia hết cho t. Người chơi thứ j quan sát thấy toàn bộ n ´ 1 nón đen đầu tiên của những người chơi khác nên khi có t và áp dụng 2 tiêu chí trên, anh ta sẽ nhanh chóng tính ra được chỉ số nón đen đầu tiên của mình. Và đó là con số duy nhất trong khoảng từ 1 đến t. Xét tiêu chí (A) với n = 1000 người chơi và giá trị t = 13, khi đó xác suất trong 13 nón đầu có nón đen xuất hiện của một người là 1´(1/2)13 và do vậy xác suất cả n người đều có nón đen trong số t nón đầu sẽ là (1 ´ (1/2)13)1000 = 0.885, nghĩa là xấp xỉ 88.5%. Xác suất này sẽ tiến dần đến xấp xỉ 100% khi t tăng. Xét tiêu chí (B), xác suất để tổng tất cả các chỉ số của nón đen đầu tiên chia hết cho t là 1/t. 65 Toán Như vậy, chiến thuật Winkler đề ra sẽ thành công khi cả (A) và (B) đều đúng, nghĩa là xác suất thành công sẽ là: 1 ´12t n1t yêu nếu ta xét (A) và (B) như 2 biến cố độc lập (mặc dù thực tế (A) và (B) không hoàn toàn độc lập). người Câu hỏi đặt ra là với Để tìm cực trị cho (1 ´ 12t )n 1t, ta xét đạo hàm: chiến thuật như vậy, xác suất chiến thắng là B Bt (1 ´ 12t )n t ! =(1 ´ 2´t)n(ntlog(2) ´ 2t + 1) (2t ´ 1)t2 những bao nhiêu? Và giá trị t cần chọn là bao nhiêu? Để chiến thuật Winkler Vì t ą 0 và n ą 0 nên đạo hàm bằng 0 khi: ntlog(2) ´ 2t + 1 = 0 ô 2t = ntlog(2) + 1 Ta có khai triển MacLaurin của 2tlà: thành công với xác suất cao nhất, cần tìm ra giá 2t =ÿ∞ n=0 tnlogn(2) n! đồng trị t sao cho xác suất của cả (A) và (B) đồng xảy ra đạt giá trị cực đại. Giá trị t thỏa mãn sẽ xấp xỉ t « log2(2n ´ 2). cộng của online chí Tạp Ở đây, tiêu chí (B) cần quan tâm cao hơn vì có khả năng giá trị tối ưu sẽ đạt được khi tổng các chỉ số đầu tiên có giá trị khác 0 (mod t), nghĩa là xác suất tối ưu có thể xảy ra khi tổng này đồng dư với s (mod t) ‰ 0 nào đó. Chiến thuật Winkler vì vậy trở thành tìm cặp giá trị (t, s) sao cho giá trị xác suất đạt cực đại với đầu vào n cho trước. Ta có thể tìm ra giá trị này thông qua thuật toán như sau: Gọi F(n, t, s) là số cách đội nón cho n người với t nón đầu tiên sao cho cả 2 tiêu chí (A) và (B) đều thỏa. Khi đó, xác suất thành công chính là F(n, t, s)/2tn. F có thể xây dựng đệ quy như sau: • F[1, t, 0] = 1, lưu ý, ở đây cần hiểu là s = t, và với n = 1 thì chỉ có 1 khả năng là nón vị trí t là nón có đầu tiên có màu đen. • F[1, t, s] = 2t´s, vì chỉ cần nón ở vị trí s là nón đầu tiên màu đen, các nón sau đó có thể có màu tùy ý. • F[n, t, s] = řtk=12(t´k) F[n - 1, t, modulo(s - k, s)], đây 66 Toán yêu người những đồng cộng của online chí Tạp chỉ là đệ quy dựa trên kết quả ở bước trước. Một số kết quả tính toán với chiến thuật Winkler: • n = 2 và n = 3: chiến thuật Winkler không tốt hơn chiến thuật New Zealand. Cụ thể xác suất tối ưu cho n = 2 là F(2, 2, 0)/16 = 5/16 ă 1/3 và n = 3 là F(3, 3, 0)/512 = 121/512 ă 1/4. • n = 4, chiến thuật Winkler nhắm tới s = 0 không nhỉnh hơn New Zealand, nhưng với kết quả tối ưu t = 4 và s = 1, xác suất là 421/2048, hay 0.2056, khoảng 3% nhiều hơn 1/5. • Với n lớn, chiến thuật Winkler vượt trội chiến thuật New Zealand. Với n = 1000, (t, s) tối ưu là (13, 10) xác suất tính được xấp xỉ 0.068, tức là 68 lần tốt hơn xác suất 1/1001 của chiến thuật New Zealand. 3.3. Những ý tưởng mới Chiến thuật Winkler mặc dù cho ra kết quả rất tốt với n lớn, tuy nhiên, đây vẫn chưa phải là chiến thuật tốt nhất. Năm 2014, Larry Carter, J-C Reyes, và Joel Rosenberg (San Diego) đã đề xuất ra hai chiến thuật mới như sau: Chiến thuật “sửa sai”3. Ý tưởng của chiến thuật này như sau: nếu như một người nhận ra rằng có đồng đội nào đó của mình sẽ thất bại nếu tuân theo chiến thuật cơ bản của Winkler, lúc đó người này sẽ nhận ra rằng họ sẽ thất bại nếu cứng nhắc tuân theo chiến thuật gốc, vì vậy thay vì áp dụng trong đoạn từ 1 đến t chiến thuật Winkler, người này sẽ sửa sai bằng cách áp dụng chiến thuật trong đoạn từ t+1 đến 2t. Và như vậy, nếu mọi người đều nhận ra không thể áp dụng chiến thuật trong đoạn 1 đến t, họ sẽ sửa sai bằng cách nhảy lên một đoạn. Chiến thuật này vẫn sẽ thất bại trong trường hợp có người chơi không thể tìm thấy lỗi. Ví dụ như người A có toàn bộ t nón đầu đều màu trắng, lúc đó A sẽ không thể nhận ra là cần phải sửa lỗi. Kiểm tra bằng máy tính, chiến thuật này thật sự tốt hơn chiến thuật Winkler, với (n = 4, t = 4, s = 1), chiến thuật nâng xác suất thành công từ 0.205566 lên 0.210090. 3Thuật ngữ gốc là The “reset” strategy, ở đây chúng tôi gọi là “sửa sai” dựa trên ý tưởng của chiến thuật. 67 Toán yêu người những đồng Chiến thuật hoán vị. Ý tưởng cơ bản là thay vì tuân theo chiến thuật (B) tính tổng toàn bộ những nón đen đầu tiên của đồng đội thì họ sẽ tính các tổng từ các hoán vị khác nhau. Điều này buộc phải sử dụng thêm giả định là người chơi ngầm định mỗi người có thứ tự khác biệt. Sử dụng trợ giúp của máy tính, Stan Wagon cho ra kết quả với n = 3, t = 4 và hoán vị (342), kết quả đạt được là 263/1024 = 0.256, cao hơn 1/4 của chiến thuật New Zealand và 121/512 = 0.236 của chiến thuật Winkler. Với chiến thuật “sửa sai”, kết quả là 0.259. J-C Reyes và Joel Rosenberg tiếp tục đề xuất một chiến thuật mới đạt kết quả tốt hơn cho trường hợp n = 3. Stan Wagon cũng không giải thích được vì sao phương pháp này có thể đạt hiệu quả cao như vậy! Tuy nhiên, kiểm chứng bằng máy tính cho thấy kết quả thật sự tốt hơn. Cụ thể là xác suất với n = 3 là 0.2617, cao hơn toàn bộ các chiến thuật đã được giới thiệu tính đến đây. Phương pháp này dựa trên 3 ma trận kích thước 8 ˆ 8 được xây dựng trước: cộng của online 2, 1, 4, 3, 5, 6, 8, 7, 1, 3, 2, 5, 4, 7, 6, 8, 3, 2, 1, 4, 6, 5, 7, 4, 5, 4, 6, 2, 1, 3, 1, 2, 4, 5, 7, 1, 3, 2, 8, 6, 7, 6, 5, 8, 2, 1, 4, 3, 6, 8, 3, 7, 1, 4, 1, 2, 8, 7, 2, 6, 5, 6, 2, 1. Ma trận A 2, 1, 3, 5, 4, 6, 7, 8, 1, 3, 2, 4, 6, 5, 8, 7, 3, 2, 1, 1, 5, 4, 6, 6, 5, 4, 1, 3, 2, 7, 6, 5, 4, 5, 6, 2, 1, 3, 7, 7, 7, 6, 4, 8, 3, 1, 2, 5, 6, 8, 5, 7, 2, 2, 3, 1, 8, 7, 8, 6, 1, 3, 1, 2. Ma trận B 2, 1, 3, 5, 4, 6, 7, 8, 1, 3, 2, 4, 6, 5, 8, 7, 4, 2, 1, 6, 5, 8, 8, 6, 4, 5, 4, 2, 1, 7, 6, 7, 5, 4, 6, 1, 2, 3, 6, 1, 6, 7, 5, 3, 8, 2, 1, 4, 8, 6, 7, 6, 3, 1, 4, 2, 7, 8, 4, 5, 2, 4, 2, 1. Ma trận C Chiến thuật áp dụng như sau: người A sẽ tìm nón đen nhỏ nhất của B và C, sau đó sẽ chọn giá trị ở vị trí tương ứng ở ma trận A. chí Ví dụ như A thấy người B có nón đầu tiên là màu đen và người C có nón đầu tiên màu đen là nón thứ 5. Khi đó, A sẽ chọn số ở vị trí (1, 5) ở ma trận A, ứng với giá trị 5. B và C cũng làm tương Tạp tự với ma trận của mình. Chiến thuật sẽ chắc chắn sai khi có một người có nón đen đầu tiên nằm ngoài 8 vị trí đầu tiên. Lưu ý rằng các số trên dòng và cột ở các ma trận này không phải là hoán vị, nên tổng khả năng của các ma trận là 83˚64 = 10173. 68 Toán Chiến thuật Winkler với (n = 3, t = 3, s = 0) tương ứng với chiến thuật này với ma trận A = B = C và bằng   1 3 2 3 2 1 2 1 3   yêu người những đồng cộng của online chí Tạp Để tổng kết các phương pháp, chúng tôi sử dụng lại hình ảnh của tóm tắt Stan Wagon và trình bày lại ở Hình. 6.3. Hình 6.3: Hiệu quả của các chiến thuật dùng để giải bài toán vô hạn nón. Nguồn: [5] 3.4. Trường hợp n = 2 Toàn bộ các chiến thuật ở trước đều cố gắng tìm ra phương án tốt hơn cho n ą 2, vì với n = 2, đa số đều nghĩ rằng chiến thuật đơn giản New Zealand đã cho kết quả tối ưu. Tuy nhiên, Jim Roche đã khám phá ra rằng, ngay cả trong trường hợp n = 2, các phương án tốt hơn vẫn còn có thể được phát hiện! Cụ thể, chiến thuật sau đây sẽ thành công với xác suất 22/63 = 0.349 ą 1/3. A và B sẽ tuân theo 7 "mẫu" như sau: nếu A thấy 3 nón đầu tiên của B là Đen-Đen-Đen hoặc Đen-Đen-Trắng hoặc Trắng-Đen Đen, A sẽ chọn 1. Nếu A thấy 3 nón đầu là Đen-Trắng-Đen hoặc 69 Toán yêu người những đồng cộng của online chí Tạp Trắng-Trắng-Đen sẽ chọn 2 và nếu A thấy Trắng-Đen-Đen hoặc Trắng-Đen-Trắng sẽ chọn 3. Và B cũng làm tương tự. Chiến thuật này, Stan Wagon gọi đây là chiến thuật 3-nón4. Nếu A thấy 3 nón đầu của B đều màu trắng, A biết rằng chiến thuật không sử dụng được, A sẽ sửa sai bằng cách di chuyển quan sát lên các nón từ 4 đến 6 và lại áp dụng 7 luật như trên. Kiểm tra bằng vét cạn (Brute-force), nếu không áp dụng sửa sai, chiến thuật cho kết quả 22/64 = 0.34375 và với sửa sai, kết quả là 22/63 = 0.3492064. Stan Wagon đã thử nghiệm với các ma trận khác nhau cho A và B, nhưng kết quả không cao hơn. Các mở rộng với các giá trị của t với n = 2 và n = 3 được khảo sát bởi máy tính và kỷ lục hiện tại cho n = 2, t = 8 là 22937/65535 = 0.3499961 và 0.35 vẫn đang là một chặn trên cho trường hợp vô hạn nón có 2 người chơi. Tiefenbruck, Reyes, Carter, và Rosenberg đưa ra một cách lý luận đơn giản cho kết quả 0.35 như sau: bắt đầu với chiến thuật 3-nón 11213321 với xác suất 22/64. Nếu A thấy 3 nón đầu tiên của B là toàn trắng hoặc toàn đen, A sẽ bỏ qua và xem xét 3 nón tiếp theo và cứ thế tiếp tục. B cũng làm tương tự. Nghĩa là họ chỉ áp dụng chiến thuật 3-nón khi thấy 3 nón có màu khác nhau, do vậy, có 60 khả năng mà tại đó ít nhất A hoặc B phải đoán (không bỏ qua). Và họ sẽ thắng lợi với xác suất 21 trong tổng số 60 trường hợp này, ít hơn 1 trường hợp so với chiến thuật 3-nón (là trường hợp 3 nón đầu tiên của cả 2 người đều màu đen). Và như vậy, xác suất chiến thắng là 21/60 = 0.35. 4 Với 0 là đen và 1 là trắng, chiến thuật 3-nón tóm tắt như sau: (0, 0, 0) Ñ 1, (0, 0, 1) Ñ 1, (0, 1, 0) Ñ 2, (0, 1, 1) Ñ 1, (1, 0, 0) Ñ 3, (1, 0, 1) Ñ 3, (1, 1, 0) Ñ 2, hay gọi ngắn gọn là 11213321, ứng với chỉ số cho bộ 8 giá trị khác nhau sinh ra từ 3 nón. 70 Toán yêu người những đồng cộng của online chí Tạp 3.5. Sáng tạo bất tận Liệu chúng ta có thể nâng cao hiệu quả cho bài toán? Để giải đáp được câu hỏi này, trước tiên cần phát biểu lại bài toán một cách hệ thống. Thử xét với trường hợp n = 2: Gọi P là tập của tất cả các chuỗi 0 và 1; và N là tập số tự nhiên. Khi đó, một cách đội nón ở một chỉ số nào đó là một phần tử của P ˆ P.5 Một chiến thuật là một hàm S : P ˆ P Ñ N, không quan tâm nếu hàm này có khả dựng hay không (hay dễ hiểu hơn là không quan tâm đến sự phức tạp của hàm này). Và như vậy với lý thuyết tập hợp dựa trên tiền đề chọn6, tồn tại một chiến thuật mà nếu người chơi sử dụng họ sẽ đưa tập con của PˆP về chiến thắng với độ đo ngoài bằng 1. Điều này có nghĩa là luôn tồn tại chiến thuật mà người chơi không thua! Hoặc, quay lại những nghi ngờ kinh điển của Toán học về tiên đề chọn với những tranh cãi cũng vô tận như chính bản thân của vấn đề! Như vậy, mặc dù tồn tại chiến thuật luôn chiến thắng (Lưu ý: tiên đề chọn được sử dụng), với trường hợp n = 2, chiến thuật tốt nhất được ghi nhận hiện tại vẫn chỉ là 35% và với n ą 2, kết quả hãy còn thấp hơn rất nhiều. Điều này có nghĩa là bài toán vẫn còn được để mở và mong chờ các đóng góp từ những người yêu toán học. 4. Lời kết Như vậy là với 2 chuyên mục đầu tiên về toán học giải trí đăng tải ở 2 số đầu tiên của Epsilon, chúng tôi đã giới thiệu tương đối trọn vẹn "50 năm những bài toán đội nón". Thông qua những bài toán này, chúng tôi hi vọng đã mang đến cho độc giả không 5Kết quả này được chứng minh bởi Freiling với tên gọi định lý C. Freiling, có thể tham khảo ở liên kết cuối bài. 6Tiên đề chọn, hay còn gọi là tiên đề Zermelo-Fraenkel được đưa ra bởi Zermelo vào năm 1904, là tiên đề khẳng định rằng với mỗi họ tập hợp tùy ý không rỗng và đôi một không giao nhau luôn tồn tại một tập hợp mà mỗi phần tử của nó là phần tử của một tập hợp trong họ tập hợp kia và phần tử đó là duy nhất. Một cách phát biểu khác của tiên đề chọn là: “Với một họ X bất kỳ các tập hợp không rỗng, luôn tồn tại một hàm chọn f định nghĩa trên X”. Đây chính là cơ sở của chứng minh cho bài toán vô hạn nón bằng cách áp dụng hàm chọn cho S. 71 Toán yêu người những đồng cộng của online chí Tạp chỉ là những bài toán đố thuần túy mà còn từ đó cho thấy giá trị và vẻ đẹp của toán học tiềm ẩn ở mọi nơi. Để tiện tra cứu, độc giả có thể truy tìm lại nguồn gốc của từng bài thông qua những tài liệu sau: • Phần 1: chúng tôi sử dụng chủ yếu tài liệu ở [1] và [2]. Phần bài toán đội nón số 6, "người dẫn trò xảo quyệt" khá hiếm gặp. Bài toán theo ghi nhận của chúng tôi xuất hiện một cách chính thức tại Việt Nam vào năm 2007, trong khóa học của giáo sư Michel Waldschimidt, khoa Toán đại học Pierre et Marie Curie, Paris. Ông đã đến trường Đại học Khoa học Tự nhiên TP.HCM trong dịp này và giảng cho sinh viên và học sinh phổ thông Năng Khiếu các bài giảng rất thú vị, phần bài giảng này, may mắn thay vẫn còn có thể được tìm thấy ở đây. • Phần 2: Chúng tôi sử dụng chủ yếu từ [3] và tham khảo Blog của Tanya Khovanova. • Phần 3: Bạn đọc có thể xem thêm ở [4] và đặc biệt là ở [5] (trang gốc của tác giả Stan Wagon). Tài liệu tham khảo [1] E. Brown and J. Tanton, “A dozen hat problems,” Archives of Psychology, vol. 16, no. 4, pp. 22–25, 2009. [2] A. Zorn, “Colored hats and logic puzzles,” Berkeley Math Circle, 2013. [3] T. Khovanova, “A line of sages,” The Mathematical Intelli gencer, 2014. [4] C. S. Hardin and A. D. Taylor, “An introduction to infi nite hat problems,” The Mathematical Intelligencer, vol. 30, no. 30, pp. 20–25, 2008. [5] S. Wagon, “Problem of the week 1179,” 2014. 72 Tạp chí online của những người yêu Toán cộng đồng ToánBÀI TOÁN FROBENIUS yêu người những đồng cộng của online chí Tạp VỀ NHỮNG ĐỒNG XU Trần Nam Dũng (Đại học KHTN, TP. Hồ Chí Minh) Nguyễn Tất Thu (THPT Chuyên Lương Thế Vinh, Đồng Nai) Bài toán Frobenius về những đồng xu là một bài toán kinh điển đã được nhắc đến trong nhiều bài viết, nhiều công trình nghiên cứu. Một trong những lý do để đề tài tiếp tục được để ý là bài toán số 6 trong kỳ thi chọn học sinh giỏi toán quốc gia năm học 2014-2015 mới diễn ra vào tháng 1 vừa qua. Tác giả thứ nhất của bài báo có nhiều duyên nợ với bài toán này. Khi còn là học sinh, anh đã gặp (và rất may mắn, giải được) bài toán 4 ở dưới đây. Sau này anh lại gặp lại bài toán nhiều lần, lúc này đã là trong vai trò thầy giáo, giảng viên. 1. Mở đầu Chúng ta mở đầu bằng một bài toán vui sau đây: Chúng ta đều đã đọc truyện hoặc xem phim Tây Du Ký. Câu chuyện sau đây rút từ chuyến đi kỳ vĩ của thầy trò Đường Tăng đến Tây Trúc. Vừa thoát khỏi kiếp nạn Bạch cốt tinh, thầy trò Đường tăng lại đi vào một vương quốc mới, gọi là vương quốc Ngũ Bát. Sở dĩ có cái tên này là bởi vì Ngân hàng trung ương của Vương quốc này chỉ phát hành 2 loại tiền 5 quan (Ngũ) và 8 quan (Bát). Vương quốc này cũng chưa được phát triển lắm nên người dân ở đây chỉ biết phép tính cộng, không biết phép tính trừ. Vì thế, khi bán hàng, nếu mình đưa thừa người ta sẽ không trả lại (còn đưa thiếu thì người ta. . . không chịu - khôn lắm). Thầy trò Đường tăng đang đi tung tăng trong thành thì thấy một siêu thị có tên là “Over 28”. Thấy tên lạ lạ, họ bèn bước vào. 73 Toán yêu người những đồng cộng của online chí Tạp Nhân viên bảo vệ ra chặn lại, xem chừng không muốn cho vào. Trư bát giới xông ra nói: - Sao không cho chúng ta vào? Tay bảo vệ chỉ tay vào số 28 (nhị thập bát) nói: Ông có thấy số gì đây không? - 28 à. 28 tuổi mới được vào à. Yên tâm đi nhé chú em. Anh đây 360 tuổi rồi nhé. Còn ông anh đang gãi mông kia 720 tuổi. Cái chú đang gánh hàng được 240 tuổi. Ngay cả con ngựa này cũng 130 tuổi rồi. Trẻ nhất ở đây có lẽ là sư phụ của bọn anh, ông ấy vừa làm sinh nhật lần thứ 30. Các chú có cần xem chứng minh nhân dân không, loại mới nhé, có cả tên bố mẹ. - Không, không, đây không phải tuổi, đây là. . . - Đây là gì. . . Trư Bát giới được thể tấn công. - Đây là siêu thị mà mọi món hàng đều từ 28 quan trở lên. Tôi thấy mấy ông nhà quê quá, sợ không đủ tiền nên không muốn cho vào. - Ấy, chú đừng nghĩ thế. Bọn anh đây đều là con nhà có điều kiện nhé, tiền 5 quan, 8 quan bọn anh mới đổi ở cửa khẩu ních túi nhé. - Vậy xin mời các anh vào ạ. Bài toán mở đầu: Chứng minh rằng thầy trò Đường tăng có thể mua đúng (tức là trả đúng giá tiền) mọi món hàng ở trong siêu thị "Over 28". Về mặt toán học, bài toán này tương đương với mệnh đề sau: Chứng minh rằng với mọi số nguyên N ě 28, tồn tại x, y nguyên không âm sao cho N = 5x + 8y. Bài toán này là trường hợp riêng của bài toán Frobenius về những đồng xu mà ta sẽ nói đến dưới đây. Có hai cách để giải bài toán này, đều mang tính thuật toán. Cách 1: Ta tìm cách biểu diễn cho các số 28, 29, 30, 31, 32. Sau đó chú ý rằng nếu N biểu diễn được thì N + 5 cũng biểu diễn được. 74 Toán yêu người những đồng cộng của online chí Tạp Cách 2: Cách này khó nghĩ đến hơn nhưng đẹp hơn. Cụ thể như sau: Ta chứng minh nếu N ě 28 biểu diễn được thì N + 1 cũng biểu diễn được. Nếu trong biểu diễn của N có 3 số 5 thì ta thay 3 số 5 bằng 2 số 8 được biểu diễn của N + 1. Nếu trong biểu diễn của N có 3 số 8 thì ta thay 3 số 8 bằng 5 số 5 thì được biểu diễn của N + 1. Một trong hai TH này phải xảy ra vì nếu không có thì N ď 2 ¨ 5 + 2 ¨ 8 = 26. Ví dụ ở trên được trích từ bài giảng của chúng tôi dành cho sinh viên khoa Toán-Tin học trường ĐH KHTN Tp HCM, môn Số học và logic, trong mục về thuật toán Euclide và định lý Bezout. Với cách phát biểu thú vị và hài hước, chúng tôi đã lôi kéo được các sinh viên vốn rất sợ Số học và Logic tham gia vào thảo luận và tìm kiếm lời giải. Thực tế, trên lớp các sinh viên đã tự mình tìm được lời giải cho bài toán theo cách 1. Bài toán nói trên chỉ là một trường hợp đặc biệt của một bài toán tổng quát hơn: bài toán Frobenius về những đồng xu. Bài toán Frobenius về những đồng xu là bài toán xác định số tiền lớn nhất không thể trả được khi chỉ sử dụng các đồng xu có mệnh giá cố định nào đó. Ví dụ với các đồng xu mệnh giá 3 và 5 đơn vị thì số tiền lớn nhất không trả được là 7 đơn vị. Số lớn nhất với mỗi bộ số như thế ta gọi là số Frobenius. Một cách toán học, bài toán được phát biểu như sau: Cho các số nguyên dương a1, a2, ¨ ¨ ¨ , an có gcd(a1, ¨ ¨ ¨ , an) = 1. Tìm số nguyên lớn nhất không biểu diễn được dưới dạng k1a1 + k2a2 + ¨ ¨ ¨ + knan với k1, k2, ¨ ¨ ¨ , kn là các số nguyên không âm. Số nguyên lớn nhất này được gọi là số Frobenius và thường được ký hiệu là g(a1, a2, ¨ ¨ ¨ , an). Và bài viết này sẽ nói về một số kết quả liên quan đến bài toán nổi tiếng này. 2. Định lý Sylvester và bài toán số 6 trong đề thi VMO 2015 Trong kì thi VMO năm 2015 có bài toán số 6 là trường hợp đặc biệt của bài toán Frobenius ứng với n = 3. Bài toán có nội dung như sau: 75 Toán yêu người những đồng cộng của online Với a, n nguyên dương, xét phương trình a2x+6ay+36z = n, trong đó x, y, z là các số tự nhiên 1. Tìm tất cả các giá trị của a để với mọi n ě 250, phương trình đã cho luôn có nghiệm (x, y, z). 2. Biết rằng a ą 1 và nguyên tố cùng nhau với 6. Tìm giá trị lớn nhất của n theo a để phương trình đã cho không có nghiệm (x, y, z). Để giải bài toán trên, chúng ta đi xét các bài toán sau đây: Bài toán 1. Cho a, b là các số nguyên dương nguyên tố cùng nhau, b ą 1. Chứng minh rằng với mọi số nguyên N, tồn tại duy nhất cặp số nguyên x, y thỏa mãn điều kiện N = ax + by và 0 ď x ă b. Lời giải. ‚ Chứng minh sự tồn tại Vì (a, b) = 1 nên theo định lí Bezout, tồn tại hai số nguyên u, v sao cho N = au + bv. Mặt khác u = b.q + r với 0 ď r ď b ´ 1 nên ta có N = a(b.q + r) + bv = a.r + b(v + a.q). Chọn x = r, y = v + a.q ta được N = ax + by với0 ď x ď b ´ 1. ‚ Chứng minh tính duy nhất Giả sử tồn tại hai bộ (x; y) và (x1; y1) thỏa 0 ď x, x1 ă b và N = ax + by = ax1 + by1 Hay a(x ´ x1) = b(y1 ´ y) (1) Do (a, b) = 1 nên từ (1) ta suy ra b|x ´ x1. Lại có 0 ď x, x1 ď b ´ 1 nên suy ra x = x1 và y = y1. Vậy bài toán được chứng minh. chí Bài toán 2. (Định lí Sylvester) Cho a, b là các số nguyên dương nguyên tố cùng nhau. Chứng minh rằng N0 = ab–a–b là số nguyên lớn nhất không biểu diễn được dưới dạng ax + by với x, Tạp y là các số nguyên không âm. Hơn nữa, với mọi p, q nguyên với p + q = N0, có đúng một trong hai số p, q biểu diễn được dưới dạng ax + by với x, y là các số nguyên không âm (mà ta sẽ gọi tắt là biểu diễn được). 76 Toán yêu người những đồng cộng Lời giải. Để giải quyết bài toán, cần thực hiện hai bước sau Bước 1: Chứng minh N0 không biểu diễn được dưới dạng ax+by với x,y là các số nguyên không âm. Giả sử tồn tại hai số nguyên không âm x, y sao cho ax + by = N0. Hay a(x + 1) + b(y + 1) = ab (2). Vì (a, b) = 1 nên từ (2), suy ra x + 1...b hay x + 1 ě b. Tương tự y + 1 ě a. Khi đó ax + by ď a(b ´ 1) + b(a ´ 1) = 2ab ´ a ´ b ą ab ´ a ´ b. Điều này dẫn đến mâu thuẫn. Do vậy N0 không biểu diễn được dưới dạng ax + by với x, y P N. Bước 2: Chứng minh với mọi số nguyên N ą N0 thì N biểu diễn được dưới dạng ax + by với x, y P N. Theo kết quả Bài toán 1 ta suy ra: tồn tại duy nhất cặp (x, y) để N = ax + by với 0 ď x ă b. Ta chỉ cần chứng minh y ě 0. Thật vậy bąab ´ a ´ b ´ a(b ´ 1) của online y =N ´ ax Mà y là số nguyên nên ta có y ě 0. Vậy bài toán được chứng minh. b= ´1. Trở lại bài toán trong đề thi VMO´2015. Bài toán đó có thể được phát biểu thành bài toán tổng quát hơn như sau Bài toán 3. Cho các số nguyên dương a, b nguyên tố cùng nhau. chí Khi đó N0 = a2b + b2a ´ a2 ´ b2 ´ ab là số nguyên dương lớn nhất không biểu diễn được dưới dạng a2x + aby + b2z với x, y, z là các số nguyên không âm. Tạp Lời giải. Tương tự như bài toán 2 và bài toán 3, ta chứng minh bài toán qua hai bước. Bước 1: Chứng minh N0 không biểu diễn được dưới dạng a2x + 77 Toán yêu người những đồng cộng của online aby + b2z. Giả sử tồn tại các số tự nhiên x, y, z để N0 = a2x + aby + b2z Hay a2(b ´ x ´ 1) + b2(a ´ z ´ 1) = ab(y + 1). Từ đây, suy ra một trong hai số b ´ x ´ 1 và a ´ z ´ 1 có ít nhất một số dương. Không mất tính tổng quát, ta giả sử b ´ x ´ 1 ě 0. Khi đó, do (a, b) = 1 nên ta suy ra b´x´1...b, dẫn tới b´x´1 ě b hay x ď ´1 (vô lí). Do vậy N0 không biểu diễn được qua a2x + aby + b2z. Bước 2: Chứng minh với mọi số nguyên N ą N0 thì N biểu diễn được dưới dạng a2x + aby + b2z. Do N ą N0 nên N ´ ab2 + a2 + ab ´ a ą ab2 ´ b2 ´ a nên theo định lí Sylvester ta suy ra tồn tại các số tự nhiên u, z sao cho N ´ ab2 + a2 + ab ´ a = ua + b2z (4). Vì u ě 0 nên u + ab ´ a ´ b + 1 ą ab ´ a ´ b nên tiếp tục áp dụng định lí Sylvester suy ra tồn tại các số tự nhiên x, y sao cho u + ab ´ a ´ b + 1 = xa + yb (5). Thay (5) vào (4) ta được N ´ ab2 + a2 + ab ´ a = a(ax + by ´ ab + a + b ´ 1) + b2z Hay N = a2x + aby + b2z. Bài toán được chứng minh. Tại kì thi IMO năm 1983 có bài toán sau Bài toán 4. Cho các số nguyên dương a, b, c đôi một nguyên tố cùng nhau. Chứng minh rằng N0 = 2abc ´ ab ´ bc ´ ca là chí số nguyên dương nhỏ nhất không biểu diễn được dưới dạng abx + bcy + caz với x, y, z là các số nguyên không âm. Tạp Lời giải. Tương tự như cách chứng minh định lí Sylvester, bài toán được chứng minh qua hai bước Bước 1: Chứng minh N0 không biểu diễn được qua abx + bcy + caz. Chứng minh điều này tương tự như cách chứng minh định 78 Toán yêu người lí Sylvester. Bước 2: Chứng minh với mọi số nguyên dương N ą N0 thì N luôn biểu diễn được dưới dạng abx + bcy + caz. Vì (a; bc) = 1 nên theo bài toán 1 tồn tại u, y sao cho au+bcy = N với 0 ď y ď a ´ 1 . Tương tự, tồn tại v, z sao cho N = vb + zac với 0 ď z ď b ´ 1. Từ đó, suy ra bcy + caz ´ N...ab. Hay tồn tại số nguyên x sao cho abx + bcy + caz = N. Ta chỉ cần chứng minh x ě 0. Thật vậy abą2abc ´ ab ´ bc ´ ca ´ bc(a ´ 1) ´ ca(b ´ 1) x =N ´ bcy ´ caz ab= ´1. những Suy ra x ě 0. Bài toán được chứng minh. đồng cộng của online chí Tạp Bài toán 5. (VN TST 2000) Cho ba số nguyên dương a, b, c đôi một nguyên tố cùng nhau.Số nguyên dương n được gọi là số bướng bỉnh nếu n không biểu diễn được dưới dạng abx + bxy + caz với x, y, z là các số nguyên dương. Hỏi có bao nhiêu số bướng bỉnh. Lời giải. Để giải bài toán này, ta chia làm hai bước Bước 1: Chứng minh N0 = 2abc là số nguyên dương lớn nhất không biểu diễn được dưới dạng abx+bcy+caz với x, y, z là các số nguyên dương. Việc chứng minh N0 không biểu diễn được qua abx + bcy + caz với x, y, z là các số nguyên dương được chứng minh tương tự như các bài toán trên. Ta chứng minh với mọi số nguyên dương N ą N0 thì N luôn biểu diễn được qua abx+bcy+caz với x, y, z là các số nguyên dương. Trước hết ta chứng minh nhận xét: Với 1 ď x ď b, 1 ď y ď a thì ax + by lập thành hệ thặng dư đây đủ theo mô đun ab. Thật vậy: Dễ thấy có tất cả a.b tổng ax + by với 1 ď x ď b, 1 ď y ď a. Giả sử tồn tại 1 ď x, x1 ď b, 1 ď y, y1 ď a sao cho ax + by ” ax1 + by1( mod ab). Hay a(x ´ x1) ” b(y1 ´ y)( mod ab). Từ đây, suy ra x ´ x1...b. Mà 1 ď x, x1 ď b nên suy ra x = x1, dẫn đến y = y1. Do vậy nhận xét được chứng minh. 79 Toán yêu người những đồng cộng của online chí Tạp Theo nhận xét trên và kết hợp với a, b, c đôi một nguyên tố nên với 1 ď x ď b, 1 ď y ď a thì c(ax + by) = acx + bcy lập thành hệ thặng dư đây đủ theo mô đun ab. Do đó với mọi số nguyên dương N ą N0, luôn tồn tại 1 ď z0 ď a, 1 ď y0 ď b sao cho acz0 + bcy0 ” N( mod ab) hay tồn tại số nguyên x0 sao cho acz0 + bcy0 + abx0 = N. Lại có acz0 + bcy0 ď acb + bca = 2abc ă N nên ta có x0 ą 0. Vậy với mọi N ą N0 thì N biểu diễn được dưới dạng abx+bcy+caz với x, y, z là các số nguyên dương. Bước 2: Đặt B là tập các số nguyên dương không biểu diễn được dưới dạng abx + bcy + caz với x, y, z là các số nguyên dương. Và A = t1, 2, ¨ ¨ ¨ , ab + bc + ca ´ 1u Y tab + bc + ca, ab + bc + ca + 1, ¨ ¨ ¨ , 2abcu. Dễ thấy t1, 2, ¨ ¨ ¨ , ab + bc + ca ´ 1u Ă B. Đặt C = tab+bc+ca, ab+bc+ca+1, ¨ ¨ ¨ , 2abcu. Ta cần tìm |BXC|. Với mỗi n P C ta xét hàm f(n) = 2abc + ab + bc + ca ´ n. Ta chứng minh n P B ô f(n) R B (1). Với n P B, theo chứng minh trên suy ra tồn tại các số nguyên 1 ď y0 ď b, 1 ď z0 ď c và x0 sao cho n = abx0 + bcy0 + caz0. Vì n P B nên x0 ď 0. Khi đó f(n) = ab(1 ´ x0) + bc(1 + a ´ y0) + ca(1 + b ´ z0) R B. Giả sử tồn tại n R B để f(n) R B. Suy ra tồn tại các số nguyên dương x, y, z,x1, y1, z1 sao cho n = abx + bcy + caz và f(n) = abx1 + bcy1 + caz1 Hay 2abc = (x + x1 ´ 1)ab + (y + y1 ´ 1)bc + (z + z1 ´ 1)ca Suy ra 2abc R B vô lí. Vậy (1) được chứng minh. Từ chứng minh trên ta suy ra |B X C| =12|C| =2abc ´ ab ´ bc ´ ca + 1 2. Vậy số các số bướng bỉnh là: abc +ab + bc + ca ´ 1 2. 80