Một mô hình của OpenAI đã bác bỏ một giả thuyết trung tâm trong hình học rời rạc

Bài từ OpenAI, dịch bởi Gemini.

Trong gần 80 năm qua, các nhà toán học đã nghiên cứu một câu hỏi tưởng chừng đơn giản: nếu bạn đặt $n$ điểm trên mặt phẳng, có bao nhiêu cặp điểm có khoảng cách bằng đúng 1?

Đây là bài toán khoảng cách đơn vị trên mặt phẳng, được Paul Erdős đề xuất lần đầu tiên vào năm 1946. Nó là một trong những câu hỏi nổi tiếng nhất trong hình học tổ hợp, dễ phát biểu nhưng lại đặc biệt khó giải quyết. Cuốn sách năm 2005 Research Problems in Discrete Geometry (Các vấn đề nghiên cứu trong Hình học Rời rạc) của Brass, Moser và Pach, gọi nó là “có lẽ là bài toán được biết đến nhiều nhất (và dễ giải thích nhất) trong hình học tổ hợp.” Noga Alon, một chuyên gia hàng đầu về tổ hợp tại Đại học Princeton, mô tả đây là “một trong những bài toán yêu thích của Erdős.” Erdős thậm chí còn từng treo thưởng tiền mặt cho ai giải quyết được bài toán này.

Hôm nay, chúng tôi chia sẻ một bước đột phá về bài toán khoảng cách đơn vị. Kể từ công trình nguyên bản của Erdős, niềm tin phổ biến luôn là các cấu hình “lưới vuông” về cơ bản đã là tối ưu nhất để tối đa hóa số lượng các cặp có khoảng cách bằng 1. Một mô hình nội bộ của OpenAI đã bác bỏ giả thuyết tồn tại từ lâu này, cung cấp một họ vô hạn các ví dụ mang lại sự cải thiện theo đa thức (polynomial improvement). Lời chứng minh này đã được kiểm tra bởi một nhóm các nhà toán học độc lập bên ngoài. Họ cũng đã viết một bài báo đồng hành giải thích lập luận, đồng thời cung cấp thêm kiến thức nền và bối cảnh cho tầm quan trọng của kết quả này.

Kết quả này cũng đáng chú ý ở chính cách nó được tìm ra. Lời chứng minh xuất phát từ một mô hình suy luận đa dụng mới, thay vì một hệ thống được huấn luyện chuyên biệt cho toán học, hay được thiết kế thuật toán tìm kiếm qua các chiến lược chứng minh, hoặc nhắm mục tiêu cụ thể vào bài toán khoảng cách đơn vị. Là một phần của nỗ lực rộng lớn hơn nhằm kiểm tra xem các mô hình tiên tiến có thể đóng góp cho nghiên cứu tuyến đầu hay không, chúng tôi đã đánh giá nó trên một tập hợp các bài toán của Erdős. Trong trường hợp này, nó đã đưa ra một lời giải chứng minh trọn vẹn bài toán mở này.

Chứng minh này là một cột mốc quan trọng đối với cả cộng đồng toán học và AI. Nó đánh dấu lần đầu tiên một bài toán mở nổi bật, mang tính trọng tâm của một phân ngành toán học, được giải quyết một cách tự động bởi AI. Nó cũng chứng minh chiều sâu suy luận mà các hệ thống này hiện có thể hỗ trợ. Toán học cung cấp một nền tảng thử nghiệm đặc biệt rõ ràng cho khả năng suy luận: các bài toán rất chính xác, các chứng minh tiềm năng có thể được kiểm tra, và một lập luận dài chỉ có giá trị nếu logic được kết nối chặt chẽ từ đầu đến cuối. Phương pháp giải quyết bài toán cũng rất đáng chú ý. Lời giải đã mang những ý tưởng phức tạp, bất ngờ từ lý thuyết số đại số (algebraic number theory) để áp dụng vào một câu hỏi hình học sơ cấp.

Chủ nhân huy chương Fields Tim Gowers, viết trong bài báo đồng hành, gọi kết quả này là “một cột mốc trong toán học AI.” Theo nhà lý thuyết số hàng đầu Arul Shankar, “Theo ý kiến của tôi, bài báo này chứng minh rằng các mô hình AI hiện tại không chỉ dừng lại ở vai trò trợ lý cho các nhà toán học con người – chúng có khả năng tạo ra những ý tưởng nguyên bản đầy khéo léo, và sau đó đưa chúng đến thành quả cuối cùng”.

Ý kiến của các nhà toán học về kết quả này:

