Bài toán hóc búa từ 3.500 năm trước cuối cùng đã có lời giải

Mới đây, 1 bài toán được cho là 3.500 tuổi từ thời Ai Cập cổ đại đã có lời giải đáp nhờ vào toán học hiện đại.

{keywords}
 

Nội dung bài toán được phát biểu đơn giản như sau : cho trước một tập hợp gồm các số nguyên dương, hỏi từ tập hợp này có thể chọn ra các phần tử có tổng nghịch đảo bằng 1 được hay không?

Bài toán 3500 tuổi này có nguồn gốc từ thời Ai Cập cổ đại và trong một bài báo của mình, nhà toán học Thomas Bloom đã giải quyết trọn vẹn bài toán này. Một phiên bản của bài toán này cũng được hai nhà toán học Erdős và Graham đặt ra và trao thưởng 500 USD cho ai giải được nó.

Bài toán đó được đưa phát biểu như sau “Nếu tập A là tập con của tập N và A có mật độ dương, thì tồn tại một tập con hữu hạn S của A mà tổng nghịch đảo các phần tử của nó bằng 1”. (Một ví dụ về tập con của N có mật độ dương là A = {3,5,7,9,11,...}, có thể hiểu nôm na là khi ta lấy một lượng đủ lớn các số tự nhiên liên tiếp thì xác suất để tồn tại một số thuộc vào A là khác 0).

{keywords}
 

Andrew Granville, một nhà toán học đến từ Đại học Montreal, nói trong Tạp chí Quanta : “Tôi chỉ nghĩ đây là một câu hỏi bất khả thi mà không ai có thể giải được. Tôi không thấy bất kỳ công cụ rõ ràng nào có thể giải quyết nó". Tuy nhiên, Bloom tình cờ đã tìm ra đáp án nhờ vào một bài báo có từ 20 năm trước trong Biên niên sử Toán học năm 2003 mà tác giả của nó là nhà toán học Ernie Croot.

{keywords}
 

Những gì Croot đã giải được gọi là “phiên bản tô màu” của bài toán Erdős – Graham. Nó được gọi như vậy bởi vì nó liên quan đến các tập con “tô màu” - về cơ bản, có thể coi nó giống như việc phân chia tập A bằng cách bỏ các phần tử của A vào một số hữu hạn các hộp có màu khác nhau.

{keywords}
 

Nhà toán học Giorgis Petridis từ Đại học Georgia nói với Quanta: “Ý tưởng mả Croot đưa ra rất tuyệt vời. Tuy nhiên, nó đòi hỏi sự sáng tạo, khéo léo với các kỹ thuật tính toán cao” Petridis chia sẻ.

Ngoài ra, có một sự khác biệt rằng trong bài toán tô màu là, toàn bộ tập hợp A đã được chia thành các hộp. Bạn không biết chính xác nó được phân chia như thế nào, nhưng điều đó không thực sự quan trọng - tất cả những gì bạn cần chỉ ra là có một hộp chứa các con số đủ đẹp để tính tổng. Croot đã xây dựng bằng chứng để chỉ ra rằng sẽ có ít nhất một hộp có đủ những con số đẹp thỏa mãn định lý.

Nhưng phép chứng minh của Croot không giải được phiên bản trù mật của bài toán đã nói ở trên. Bloom đã vận dụng tốt những ý tưởng của Croot để giải quyết trọn vẹn bài toán. "Tôi nghĩ, phương pháp của Croot [thực sự] mạnh hơn so với tưởng tượng. Vì vậy, tôi đã dành ra vài tuần và tìm ra đáp án cho bài toán này" - Ông nói.

Bloom cho rằng Croot đã chứng minh được một trường hợp đặc biệt của bài toán này. Tất cả những gì Bloom phải làm là chỉ ra rằng kết quả sẽ giống nhau khi chứng minh các trường hợp còn lại và phiên bản trù mật của bài toán sẽ được giải quyết hoàn toàn.

Các phương pháp mà Bloom sử dụng thực sự là “một phiên bản nâng cấp” của những ý tưởng do Croot đề ra. Ý tưởng của Bloom là thay vì tìm ra các số có tổng nghịch đảo bằng 1 thì lại tìm ra các nhóm số có tổng nhỏ hơn, sau đó cộng lại bằng 1. “Ví dụ nếu ta tìm được ba nhóm mà tổng nghịch đảo các số của mỗi nhóm bằng ⅓ theo cách khác nhau, thì chỉ cần cộng chúng với nhau thì ta có kết quả là 1” - Bloom nói với tờ Quanta.

Với chứng minh của mình, Bloom đã giải quyết được một câu hỏi có nguồn gốc từ thời Ai Cập cổ đại. Tuy nhiên, không dừng ở đây, Bloom đặt ra một câu hỏi mới và tiếp tục đi tìm chứng minh: đối với tập A ⊂ N nào thì không thể tìm được tập con của A có tổng nghịch đảo các phần tử bằng 1?

Doãn Hùng (Theo IFL Science)

Tù nhân giải được bài toán cổ từng khiến nhà toán học 'đau đầu'

Tù nhân giải được bài toán cổ từng khiến nhà toán học 'đau đầu'

Một tù nhân tại Mỹ đã tự học toán cao cấp cơ bản. Nhờ đó, anh ta đã giải được một bài toán phức tạp. Không những thế, còn truyền niềm đam mê toán học của mình cho các bạn tù.

tin nổi bật

