Bài toán emoji (2022)
(artofproblemsolving.com)- Xem một biến thể của câu đố công thức trái cây·emoji trên Internet như một phương trình Diophantine nguyên, và lần theo quá trình tạo ra nghiệm nguyên dương
- Công cụ cốt lõi là phương pháp hình học: thay vì tìm thẳng nghiệm nguyên, trước hết tìm điểm hữu tỉ, rồi tạo điểm hữu tỉ mới bằng đường thẳng hoặc tiếp tuyến
- Sau các phép thay biến và xoay, phương trình trở thành một đường cong elliptic đối xứng, nhưng những điểm dễ thấy ban đầu không dẫn ngay đến nghiệm dương của bài toán gốc
- Trên đường cong elliptic, đường thẳng nối hai điểm hữu tỉ hoặc tiếp tuyến tại một điểm tạo ra giao điểm thứ ba, và nhờ công thức Vieta, điểm đó cũng vẫn là điểm hữu tỉ
- Sau khi dùng Mathematica để tìm một điểm ít hiển nhiên hơn và lặp lại các phép toán, tác giả xây dựng được một nghiệm nguyên dương khổng lồ khả dĩ khi đổi trở lại các biến ban đầu
Quá trình một câu đố emoji trên Internet biến thành bài toán toán học
- Trên Internet từng lan truyền rộng rãi các câu đố công thức emoji được thiết kế để khiến người giải nhầm lẫn chi tiết, chẳng hạn số quả chuối, từ đó cho ra các đáp án khác nhau
- Đầu năm 2017, trên r/math xuất hiện một reddit thread với nội dung đại ý là đã chán các câu đố toán trái cây kiểu Facebook, và một người dùng đã tạo ra một bài khó hơn dùng hình trái cây
- Khi Sridhar Ramesh chỉnh sửa nhẹ bài toán đó và lan truyền rộng rãi, nó trở thành một bài toán tai tiếng với nghiệm tối thiểu rất dài và được cho là cần kiến thức về đường cong elliptic
- Mục tiêu là thực sự giải biến thể bài toán emoji đó
Ví dụ chuẩn bị: bộ ba Pythagore và điểm hữu tỉ
- Trước hết, bài toán tìm bộ ba Pythagore được dùng làm ví dụ dễ hơn
- Thay vì tìm trực tiếp nghiệm nguyên, nếu chuyển thành bài toán tìm điểm hữu tỉ trên đường tròn đơn vị tương ứng thì cấu trúc sẽ đơn giản hơn
- Bắt đầu từ một điểm hữu tỉ trên đường tròn đơn vị và vẽ một đường thẳng có hệ số góc hữu tỉ, điểm thứ hai nơi đường thẳng cắt đường tròn cũng là điểm hữu tỉ
- Khi tìm giao điểm của đường thẳng và đường tròn, ta thu được một phương trình bậc hai
- Vì các hệ số là số hữu tỉ và một nghiệm đã là số hữu tỉ, theo công thức Vieta nghiệm còn lại cũng là số hữu tỉ
- Ngược lại, với bất kỳ điểm hữu tỉ nào khác trên đường tròn đơn vị, hệ số góc của đường thẳng nối điểm đó với điểm xuất phát là số hữu tỉ, nên có thể thu được mọi điểm hữu tỉ theo cùng cách
- Quá trình này dẫn đến dạng chuẩn biểu diễn mọi bộ ba Pythagore bằng hai số nguyên dương và một bội số
- Mẫu hình quan trọng là cách dùng đường thẳng để thu được điểm mới, và bài toán emoji gốc cũng dùng ý tưởng tương tự
Biến phương trình gốc thành đường cong elliptic
- Sau khi khử mẫu, phương trình của bài toán emoji được chuyển thành bài toán tìm điểm hữu tỉ theo tỉ lệ giữa các biến, thay vì tìm nghiệm nguyên
- Không tìm ngay nghiệm nguyên dương, mà trước hết khảo sát toàn bộ các điểm hữu tỉ, bao gồm cả số dương và số âm
- Đồ thị không đổi khi hoán đổi hai biến, nên có tính đối xứng nghiêng
- Để thuận tiện, tác giả dùng phép thay biến để xoay đồ thị thành dạng đối xứng qua các trục, và gọi đường cong này là đường cong elliptic
- Trên đồ thị có những điểm hữu tỉ dễ nhìn thấy bằng mắt, nhưng chúng không tương ứng với nghiệm dương hợp lệ của bài toán gốc
- Vì vậy cần lấy các điểm dễ đó làm điểm xuất phát để tạo thêm nhiều điểm hữu tỉ hơn
Mẹo đường thẳng cũng hoạt động trên đường cong elliptic
- Nếu vẽ đường thẳng nối hai điểm hữu tỉ (P), (Q) trên đường cong elliptic, đường thẳng đó sẽ cắt đường cong tại điểm thứ ba (R)
- Giao điểm thứ ba này cũng là điểm hữu tỉ
- Thay phương trình đường thẳng vào phương trình đường cong elliptic sẽ cho một phương trình bậc ba theo một biến
- Các hệ số của phương trình bậc ba là số hữu tỉ
- Vì hai nghiệm đã biết là số hữu tỉ đến từ tọa độ của (P), (Q), nên theo công thức Vieta, nghiệm thứ ba cũng là số hữu tỉ
- Thay ngược lại vào phương trình đường thẳng, tọa độ còn lại cũng được xác định là số hữu tỉ
- Trường hợp (P=Q) thì thay vì đường thẳng nối hai điểm, dùng tiếp tuyến tại điểm đó, và giao điểm được tính cả theo bội số
- Dù nối các điểm dễ tìm ban đầu hoặc vẽ tiếp tuyến, ta chỉ lặp lại vài điểm và không mở rộng được sang điểm mới hữu ích
- Các điểm này là torsion point, nên dù lặp lại cùng mẹo đường thẳng cũng không thể thoát ra điểm mới nữa
Tìm điểm hữu tỉ trong vùng hợp lệ
- Tác giả dùng Mathematica để tìm kiếm các điểm hữu tỉ ít hiển nhiên hơn trên đường cong elliptic, và một trong số đó được dùng cho các tính toán sau
- Mục tiêu không phải là một điểm hữu tỉ tùy ý, mà là điểm mà khi đổi trở lại các biến ban đầu thì cả ba giá trị đều dương
- Nếu mọi biến đều âm thì có thể đảo toàn bộ dấu để thu được nghiệm dương, nên đặt một biến là dương rồi truy ngược điều kiện
- Điều kiện này xuất hiện dưới dạng một vùng màu xanh lá cụ thể trên mặt phẳng tọa độ đã biến đổi, và cần đưa một điểm hữu tỉ trên đường cong elliptic vào bên trong vùng đó
- Tính tay rất phiền phức, nên tác giả dùng Mathematica để tính các công thức tọa độ giao điểm sinh ra từ các phép toán đường thẳng·tiếp tuyến
- Các công thức tọa độ được tạo cho giao điểm thứ ba của đường thẳng nối hai điểm và giao điểm thứ ba do tiếp tuyến tại một điểm tạo ra; các biểu thức trở nên rất phức tạp và các con số cũng phình to
Cấu dựng nghiệm nguyên dương cuối cùng
- Từ điểm hữu tỉ xuất phát, vẽ tiếp tuyến để thu được điểm mới, rồi tiếp tục vẽ tiếp tuyến tại điểm đó để thu được điểm kế tiếp, lặp lại quá trình này
- Sau vài phép toán tiếp tuyến mà vẫn chưa đi thẳng vào vùng mục tiêu, tác giả tiếp tục nối với một điểm thu được bằng cách đổi dấu tọa độ của một điểm, tạo ra một điểm khác
- Cuối cùng, bằng cách nối một điểm hữu tỉ “tốt” đã để dành từ trước với điểm có tọa độ lớn vừa thu được, tác giả rốt cuộc chạm tới một điểm hữu tỉ nằm trong vùng màu xanh lá mục tiêu
- Đổi điểm hữu tỉ cuối cùng này trở lại các biến ban đầu và nhân với bội chung nhỏ nhất của các mẫu số để cấu dựng nghiệm nguyên dương
- Phần kiểm tra cuối xác nhận nghiệm nguyên khổng lồ được cấu dựng thỏa mãn phương trình của bài toán emoji gốc
1 bình luận
Ý kiến trên Hacker News
Chỉ là thay vì dùng thứ như
xthì tôi dùng những cái tên như đám mây bông, ngôi sao, và bọn trẻ dù có khó chịu vẫn giữ được hứng thú, sau đó còn làm y như vậy khi giúp bạn bèTa rất dễ quên cảm giác khi lần đầu học trừu tượng hóa, nhưng điều quan trọng là cho thấy
xchẳng có gì đặc biệt cả, nó cũng có thể là mặt trời, hoặc một cụm như “tổng số con mèo”Nhưng khi được xuất bản về sau thì độ dễ đọc thực sự rất tệ. Kiểu như “có một hạng tử đóng vai trò lớn trong biểu thức này, mà rốt cuộc nó nghĩa là gì? Ai đó gắn nhãn nó là
φnên chẳng biết nữa”Tôi hay đùa rằng nếu bạn nghĩ lập trình viên đặt tên dở thì hãy nhìn các nhà toán học. Họ có một niềm tự hào kỳ lạ về khả năng đặt tên tệ
Tệ nhất là những chương trình được suy ra trực tiếp từ bài báo toán học. Nếu biến chứa hệ số tương quan thì cứ gọi nó như thế. Chúng ta có hàng nghìn năm ngôn ngữ và ký hiệu để chia sẻ ý tưởng, đừng mã hóa nó rồi gọi là
rhoNhưng thực tế lại thành ra thế này: https://chatgpt.com/share/682cce62-c53c-8003-be2c-2929395868...
Tóm lại là mô hình tự tin đưa ra giá trị đoán, thử tính, kết luận là sai rồi cứ tiếp tục thử lại, thậm chí lặp lại cùng một phỏng đoán. Nó hoàn toàn không nhận ra tính đối xứng và hành xử như một tác nhân hoàn toàn không có cấu trúc
Cuối cùng nó còn khẳng định rất chắc rằng câu đố này vô nghiệm; nếu sau này mô hình vẫn làm tệ với các câu đố kiểu này thì chắc tôi phải điều chỉnh lại niềm tin của mình
Tôi cũng hỏi ChatGPT o3 và nó đã suy nghĩ trong 11,5 phút: https://chatgpt.com/share/682d0993-db4c-8004-a66c-3908ef7203...
Chẳng phải có một phiên bản ChatGPT nối với Wolfram Alpha sao? Tôi tò mò không biết đã thử cái đó chưa
Thêm bối cảnh và các ví dụ liên quan ở đây: https://x.com/TheOisinMoran/status/1299124512240398336
Dễ lần theo biến nào được dùng ở đâu hơn hẳn, và cũng dễ nắm bắt cấu trúc thuần túy của đoạn mã chỉ trong một cái nhìn. Ví dụ tôi từng đăng ở đây: https://imgur.com/F27ZNfk
Tiếc là đa số ngôn ngữ hiện đại như Rust và JS tuân theo khuyến nghị XID_Start/XID_Continue, mà cá nhân tôi thấy động cơ không hẳn vững lắm, và chúng loại toàn bộ ký tự emoji khỏi định danh
4, nghiệm nhỏ nhất có thể là một số thực sự khổng lồ: https://observablehq.com/@robinhouston/a-remarkable-diophant...Có phải nó có chỗ nào dễ gây hiểu nhầm đến mức khiến người ta cãi nhau không, hay là nó dễ đến mức khiến ai cũng vội vàng thể hiện mình giỏi?
Tôi ra
10, 4, 2, dù cũng có thể là tôi đã hiểu nhầmNên có vẻ có thể hiểu là
1 + 10 + 3