Noga Alon: “Đây là một trong những bài toán yêu thích của Erdős, chính tôi đã nghe ông nhắc đến bài toán này nhiều lần trong các bài giảng của mình. Tôi tin rằng có thể nói công bằng rằng mọi nhà toán học làm việc trong lĩnh vực Hình học Tổ hợp đều đã từng nghĩ về bài toán này, và rất nhiều nhà toán học làm việc ở các lĩnh vực khác cũng đã dành ít nhất một chút thời gian để suy nghĩ về nó… Giải pháp cho bài toán từ mô hình nội bộ của Open AI, theo ý kiến của tôi, là một thành tựu xuất sắc, giải quyết dứt điểm một bài toán mở đã tồn tại từ lâu. Việc đáp án đúng không phải là $n^{1+o(1)}$ là một điều đáng ngạc nhiên, và cách xây dựng cấu hình cùng phân tích của nó đã áp dụng các công cụ khá phức tạp từ lý thuyết số đại số một cách thanh lịch và thông minh.”
Tim Gowers: “Không có nghi ngờ gì rằng giải pháp cho bài toán khoảng cách đơn vị là một cột mốc trong toán học AI: nếu một con người viết bài báo này và gửi cho tờ Annals of Mathematics và tôi được yêu cầu đưa ra ý kiến nhanh, tôi sẽ đề nghị chấp nhận mà không hề do dự. Chưa có chứng minh nào do AI tạo ra trước đây có thể tiến gần đến mức đó.”
Arul Shankar: “Chuỗi suy luận (CoT) của mô hình cực kỳ thú vị. Đáng chú ý là phần lớn các luồng suy nghĩ đều cố gắng xây dựng một phản ví dụ cho giới hạn trên (upper bound) vốn được nhiều người tin tưởng, thay vì cố gắng chứng minh nó. Điều này lập luận rằng mô hình có sự kết hợp của trực giác tốt, sự sẵn sàng thử các phương pháp tiếp cận mà cộng đồng coi là ‘mò kim đáy bể’ (long-shot), và một thiên hướng nỗ lực xây dựng các cấu hình… Theo ý kiến của tôi, bài báo này chứng minh rằng các mô hình AI hiện tại không chỉ là những người trợ lý cho các nhà toán học con người – chúng có khả năng có những ý tưởng nguyên bản khéo léo, và đưa chúng đến kết quả cuối cùng.”
Jacob Tsimerman: “Đây là một tác phẩm thực sự ấn tượng, và tôi sẽ chấp nhận nó cho bất kỳ tạp chí nào mà không ngần ngại. Tôi thực sự đã từng nghiên cứu bài toán này một thời gian ngắn và cố gắng tạo ra một phản ví dụ, nhưng không tiến triển được… Chắc chắn đây là một cấu hình rất đáng sợ để đọc hiểu ngay cả khi bạn biết những gì đang diễn ra, và thậm chí còn khó hơn nhiều để tự mình triển khai.”

Bài toán khoảng cách đơn vị

Cho $u(n)$ là số lượng lớn nhất có thể của các cặp khoảng cách đơn vị trong số $n$ điểm trên mặt phẳng. Rất dễ để xây dựng các ví dụ đạt được tốc độ tăng trưởng tuyến tính: đặt $n$ điểm trên một đường thẳng sẽ cho $n-1$ cặp, trong khi một lưới vuông cho khoảng $2n$ cặp. Cấu hình tốt nhất được biết đến trước đây, xuất phát từ một lưới vuông được thu phóng, hóa ra lại cho nhiều hơn thế: $n^{1 + C / \log \log(n)}$ với $C$ là một hằng số. Vì $\log \log(n)$ tiến đến vô cùng theo $n$ , nên số hạng bổ sung trong số mũ tiến đến 0, có nghĩa là các cấu hình này đạt được tốc độ tăng trưởng chỉ nhanh hơn tuyến tính một chút. Trong nhiều thập kỷ, người ta tin rộng rãi rằng tốc độ này về cơ bản là tốt nhất có thể, và không có cấu hình nào có thể cải thiện đáng kể so với lưới vuông. Về mặt kỹ thuật, Erdős phỏng đoán một giới hạn trên là $n^{1+o(1)}$ trong đó $o(1)$ chỉ ra một số hạng tiến tới 0 theo $n$ .

Kết quả mới của chúng tôi đã bác bỏ giả thuyết này. Chính xác hơn, với vô hạn giá trị của $n$ , lời chứng minh xây dựng các cấu hình gồm $n$ điểm với ít nhất $n^{1+\delta}$ cặp khoảng cách đơn vị, với một số mũ cố định $\delta > 0$ . (Lời chứng minh AI gốc không đưa ra một $\delta$ cụ thể, nhưng một tinh chỉnh sắp tới do giáo sư toán học Will Sawin của Princeton thực hiện đã chỉ ra rằng người ta có thể lấy $\delta=0.014$ ).

Lịch sử của bài toán giúp chúng ta thấy tại sao kết quả này lại đáng kinh ngạc. Giới hạn dưới (lower bound) tốt nhất được biết đến về cơ bản đã không thay đổi kể từ cấu hình nguyên bản năm 1946 của Erdős. Giới hạn trên tốt nhất, $O(n^{4/3})$ , có từ công trình của Spencer, Szemerédi, và Trotter năm 1984, và mặc dù sau đó có những tinh chỉnh và công trình cấu trúc liên quan của Székely, Katz và Silier, Pach, Raz, và Solymosi cùng những người khác, giới hạn trên này về cơ bản vẫn không thay đổi. Như một bằng chứng ủng hộ cho giả thuyết, Matoušek và Alon-Bucić-Sauermann đã nghiên cứu bài toán với các khoảng cách phi Euclid trên mặt phẳng, và chứng minh rằng “phần lớn” các khoảng cách phi Euclid này tuân theo giả thuyết theo một nghĩa nào đó.

Đáng ngạc nhiên là, các thành phần cốt lõi của cấu hình lại đến từ một phần rất khác của toán học được gọi là lý thuyết số đại số, nghiên cứu các khái niệm như phân tích nhân tử trong các phần mở rộng của số nguyên được gọi là các trường số đại số (algebraic number fields).

Những kỹ thuật mới từ lý thuyết số đại số

Ở mức độ tổng quan, lời chứng minh bắt đầu với một ý tưởng hình học quen thuộc và đẩy nó theo một hướng bất ngờ.

Giới hạn dưới ban đầu của Erdős có thể được hiểu thông qua các số nguyên Gauss (Gaussian integers): các số có dạng $a+bi$ , trong đó $a$ và $b$ là các số nguyên và $i$ là căn bậc hai của $-1$ . Số nguyên Gauss mở rộng các số nguyên thông thường và, giống như chúng, có được các đặc tính như phân tích duy nhất thành các số nguyên tố. Những sự mở rộng như vậy của số nguyên hoặc số hữu tỉ thông thường được gọi là các trường số đại số. Lập luận mới thay thế các số nguyên Gauss bằng các dạng tổng quát hóa phức tạp hơn từ lý thuyết số đại số với các tính đối xứng phong phú hơn, có thể tạo ra nhiều hơn đáng kể các hiệu số có độ dài bằng đơn vị.

