Bài báo của Bill Gates
Ngô Quang Hưng | 25 tháng 01, 2008 | 
Bản để in
Hồi mới thành lập MS (và còn chân trong chân ngoài ở Harvard), Bill Gates có viết một bài báo toán rời rạc (đăng ở tạp chí Discrete Math.) với đồng tác giả là giáo sư Papadimitriou của Berkeley. Hình như đây là bài báo khoa học duy nhất của Gates. Bài toán khá thú vị:
Cho một hoán vị bất kỳ của n số 1 … n. Phải cần, trong trường hợp tệ nhất, bao nhiêu lần đảo ngược một prefix của hoán vị để đạt được hoán vị đơn vị.
Ví dụ, nếu hoán vị là 5 1 3 4 2, ta có thể làm như sau:
- 5 1 3 4 2
- 2 4 3 1 5
- 4 2 3 1 5
- 1 3 2 4 5
- 3 1 2 4 5
- 2 1 3 4 5
- 1 2 3 4 5
Trong bài báo, họ chứng minh rằng số lần nghịch đảo nằm khoảng giữa 17n/6 và 5(n+1)/3.
hi hi … ca’i na\y vui .. sa\i ddu+o+.c ! Mo^?i la^\n to^i xe^’p ddo^\ o+? nha\ la\ bi. ba\ xa~ ca\m
ra\m la\ xe^’p tu\m lum kho^ng theo thu+’ tu+. .
Mo^.t deviation. Maximum pha?i flip bao nhie^u la^\n dde^? sort ra nhu+~ng qua^\n/a’o cu\ng ma\u ?
You’re funny!
Bài toán của anh rất hay. Nếu mỗi số từ 1 đến n có thể xuất hiện với một frequency cho trước thì cái bound 5N/3 sẽ ra sao? Dĩ nhiên ta có thể áp dụng bound của Gates và Papadimitriou với N = tổng frequency, nhưng chắc chắn không phải là bound tốt nhất.