Vào Huế thực tế, nam sinh viên Học viện Báo chí bị sóng biển cuốn mất tích

Từ Hà Nội đi thực tế tại Huế, đoàn sinh viên Học viện Báo chí và tuyên truyền về biển Thuận An chơi thì 1 người bị sóng cuốn ra xa.

Niềm vui bất ngờ của nữ sinh từng khóc nhiều đêm sau khi đỗ đại học

Nỗi lo không có tiền để học đại học của nữ sinh Phạm Thị Tú Nguyên (Bến Tre) đã vơi bớt nhờ suất học bổng “Nâng bước thủ khoa 2022” do báo Tiền Phong và Quỹ hỗ trợ tài năng trẻ Việt Nam trao tặng hôm nay.

Loạt sai sót của trường bị phụ huynh tố vận động xã hội hóa hơn 300 triệu

Nguồn tin của VietNamNet cho biết, Sở GD-ĐT Cà Mau đã có thông báo kết quả xác minh nội dung đơn yêu cầu từ phụ huynh học sinh Trường THCS-THPT Tân Lộc (huyện Thới Bình) liên quan đến vụ vận động thu tiền xã hội hóa.

Nữ sinh lớp 11 bị nhóm bạn đánh tụ máu mắt

Trường THPT Cao Thắng (xã Sơn Tây, huyện Hương Sơn, Hà Tĩnh) đang phối hợp với công an làm rõ việc một nữ sinh lớp 11 bị nhóm bạn đánh tụ máu mắt.

Phụ cấp giáo viên có thể tăng 100%, riêng chi cho mầm non thêm 4 nghìn tỉ/năm

Bộ GD-ĐT đề xuất phụ cấp nhà giáo ở mức 25-100% tùy đối tượng, trong đó riêng đối với 200 nghìn giáo viên mầm non ở vùng khó, mức hỗ trợ dự kiến tăng thêm 4.032 tỉ đồng/năm.

TP.HCM có 91 cơ sở giáo dục có gói thầu, dự án liên quan AIC

Thực hiện chỉ đạo của Thanh tra TP.HCM, Sở GD-ĐT đang rà soát, kiểm tra các dự án, gói thầu mua sắm trang thiết bị ở các cơ sở giáo dục liên quan đến công ty cổ phần Tiến bộ quốc tế (AIC).

Nam sinh cứu người khỏi đường ray tàu hỏa được Bộ trưởng Giáo dục tặng bằng khen

Bộ trưởng Bộ GD-ĐT vừa có quyết định tặng bằng khen cho em Hoàng Mạnh Chiến (học sinh lớp 7A2, Trường THCS Cẩm Thịnh, TP Cẩm Phả, tỉnh Quảng Ninh) vì đã có hành động dũng cảm cứu người.

Nữ sinh lớp 10 hẹn nhau đánh hội đồng bạn cùng lớp

Do mâu thuẫn trong chuyện tình cảm riêng và từ phát ngôn trên mạng xã hội, nữ sinh lớp 10 ở Bà Rịa - Vũng Tàu đã hẹn gặp bạn cùng lớp giải quyết, sau đó dùng mũ bảo hiểm đánh hội đồng người này.

Trường đại học cho sinh viên nghỉ Tết Nguyên đán kỷ lục 40 ngày

Trường ĐH Khoa học Tự nhiên (ĐH Quốc gia TP.HCM) cho sinh viên nghỉ Tết Nguyên đán 2023 với thời gian 40 ngày

LG trao học bổng ‘Chung tay sẻ chia’ cho sinh viên tài năng

LG đồng hành với Hiệp hội Doanh nghiệp Hàn Quốc (Kocham) tổ chức chương trình trao học bổng “Chung tay chia sẻ” năm 2022 nhằm tiếp sức và tạo động lực cho sinh viên Việt Nam tài năng.

'Thành tựu của tôi sau 2 tháng độc thoại với nữ sinh trầm cảm'

Đối với một giáo viên, điều đầu tiên cần làm là tiếp xúc để tìm hiểu học sinh, từ đó có đánh giá ban đầu về khả năng học tập của các em. Câu chuyện của nữ sinh bị trầm cảm ở lớp tôi là một ví dụ.

Lương giáo viên trên thế giới: Cao nhất 3 tỷ đồng/năm

Giáo viên không phải là người kiếm nhiều tiền nhất ở các nước, nhưng hầu hết trang trải đủ cho cuộc sống thường nhật bằng tiền lương nhận được.

Thầy giáo Toán được mệnh danh 'quyến rũ nhất thế giới' hiện làm gì?

Một khoảnh khắc chụp lén thầy giáo Pietro Boselli đã tạo bước ngoặt cuộc đời Boselli, khiến thầy được mệnh danh là giáo viên "quyến rũ nhất thế giới".

4 lĩnh vực tuyển sinh kém nhất trong 3 năm gần đây

Theo thống kê của Bộ GD-ĐT, 4 lĩnh vực gồm Nông lâm nghiệp và thủy sản, Khoa học sự sống, Khoa học tự nhiên và Dịch vụ xã hội tuyển sinh kém nhất trong 3 năm gần đây.

Bộ GD-ĐT cân nhắc không xét tuyển đại học sớm năm 2023

Năm tới, Bộ GD-ĐT có thể không xét tuyển sinh ĐH, CĐ sớm như năm nay, mà tổ chức tất cả các phương thức cùng thời điểm với đợt xét tuyển căn cứ kết quả thi tốt nghiệp THPT.