Lập luận chính xác sử dụng các công cụ như tháp trường lớp vô hạn (infinite class field towers) và lý thuyết Golod–Shafarevich để chứng minh rằng các trường số cần thiết cho lập luận thực sự tồn tại. Những ý tưởng này rất quen thuộc đối với các nhà lý thuyết số đại số, nhưng thật là một bất ngờ lớn khi những khái niệm này lại có ý nghĩa đối với các câu hỏi hình học trong mặt phẳng Euclid.

Ý nghĩa của điều này đối với toán học

Kết quả này đánh dấu một khoảnh khắc quan trọng trong sự tương tác giữa AI và toán học: một hệ thống AI đã tự động giải quyết một bài toán mở tồn tại từ lâu, đóng vai trò trung tâm của một lĩnh vực đang hoạt động tích cực. Nó cũng mang đến cái nhìn thoáng qua sớm về một kiểu hợp tác mới giữa AI và các nhà toán học con người. Trong trường hợp này, công trình đồng hành của các nhà toán học bên ngoài đã vẽ nên một bức tranh phong phú hơn rất nhiều so với chỉ riêng lời giải nguyên bản.

Như Thomas Bloom viết trong ghi chú đồng hành:

“Khi đánh giá tầm quan trọng và sự ảnh hưởng của một chứng minh do AI tạo ra, câu hỏi tôi tự đặt ra cho mình là: điều này có dạy chúng ta điều gì mới về bài toán không? Hiện tại chúng ta có hiểu hình học rời rạc tốt hơn không? Tôi nghĩ câu trả lời là một từ ‘có’ có chừng mực: điều này cho thấy rằng các cấu hình lý thuyết số có nhiều điều để nói về những dạng câu hỏi này hơn chúng ta tưởng; hơn nữa, phần lý thuyết số được yêu cầu có thể rất sâu sắc. Không nghi ngờ gì nữa, nhiều nhà lý thuyết số đại số sẽ xem xét kỹ lưỡng các bài toán mở khác trong hình học rời rạc trong những tháng tới.”

Sự kết nối bất ngờ giữa lý thuyết số đại số và hình học rời rạc được bộc lộ bởi lời giải là một phần khiến kết quả này trở nên đáng chú ý. Nó không đơn thuần giải quyết một giả thuyết cụ thể, mà còn có thể cung cấp cho các nhà toán học một cây cầu để bắt đầu khám phá thêm các bài toán liên quan khác.

Bloom cũng hướng tới một khả năng rộng lớn hơn:

“Ranh giới của tri thức phát triển như những mũi nhọn (rất không đồng đều), và không có gì phải nghi ngờ rằng trong những tháng và năm tới sẽ chứng kiến những thành công tương tự trong nhiều lĩnh vực toán học khác, nơi các bài toán mở tồn tại từ lâu được giải quyết bởi một AI bộc lộ những kết nối bất ngờ và đẩy bộ máy kỹ thuật hiện tại đến giới hạn của nó. AI đang giúp chúng ta khám phá trọn vẹn hơn thánh đường toán học mà chúng ta đã xây dựng qua nhiều thế kỷ; những kỳ quan chưa từng thấy nào khác đang chực chờ phía sau cánh gà?”

Kết quả này cung cấp một ví dụ đầy hứa hẹn: AI không chỉ đóng góp một lời giải, mà còn là một sự khám phá toán học mà ý nghĩa của nó trở nên rõ ràng và phong phú hơn thông qua sự thấu hiểu tiếp nối của con người.

Tại sao điều này lại quan trọng

Bài học rút ra còn lớn hơn kết quả cụ thể này. Khả năng suy luận toán học tốt hơn có thể biến AI thành một đối tác nghiên cứu mạnh mẽ hơn: một thứ có thể gắn kết các luồng tư duy khó nhằn lại với nhau, kết nối các ý tưởng giữa các mảng kiến thức xa lạ, phát hiện ra các con đường đầy hứa hẹn mà các chuyên gia có thể chưa ưu tiên, và giúp các nhà nghiên cứu đạt được tiến bộ trên những bài toán mà nếu không có nó, sẽ quá phức tạp hoặc tốn nhiều thời gian để giải quyết.

Những khả năng đó quan trọng vượt ra ngoài toán học. Nếu một mô hình có thể giữ cho một lập luận phức tạp mạch lạc, kết nối các ý tưởng qua các vùng tri thức xa lạ và tạo ra những công trình vượt qua được sự giám sát của chuyên gia, thì đó cũng là những khả năng hữu ích trong sinh học, vật lý, khoa học vật liệu, kỹ thuật và y học. Và chúng là một phần trong lộ trình dài hạn của chúng tôi hướng tới những nghiên cứu tự động hóa hơn: các hệ thống có thể giúp các nhà khoa học và kỹ sư khám phá nhiều ý tưởng hơn và theo đuổi các câu hỏi kỹ thuật hóc búa hơn.

AI sắp sửa bắt đầu đảm nhận một vai trò rất nghiêm túc trong các phần sáng tạo của nghiên cứu, và quan trọng nhất là trong chính nghiên cứu về AI. Dù tiến bộ này không nằm ngoài dự đoán, nó củng cố thêm tính cấp bách mà chúng tôi cảm nhận được về việc cần phải thấu hiểu giai đoạn phát triển tiếp theo này của AI, những thách thức của việc hiệu chỉnh (aligning) các hệ thống siêu thông minh, và tương lai của sự hợp tác giữa con người và AI.

Tương lai đó vẫn phụ thuộc vào phán đoán của con người. Chuyên môn hóa trở nên có giá trị hơn chứ không phải kém đi. AI có thể giúp tìm kiếm, đề xuất và xác minh. Con người sẽ chọn những bài toán quan trọng, diễn giải các kết quả và quyết định những câu hỏi nào sẽ theo đuổi tiếp theo.

