Mặc dầu không là học sinh xuất sắc nhất về môn toán ở
Harvard, nhưng Gates đã bắt đầu chọn giải toán của sinh viên cao
học khi mới học năm thứ nhất và thường được điểm A cao nhất.
BÀI TOÁN XẾP ĐĨA
“Đầu bếp của chúng tôi vốn là người cẩu thả. Khi ông đặt
bánh vào đĩa và xếp thành từng chồng thì chúng luôn có
các kích cỡ khác nhau.
Vì vậy trong lúc mang đến bàn cho khách hàng, tôi lại phải
sắp xếp lại chồng bánh đó (sao cho đĩa bánh nhỏ nhất ở
trên cùng rồi tới những đĩa bánh lớn, lớn hơn và dưới cùng
sẽ là đĩa bánh lớn nhất) bằng cách lấy một số đĩa bánh
trên cùng rồi đặt chúng xuống dưới, lặp lại thao tác này
(số bánh tôi lấy ra đặt xuống dưới không giống nhau)
bao nhiêu lần tùy ý. Nếu có “n” đĩa bánh, số lần chuyển
đổi tối đa để sắp xếp lại chồng bánh theo thứ tự ‘lớn
dưới, nhỏ trên’ sẽ là bao nhiêu?”
“Đây là một bài toán nhìn trông đơn giản nhưng đã được
chứng minh là rất khó giải”, Christos Papadimitriou, giáo sư
khoa Khoa Học
Máy Tính của trường Harvard nói. Tuy nhiên, Bill Gates xem
việc viết một chương trình máy tính phức tạp để giải bài
toán này là một thách thức phải vượt qua. Giải pháp của anh
ta hơi dài nhưng rất thông minh.
Giáo sư Papadimitriou đã viết bài khen ngợi cách giải của
Gates và đến năm 1979, bài viết này được đăng trong tờ
Journal of Discrete Mathematics. Cách giải đột phá của
