Bài toán Con Đ ng Màu đã đ c gi i ườ ượ ả
Vi t b i Lim Nguy n ế ở ễ
Ch nh t, 13 Tháng 4 2008 02:54 ủ ậ
Nhà toán h c Avraham Trakhtman, 63 tu i, v a gi i quy t đ c m t trong nh ng bàiọ ổ ừ ả ế ượ ộ ữ
toán thú v nh t c a lĩnh v c toán t h p hi n đ i mang tên, bài toán Con Đ ng M uị ấ ủ ự ổ ợ ệ ạ ườ ầ
(Road coloring problem). L i gi i chính th c c a bài toán s đ c đăng trên t p chíờ ả ứ ủ ẽ ượ ạ
toán h c Israel s t i. Bài toán Con đ ng màu l n đ u tiên đ c đ xu t b i nhà toánọ ố ớ ườ ầ ầ ượ ề ấ ở
h c ng i Israel Binyamin Weiss năm 1970. Bài toán liên quan đ n các ch d n đ ngọ ườ ế ỉ ẫ ồ
b và đ c di n gi i ng n g n nh sau :ộ ượ ễ ả ắ ọ ư
"M t anh chàng đi đ n m t th tr n mà anh ta ch a t ng đ t chân đ n bao gi đ tìmộ ế ộ ị ấ ư ừ ặ ế ờ ể
nhà ng i b n gái thâm niên c a mình. M c dù các đo n đ ng trong th tr n đ uườ ạ ủ ặ ạ ườ ị ấ ề
không có g n tên, ng i b n gái c a anh an i anh c yên tâm đi theo ch d n c aắ ườ ạ ủ ủ ứ ỉ ẫ ủ
mình thì anh s đ n đ c đúng n i, sau m t t p h p các thao tác ( r trái, r ph i, rẽ ế ượ ơ ộ ậ ợ ẽ ẽ ả ẽ
ph i ...). Bài toán Con đ ng màu đ t gi thuy t r ng, dù b t đ u t đâu trong thả ườ ặ ả ế ằ ắ ầ ừ ị
tr n, đông tây b c nam, s có m t t p h p các thao tác ( r trái, r ph i) d n anhấ ắ ẽ ộ ậ ợ ẽ ẽ ả ẫ
chàng đi đ n đúng nhà ch b n cũ."ế ị ạ
M t phiên b n khác đó là bài toán email b th t l c, ng i g i mu n ch c ch n b cộ ả ị ấ ạ ườ ử ố ắ ắ ứ
th đi n t đó đ n đ c đúng n i, ngay c khi thao tác ban đ u b nh m l n. Hình vư ệ ử ế ượ ơ ả ầ ị ầ ẫ ẽ
d i đây là m t ví d ,ướ ộ ụ
http://plus.maths.org/latestnews/jan-apr08/road/road.jpg
B t k b n b t ngu n t đâu, b ng vi c đi theo ch d n Xanh-Đ -Đ --- Xanh-Đ -Đấ ể ạ ắ ồ ừ ằ ệ ỉ ẫ ỏ ỏ ỏ ỏ
--- Xanh-Đ -Đ , b n s đ n đ c đ nh màu Vàng. Bài toán ban đ u là m t gi thuy t,ỏ ỏ ạ ẽ ế ượ ỉ ầ ộ ả ế
cho r ng luôn có m t ch d n t ng quát đ đ n m t v trí c n đ n, trong m t h đóngằ ộ ỉ ẫ ổ ể ế ộ ị ầ ế ộ ệ
mà đó không có con đ ng nào r ra ngoài. ở ườ ẽ
Bài toán này có nhi u đi m gi ng v i Đ nh lý B n Màu (Four Colour Theorem) ch aề ể ố ớ ị ố ư
đ c ch ng minh, đó cho r ng b n ch c n duy nh t 4 màu đ có th tô vào m i t nhượ ứ ở ằ ạ ỉ ầ ấ ể ể ỗ ỉ
thành m t màu sao cho hai t nh k nhau s có hai màu khác nhau. Các b n có th tìmộ ỉ ề ẽ ạ ể
hi u thêm v bài toán này qua bài vi t b ng ti ng Anh The origins of proof IV: Theể ề ế ằ ế
philosophy of proof. Bài toán này l n đ u tiên đ c s quan tâm r ng rãi là vào nămầ ầ ượ ự ộ
1852; và năm 1879 Alfred Kempe đã công b " ch ng minh" c a mình trên t p chíố ứ ủ ạ
Nature và c t p chí toán h c M , American Journal of Mathematics. Đáng ti c, nămả ạ ọ ỹ ế
1890, Percy Heawood đã tìm ra m t l i sai ch ng minh trên, và ph i đ i 86 năm sau,ộ ỗ ở ứ ả ợ
Kenneth Appel và Wolfgang Haken m i đ a ra đ c m t ch ng minh liên quan đ n bàiớ ư ượ ộ ứ ế
toán này b ng phép t ng ph n. Ch ng minh b t đ u b ng gi thuy t có nhi u b nằ ươ ả ứ ắ ầ ằ ả ế ề ả
đ đ a lý 5 màu, b n luôn có th ch n ra m t b n đ có s t nh thành là nh nh t. Sauồ ị ạ ể ọ ộ ả ồ ố ỉ ỏ ấ
đó h ch ra r ng t m b n đ đó ph i ch a m t trong s 1936 c u hình kh năng, vàọ ỉ ằ ấ ả ồ ả ứ ộ ố ấ ả
h ch ng minh đ c r ng m i câu hình đó có th rút g n đ t o thành các m u nhọ ứ ượ ằ ỗ ể ọ ể ạ ẫ ỏ
h n, và có th đ c tô b ng 5 n m khác nhau. Đi u này là mâu thu n b i vì chúng taơ ể ượ ằ ằ ề ẫ ở
đã đ t ra gi thuy t r ng t m b n đ năm màu ban đ u là nh nh t. ặ ả ế ằ ấ ả ồ ầ ỏ ấ
V n đ v i ch ng minh c a h đó là s d ng máy tính đ phân tích 1936 c u hìnhấ ề ớ ứ ủ ọ ử ụ ể ấ
kh năng c a b n đ . Ch ng minh đó n u in ra s r t dài và không nhà toán h c nàoả ủ ả ồ ứ ế ẽ ấ ọ
có th i gian và kh năng đ đ c h t đ c b n in này. N u m t ch ng minh mà khôngờ ả ể ọ ế ượ ả ế ộ ứ
đ c ki m ch ng, thì đa s các nhà toán h c cho r ng nó không ph i là m t l i gi iượ ế ứ ố ọ ằ ả ộ ờ ả
t ng minh.ườ
Ng c l i v i ch ng minh c a Đ nh lý 4 màu, l i gi i bài toán Con đ ng màu c aượ ạ ớ ứ ủ ị ờ ả ườ ủ
Trakhtman đ c xem là đ n gi n, tao nhã và tinh t . Trakhtman đã gi i bài toán b ngượ ơ ả ế ả ằ
ph ng pháp truy n th ng - không s d ng đ n máy tính - mà b ng bút chi và gi yươ ề ố ử ụ ế ằ ấ
tr ng. Công trình c a Trakhtman còn có ý nghĩa h n vì nh nó mà ông đ c công nh nắ ủ ơ ờ ượ ậ
là giáo s toán h c t i tr ng đ i h c Bar-Ilan. Là m t nhà khoa h c Nga, nh p cư ọ ạ ườ ạ ọ ộ ọ ậ ư
vào Israel năm 1990, Trakhtman đã ph i làm vi c không m t m i đ duy trì v trí c aả ệ ệ ỏ ể ị ủ
ông, nh m nh n đ c biên ch chính th c c a tr ng đ i h c. L i gi i c a bài toánằ ậ ượ ế ứ ủ ườ ạ ọ ờ ả ủ
này còn có nhi u ng d ng cho lĩnh v c b n đ cũng nh khoa h c máy tính. B n cóề ứ ụ ự ả ồ ư ọ ạ
th xem tr c l i gi i c a Trakhtman trên trang d b arXiv.ể ướ ờ ả ủ ự ị
Ngu n : plus.maths.orgồ