Các đường dẫn tham khảo

[1] https://openai.com/index/model-disproves-discrete-geometry-conjecture/

[2] Will Sawin, An explicit lower bound for the unit distance problem: https://arxiv.org/abs/2605.20579

[3] Noga Alon, Thomas F. Bloom, W. T. Gowers, Daniel Litt, Will Sawin, Arul Shankar, Jacob Tsimerman, Victor Wang, Melanie Matchett Wood Remarks on the disproof of the unit distance conjecture: https://arxiv.org/abs/2605.20695

IMO Shortlist 2024: Combinatorics

Trong bài này tôi sẽ giới thiệu các bài toán tổ hợp trong cuốn IMO Shortlist 2024, các bài toán từ IMO SL năm trước các bạn có thể tìm ở https://nttuan.org/category/contests/imo-shortlist/ .

Các phần khác của bộ 2024 tôi đã đăng ở đây

A. https://nttuan.org/2025/09/03/isl2024a/

G. https://nttuan.org/2025/08/07/isl2024g/

N. https://nttuan.org/2025/11/14/isl2024n/

C1. https://artofproblemsolving.com/community/c6h3610442p35340913

Cho $n$ là một số nguyên dương. Một lớp gồm $n$ học sinh chạy $n$ cuộc đua, trong mỗi cuộc đua họ được xếp hạng mà không có hòa. Một học sinh đủ điều kiện để nhận điểm đánh giá $(a, b)$ với $a$ và $b$ là các số nguyên dương, nếu họ về đích trong $b$ vị trí dẫn đầu ở ít nhất $a$ cuộc đua. Điểm số cuối cùng của họ là giá trị lớn nhất có thể của $a-b$ trên tất cả các điểm đánh giá mà họ đủ điều kiện. Tìm tổng lớn nhất có thể của tất cả các điểm số của $n$ học sinh.

C2. https://artofproblemsolving.com/community/c6h3610436p35340903

Cho $n$ là một số nguyên dương. Các số nguyên $1, 2, 3, \ldots, n^2$ được điền vào các ô của bảng $n \times n$ sao cho mỗi số nguyên được điền vào đúng một ô và mỗi ô chứa đúng một số nguyên. Với mỗi số nguyên $d$ sao cho $d\mid n$ , phép $d$ -chia của bảng là phép chia bảng thành $(n/d)^2$ bảng con không chồng nhau, mỗi bảng con có kích thước $d \times d$ , sao cho mỗi ô được chứa trong đúng một bảng con $d \times d$ . Ta nói rằng $n$ là một số đẹp nếu các số nguyên có thể được điền vào bảng $n \times n$ sao cho, với mỗi số nguyên $d$ với $d\mid n$ và $1 < d < n$ , trong phép $d$ -chia của bảng, tổng các số nguyên được điền trong mỗi bảng con $d \times d$ không chia hết cho $d$ . Hãy xác định tất cả các số đẹp chẵn.

C3. https://artofproblemsolving.com/community/c6h3610441p35340911

Cho $n$ là một số nguyên dương. Có $2n$ hiệp sĩ ngồi quanh một bàn tròn. Họ gồm $n$ cặp đối tác, mỗi cặp muốn bắt tay nhau. Một cặp chỉ có thể bắt tay khi họ ngồi cạnh nhau. Mỗi phút, một cặp hiệp sĩ ngồi cạnh nhau đổi chỗ. Tìm số lần đổi chỗ nhỏ nhất giữa các hiệp sĩ ngồi cạnh nhau sao cho, bất kể cách sắp xếp ban đầu thế nào, mỗi hiệp sĩ đều có thể gặp đối tác của mình và bắt tay tại một thời điểm nào đó.

C4. https://artofproblemsolving.com/community/c6h3359777p31218774

Trên một bảng có $2024$ hàng và $2023$ cột, Ốc sên Turbo cố gắng di chuyển từ hàng đầu tiên đến hàng cuối cùng. Trong mỗi lần thử, nó chọn bắt đầu ở bất kỳ ô nào trong hàng đầu tiên, sau đó di chuyển từng bước đến một ô liền kề chung cạnh. Nó thắng nếu đạt đến bất kỳ ô nào trong hàng cuối cùng. Tuy nhiên, có $2022$ quái vật đã được xác định trước và giấu kín trong $2022$ ô, mỗi hàng có một con trừ hàng đầu tiên và hàng cuối cùng, sao cho không có hai quái vật nào nằm cùng một cột. Nếu không may Turbo đến ô có quái vật, lần thử của nó kết thúc và nó được đưa trở lại hàng đầu tiên để bắt đầu một lần thử mới. Các quái vật không di chuyển. Giả sử Turbo được phép thực hiện $n$ lần thử. Xác định giá trị nhỏ nhất của $n$ sao cho nó có một chiến lược đảm bảo đến được hàng cuối cùng, bất kể vị trí của các quái vật thế nào. (IMO2024/5)

C5. https://artofproblemsolving.com/community/c6h3610469p35340978

Cho $N$ là một số nguyên dương. Geoff và Ceri chơi một trò chơi mà họ bắt đầu bằng cách viết các số $1, 2, \ldots, N$ lên bảng. Sau đó họ luân phiên thực hiện một nước đi, bắt đầu từ Geoff. Mỗi nước đi bao gồm việc chọn một cặp số nguyên $(k, n)$ , trong đó $k \ge 0$ và $n$ là một trong các số nguyên trên bảng, sau đó xóa mọi số nguyên $s$ trên bảng sao cho $2^k \mid n-s$ . Trò chơi tiếp tục cho đến khi bảng trống. Người chơi xóa số nguyên cuối cùng trên bảng sẽ thua. Xác định tất cả các giá trị của $N$ mà Geoff có thể đảm bảo thắng, bất kể Ceri chơi như thế nào.

C6. https://artofproblemsolving.com/community/c6h3610456p35340931

Cho $n$ và $T$ là các số nguyên dương. James có $4n$ viên bi với khối lượng $1, 2, \ldots, 4n$ . Anh ấy đặt chúng lên một chiếc cân thăng bằng sao cho hai bên có khối lượng bằng nhau. Andrew có thể di chuyển một viên bi từ bên này sang bên kia của chiếc cân, sao cho độ chênh lệch về khối lượng của hai bên luôn không quá $T$ . Tìm, theo $n$ , số nguyên dương $T$ nhỏ nhất sao cho Andrew có thể thực hiện một chuỗi các nước đi để mỗi viên bi cuối cùng nằm ở phía đối diện của chiếc cân, bất kể cách James đặt bi ban đầu như thế nào.

C7. https://artofproblemsolving.com/community/c6h3358930p31206050

Cho dãy vô hạn các số nguyên dương $(a_n){n\geq 1}$ và số nguyên dương $N$ . Giả sử với mọi số nguyên $n>N$ , $a_n$ bằng số lần xuất hiện của $a_{n-1}$ trong dãy số $a_1$ , $a_2$ , $\ldots$ , $a_{n-1}$ . Chứng minh rằng một trong hai dãy số $(a_{2n-1})_{n\geq 1}$ và $(a_{2n})_{n\geq 1}$ là tuần hoàn kể từ lúc nào đó. (IMO2024/3)

C8. https://artofproblemsolving.com/community/c6h3610448p35340921

Cho $n$ là một số nguyên dương. Cho một bảng $n \times n$ , ô đơn vị ở góc trên bên trái ban đầu được tô màu đen, và các ô khác được tô màu trắng. Sau đó, ta áp dụng một chuỗi các thao tác tô màu lên bảng. Trong mỗi thao tác, ta chọn một hình vuông $2 \times 2$ có đúng một ô màu đen và ta tô ba ô còn lại của hình vuông $2 \times 2$ đó thành màu đen. Xác định tất cả các giá trị của $n$ sao cho ta có thể tô toàn bộ bảng thành màu đen.

Formal power series

Định nghĩa 1. Một chuỗi lũy thừa hình thức là một biểu diễn có dạng

$a_0+a_1x+a_2x^2+a_3x^3+\ldots,$

hay gọn hơn $\displaystyle\sum_{k=0}^{\infty}a_kx^k.$ Trong đó $(a_n)_{n\geq 0}$ là một dãy các số phức. Các $a_i$ được gọi là các hệ số của chuỗi lũy thừa hình thức, $a_0$ được gọi là hệ số tự do của chuỗi lũy thừa hình thức.

Từ “hình thức” trong định nghĩa trên có nghĩa là ta không bận tâm đến việc cho $x$ các giá trị đặc biệt, ta cũng không quan tâm đến tính hội tụ hay phân kỳ của chuỗi. Tập tất cả các chuỗi lũy thừa hình thức với hệ số thuộc một tập hợp $A$ được ký hiệu bởi $A[[x]]$ . Với một chuỗi lũy thừa hình thức $a(x)$ , ta ký hiệu hệ số của $x^n$ trong chuỗi này bởi $[x^n]a(x)$ .

Nếu $a_i=0$ với mọi $i>m$ thì để cho gọn, chuỗi $\sum_{n=0}^{\infty}a_nx^n$ sẽ được viết là

$a_0+a_1x+\ldots+a_mx^m.$

Chuỗi lũy thừa hình thức với tất cả các hệ số bằng $0$ được gọi là chuỗi không, ký hiệu là $0$ . Tổng và tích của hai chuỗi lũy thừa hình thức $\displaystyle\sum_{n=0}^{\infty}a_nx^n$ và $\displaystyle\sum_{n=0}^{\infty}b_nx^n$ được định nghĩa bởi

$\displaystyle\sum_{n=0}^{\infty}a_nx^n+\sum_{n=0}^{\infty}b_nx^n=\sum_{n=0}^{\infty}(a_n+b_n)x^n$

và

$\displaystyle\left(\sum_{n=0}^{\infty}a_nx^n\right)\left(\sum_{n=0}^{\infty}b_nx^n\right)=\sum_{n=0}^{\infty}\left(\sum_{k=0}^na_kb_{n-k}\right)x^n.$

Với hai phép toán này thì $\mathbb{C}[[x]]$ là một vành giao hoán có đơn vị là chuỗi đơn vị $1+0x^1+0x^2+0x^3+\ldots,$ ký hiệu là $1$ .

Tương tự như với các số phức, ta có kết quả sau:

Định lý 1. Nếu $a$ và $b$ là các phần tử khác không của $\mathbb{C}[[x]]$ , thì chuỗi tích $ab$ cũng khác chuỗi không.

Chứng minh. Gọi $m$ là số tự nhiên nhỏ nhất sao cho $[x^m]a\not=0$ , và $n$ là số tự nhiên nhỏ nhất sao cho $[x^n]b\not=0$ . Khi đó

$[x^{m+n}](ab)=([x^m]a)([x^n]b)\not=0,$

suy ra $ab$ khác chuỗi không. $\Box$

Khác với phép nhân trong tập các số phức, không phải mọi chuỗi khác không đều có nghịch đảo. Chẳng hạn, khi $a(x)=0+x+0x^2+0x^3+\ldots,$ (chuỗi này thường được viết là $a(x)=x$ ) thì $a(x)\not=0$ nhưng không có chuỗi $b(x)$ để $a(x)b(x)=1$ .

Định lý 2. Chuỗi $a(x)$ có nghịch đảo khi và chỉ khi $[x^0]a(x)\not=0$ .

Chứng minh. Giả sử chuỗi $a(x)$ có nghịch đảo, và $b(x)$ là nghịch đảo của nó. Khi đó

$1=[x^0](ab)=([x^0]a)([x^0]b),$

suy ra $[x^0]a(x)\not=0$ .

Bây giờ giả sử $\displaystyle a(x)=\sum_{n=0}^{\infty}a_nx^n$ là một chuỗi lũy thừa hình thức có $a_0=[x^0]a(x)\not=0$ . Chuỗi lũy thừa hình thức $\displaystyle b(x)=\sum_{n=0}^{\infty}b_nx^n$ là nghịch đảo của $a(x)$ khi và chỉ khi $a_0b_0=1$ và

$\displaystyle\sum _{k=0}^na_kb_{n-k}=0,\quad\forall n\geq 1.$

Từ hệ này ta có thể xác định $b(x)$ bởi $b_0=1/a_0$ và

$\displaystyle b_n=-\frac{1}{a_0}\sum _{k=1}^na_kb_{n-k},\quad\forall n\geq 1.$ $\Box$

Khi $a$ là một chuỗi có nghịch đảo thì ta ký hiệu chuỗi nghịch đảo của nó bởi $a^{-1}$ . Tích của chuỗi $b$ và chuỗi $a^{-1}$ thường được viết là $\frac{b}{a}$ .

Ví dụ. Chuỗi lũy thừa hình thức $1-x$ có nghịch đảo là chuỗi

$\displaystyle \frac{1}{1-x}=1+x+x^2+x^3+\ldots$

Định nghĩa 2. Dãy các chuỗi lũy thừa hình thức với hệ số phức $\{S_n(x)\}_{n\geq 1}$ được gọi là hội tụ đến chuỗi lũy thừa hình thức với hệ số phức $S(x)$ , ký hiệu $\displaystyle\lim_{n\to\infty} S_n(x)=S(x)$ , nếu với mỗi $n\geq 0$ có số nguyên dương $N$ sao cho $[x^n]S_i(x)=[x^n]S(x)$ mỗi khi $i\geq N$ . Trong trường hợp này ta nói $\{S_n(x)\}_{n\geq 1}$ là một dãy hội tụ.

Khi $\displaystyle A(x)=\sum_{n\geq 0}a_nx^n$ là một phần tử khác không của $\mathbb{C}[[x]]$ , ta gọi bậc của $A(x)$ , ký hiệu $\deg A(x)$ , là số $n$ nhỏ nhất sao cho $a_n\not=0$ . Dễ thấy nếu $B(x)$ và $C(x)$ là các phần tử khác không của $\mathbb{C}[[x]]$ thì $B(x)C(x)$ cũng là một phần tử khác không của $\mathbb{C}[[x]]$ , và

$\deg B(x)C(x)=\deg B(x)+\deg C(x).$

Ta quy ước $\deg 0=\infty$ . Sử dụng bậc của một chuỗi lũy thừa hình thức ta có một định nghĩa khác của tính hội tụ của dãy các chuỗi lũy thừa hình thức.

Continue reading →

IMO Shortlist 2023: Combinatorics

Hình học : https://nttuan.org/2024/11/02/isl2023-geometry/

Đại số: https://nttuan.org/2025/01/23/isl2023-algebra/

Số học: https://nttuan.org/2025/02/13/isl2023-number-theory/

C1. https://artofproblemsolving.com/community/c6h3359749p31218491

Cho $m$ và $n$ là các số nguyên lớn hơn $1$ . Trong mỗi ô vuông đơn vị của lưới $m\times n$ có một đồng xu với mặt trái hướng lên trên. Một phép toán bao gồm các bước sau.

chọn một hình vuông $2\times 2$ trong lưới;
lật các đồng xu ở ô đơn vị trên cùng bên trái và dưới cùng bên phải;
lật đồng xu ở ô vuông đơn vị trên cùng bên phải hoặc dưới cùng bên trái.

Xác định tất cả các cặp $(m,n)$ sao cho mọi đồng xu đều hiện mặt phải sau một số hữu hạn lần thực hiện phép toán.

C2. https://artofproblemsolving.com/community/c6h3359755p31218537

Xác định số nguyên dương $L$ lớn nhất sao cho tồn tại một dãy các số nguyên dương $a_1,\dots,a_L$ có tính chất: mỗi số hạng của dãy không lớn hơn $2^{2023}$ , và không có các số hạng liên tiếp $a_i,a_{i+1},\dots,a_j$ (ở đây $1\le i\le j\le L$ ) với một cách chọn dấu $s_i,s_{i+1},\dots,s_j\in\{1,-1\}$ để

$s_ia_i+s_{i+1}a_{i+1}+\dots+s_ja_j=0.$

C3. https://artofproblemsolving.com/community/c6h3107350p28104367

Cho $n$ là một số nguyên dương. Một tam giác Nhật Bản gồm $1+2+\cdots+n$ hình tròn được xếp thành một hình tam giác đều sao cho với mỗi $i = 1, 2, ..., n$ , hàng thứ $i$ có đúng $i$ hình tròn và trên hàng đó có đúng một hình tròn được tô màu đỏ. Một đường đi ninja trong một tam giác Nhật Bản là một dãy gồm $n$ hình tròn nhận được bằng cách xuất phát từ hàng trên cùng, đi lần lượt từ một hình tròn xuống một trong hai hình tròn ngay dưới nó, và kết thúc tại hàng dưới cùng. Trong hình vẽ là một tam giác Nhật Bản với $n = 6$ và một đường đi ninja có chứa hai hình tròn màu đỏ.

Như một hàm số của $n$ , tìm giá trị lớn nhất của $k$ sao cho trong mỗi tam giác Nhật Bản luôn có một đường đi ninja chứa ít nhất $k$ hình tròn màu đỏ. (IMO2023/5)

C4. https://artofproblemsolving.com/community/c6h3359724p31218375

Cho $n\geqslant 2$ là một số nguyên dương. Paul có một dải hình chữ nhật cỡ $1\times n^2$ gồm $n^2$ hình vuông đơn vị, trong đó hình vuông thứ $i$ được gắn nhãn $i$ với mọi $1\leqslant i\leqslant n^2$ . Anh ta muốn cắt dải giấy thành nhiều mảnh, trong đó mỗi mảnh bao gồm một số ô vuông đơn vị liên tiếp, sau đó dịch chuyển (không xoay hoặc lật) các mảnh để thu được hình vuông $n\times n$ thỏa mãn tính chất sau: nếu hình vuông đơn vị trong hàng $i$ và cột $j$ được gắn nhãn $a_{ij}$ , thì $a_{ij}-(i+j -1)$ chia hết cho $n$ .

Xác định số mảnh nhỏ nhất mà Paul cần tạo để hoàn thành việc này.

C5. https://artofproblemsolving.com/community/c6h3359765p31218619

Elisa có $latex $2023$ rương kho báu, tất cả đều được mở khóa và trống rỗng lúc đầu. Mỗi ngày, Elisa thêm một viên đá quý mới vào một trong những chiếc rương đã mở khóa mà cô ấy chọn, và sau đó, một cô tiên sẽ hành động theo các quy tắc sau:

nếu có nhiều hơn một rương được mở khóa, cô sẽ khóa một trong số chúng, hoặc
nếu chỉ có một rương được mở khóa, cô sẽ mở khóa tất cả các rương.

Cho rằng quá trình này diễn ra mãi mãi, hãy chứng minh rằng tồn tại một hằng số $C$ với tính chất sau: Elisa có thể đảm bảo rằng chênh lệch giữa số viên ngọc trong hai rương bất kỳ không bao giờ vượt quá $latex $C$, bất kể cô tiên hành động như thế nào.

C6. https://artofproblemsolving.com/community/c6h3359747p31218478

Cho $N$ là một số nguyên dương và xét một lưới $N \times N$ các ô vuông. Đường dẫn xuống bên phải là một dãy các ô lưới sao cho mỗi ô là một ô ở bên phải hoặc một ô bên dưới ô trước đó trong chuỗi. Đường dẫn lên bên phải là một chuỗi các ô lưới sao cho mỗi ô là một ô ở bên phải hoặc một ô phía trên ô trước đó trong chuỗi.

Chứng minh rằng không thể phân chia các ô của lưới $N \times N$ thành ít hơn $N$ vùng sao cho mỗi vùng là một đường dẫn xuống bên phải xuống hoặc một đường dẫn lên bên phải.

Chẳng hạn, lưới $5 \times 5$ có thể phân chia thành $5$ vùng như hình vẽ.

C7. https://artofproblemsolving.com/community/c6h3359751p31218524

Quần đảo Imomi bao gồm $n\geq 2$ hòn đảo. Giữa mỗi cặp đảo khác nhau có một tuyến phà duy nhất chạy theo cả hai hướng và mỗi tuyến phà được điều hành bởi một trong $k$ công ty. Được biết, nếu bất kỳ công ty nào đóng cửa tất cả các tuyến phà của mình thì một du khách, bất kể bắt đầu từ đâu, sẽ không thể ghé thăm tất cả các hòn đảo đúng một lần (đặc biệt là không quay lại hòn đảo mà du khách bắt đầu). Xác định giá trị lớn nhất có thể có của $k$ theo $n$ .

Ramsey numbers

Các bạn đọc lại các bài sau để theo dõi cho dễ:

[1] https://nttuan.org/2024/01/24/naive-definition-of-probability/

[2] https://nttuan.org/2024/06/02/probability-space/

[3] https://nttuan.org/2023/09/01/graph02/

—

Trong khi chuẩn bị cho các kỳ thi chọn học sinh giỏi, các bạn học sinh có lẽ đã gặp ví dụ sau nhiều lần.

Ví dụ 1. Trong mỗi nhóm sáu người luôn có ba người đôi một quen nhau hoặc đôi một không quen nhau.

Lời giải. Gọi $A$ là một người trong nhóm sáu người ta đang quan tâm. Vì với mỗi một trong năm người còn lại, $A$ sẽ quen hoặc không quen người đó, suy ra trong năm người còn lại ta tìm được ba người, gọi là $B$ , $C$ , $D$ , mà $A$ cùng quen hoặc cùng không quen họ. Giả sử mà không làm mất tính tổng quát rằng $A$ quen cả ba người $B$ , $C$ , và $D$ . Nếu trong $B$ , $C$ , và $D$ có hai người quen nhau, chẳng hạn là $B$ và $C$ thì ba người $A$ , $B$ , và $C$ đôi một quen nhau. Nếu không, $B$ , $C$ , và $D$ đôi một không quen nhau. $\Box$

Chứng minh là ví dụ đầu tiên của lý thuyết Ramsey. Không khó khăn lắm ta thấy với một nhóm ít hơn sáu người thì kết luận không còn đúng.

Bây giờ cho mỗi người ứng với một đỉnh của đồ thị đầy đủ $K_6$ trên sáu đỉnh. Hai người được nối với nhau bởi một cạnh đỏ nếu họ quen nhau, được nối với nhau bởi một cạnh xanh nếu họ không quen nhau. Theo ví dụ trên thì với mọi cách tô các cạnh của $K_6$ bởi hai màu, luôn có $K_3$ mà các cạnh của nó mang cùng một màu. Hơn nữa, kết luận không còn đúng nếu thay $K_6$ bởi $K_n$ với $n<6$ . Kết quả sẽ thay đổi thế nào nếu thay $K_3$ bởi $K_{\alpha}$ ? Ta xét bài toán tổng quát sau:

Bài toán. Cho một số nguyên dương $\alpha$ . Tồn tại hay không số nguyên dương $n$ có tính chất: Với mỗi cách tô màu các cạnh của $K_n$ bởi hai màu, luôn có $K_{\alpha}$ mà các cạnh mang cùng một màu. Số nguyên dương $n$ nhỏ nhất có tính chất này bằng bao nhiêu?

Với câu hỏi đầu tiên thì định lý tổng quát sau cho câu trả lời là tồn tại. Câu hỏi thứ hai rất khó, hiện tại ta không thể tính được $n$ như một hàm của $\alpha$ trong tình huống tổng quát mà chỉ có thể ước lượng nó.

Định lý 1 (Ramsey). Cho $s$ và $t$ là hai số nguyên lớn hơn $1$ . Khi đó tồn tại số nguyên dương $n$ có tính chất: Với mỗi cách tô màu các cạnh của $K_n$ bởi hai màu xanh và đỏ, $K_n$ có đồ thị con $K_s$ với các cạnh xanh hoặc có đồ thị con $K_t$ với các cạnh đỏ. Nếu ký hiệu $R(s,t)$ là số nguyên dương $n$ nhỏ nhất có tính chất này thì

$R(s,t)\leq R(s,t-1)+R(s-1,t)$

mỗi khi $s$ và $t$ lớn hơn $2$ .

Các số $R(s,t)$ được gọi là các số Ramsey. Phần thảo luận lúc đầu cho ta biết $R(3,3)=6$ . Từ bất đẳng thức trên ta có thể tìm được một cận trên của các số Ramsey. Mục đính chính của bài là dùng phương pháp xác suất đưa ra một cận dưới của các số $R(k,k)$ , chúng được gọi là các số Ramsey đối xứng.

Chứng minh. Ta chứng minh bằng quy nạp theo $s$ và $t$ . Lập luận đơn giản ta thu được $R(k,2)$ , $R(2,k)$ đều tồn tại và bằng $k$ với mọi $k>1$ .

Bây giờ giả sử $R(s,t-1)$ và $R(s-1,t)$ đều tồn tại, ở đây $s$ và $t$ là các số nguyên lớn hơn $2$ . Đặt $\alpha=R(s,t-1)+R(s-1,t)$ . Xét một cách tô màu các cạnh của $K_{\alpha}$ bởi một trong hai màu xanh và đỏ. Gọi $v$ là một đỉnh của $K_{\alpha}$ . Mỗi một trong $\alpha-1$ đỉnh còn lại của $K_{\alpha}$ được nối với $v$ bởi một cạnh xanh hoặc đỏ. Suy ra, trong các đỉnh này có $R(s-1,t)$ đỉnh được nối với $v$ bởi cạnh xanh, hoặc có $R(s,t-1)$ đỉnh được nối với $v$ bởi cạnh đỏ. Ta xét tình huống thứ nhất, tình huống còn lại được lập luận hoàn toàn tương tự. Xem $R(s-1,t)$ đỉnh như một đồ thị đầy đủ. Theo giả thiết quy nạp, trong đồ thị đầy đủ này có $K_{s-1}$ với các cạnh xanh hoặc $K_t$ với các cạnh đỏ. Nếu có $K_t$ với các cạnh đỏ thì ta có điều phải chứng minh, nếu có $K_{s-1}$ với các cạnh xanh thì thêm $v$ vào ta có đồ thị con $K_s$ của $K_{\alpha}$ với các cạnh xanh, và ta cũng có điều cần chứng minh. $\Box$

Định lý 2. Với mỗi số nguyên $k>3$ , ta có $R(k,k)>2^{k/2}$ .

Chứng minh (của Paul Erdos). Xét một số nguyên $n$ thỏa mãn $k\leq n\leq 2^{k/2}$ . Định lý sẽ được chứng minh nếu ta chỉ ra rằng tồn tại một cách tô màu các cạnh của $K_n$ bởi hai màu xanh và đỏ, sao cho trong $K_n$ không có $K_k$ với các cạnh cùng màu.

Tô màu mỗi cạnh của $K_n$ bởi một trong hai màu xanh và đỏ một cách ngẫu nhiên. Như vậy ta có một không gian xác suất rời rạc với không gian mẫu $\Omega$ là tập tất cả các cách tô màu, và với mỗi biến cố $A$ , xác suất xảy ra $A$ bằng $\mid A\mid /\mid\Omega\mid$ .

Gọi $X$ là biến cố: trong $K_n$ không có $K_k$ với các cạnh cùng màu. Ta cần chứng $\mathbb{P}(X)>0$ . Với mỗi đồ thị con đầy đủ trên $k$ đỉnh của $K_n$ , gọi $Y_{\alpha}$ là biến cố: $\alpha$ có các cạnh cùng màu. Khi đó

$\displaystyle\mathbb{P}(Y_{\alpha})=\frac{\mid Y_{\alpha}\mid }{\mid \Omega\mid}=\frac{2\cdot 2^{C_n^2-C_k^2}}{2^{C_n^2}}=2^{1-C_k^2},$

do đó

$\mathbb{P}(X)=1-\mathbb{P}(\overline{X}) =1-\mathbb{P}\left(\bigcup_{\alpha}Y_{\alpha}\right)\geq 1-\sum_{\alpha}\mathbb{P}(Y_{\alpha})=1-C_n^k2^{1-C_k^2}.$

Mà ta lại có

$\displaystyle C_n^k2^{1-C_k^2}<\frac{n^k}{k!}\cdot 2^{1-C_k^2}\leq \frac{2^{k^2/2}}{k!}\cdot 2^{1-C_k^2}=\frac{2^{1+\frac{k}{2}}}{k!}< 1,$

suy ra $\mathbb{P}(X)>0$ . $\Box$