🔙 Quay lại trang tải sách pdf ebook Tạp Chí Epsilon Số 13 Ebooks Nhóm Zalo THỨC BẬC HAI - Nguyễn Văn Huyện TAM QUAN ĐIỂM CỦA KANT VỀ KHÔNG GIAN VÀ ẰNG B G PHƯƠN H NÌ H B HP ÂN T CÍ KHÁC NO 13 t h áng 2 \ 2017 SỐ THỜI GI A N - Nguyễn Ái Việt Liên C Ụ M CÁC CHUYÊN HOÀN HẢO VÀ NHỮNG SỐ BẠN BÈ - Nguyễn Duy Lữ SỬ DỤNG GIỚI HẠN TRONG GIẢI TOÁN - Lê Phúc HỮNG BÍ ẨN CỦA SỐ NGUYÊN TỐ - Ian Stewart N g ÀV Hưn VƯỢT ĐỊNH KIẾN BẰNG LĂNG BA VI BỘ - Ngô Quang Epsilon - Một chặng đường Ban Biên tập Epsilon LỜI NGỎ TỪ TỔNG BIÊN TẬP Vậy là chúng ta đã đi qua một chặng đường của 13 số Epsilon, tương đương với gần 800 ngày, 26 tháng và nhiều đêm thức trắng của các tác giả và các thành viên ban biên tập. Cuộc tổng diễn tập đã thành công. Và hơn thế một tinh thần vì cộng đồng đã được lan tỏa. Các tác giả đã đóng góp những bài viết tâm huyết của mình. Và các biên tập viên đã tốn nhiều thời gian, công sức để sắp xếp, trình bày các bài viết đó trong một hình thức đẹp nhất, khoa học nhất. Tất cả đã cùng tạo ra những số Epsilon đáng đọc và đáng lưu giữ. Epsilon không phải là tờ báo để đọc trong một ngày hay một vài ngày. Hôm nay bạn đọc có thể đọc (và hiểu được) một vài bài trong đó. Nhưng sau vài năm, nếu đọc lại, bạn đọc có thể sẽ tìm được nhiều điều thú vị hơn thế (và hiểu được nhiều hơn). Vì thế tuy Epsilon sẽ tạm dừng lại ở con số 13, những số báo của Epsilon chắc chắn vẫn sẽ còn hiện diện và lan tỏa. Và hơn cả 13 số báo Epsilon, tinh thần của Epsilon chắc chắn sẽ được tiếp nối qua những con người đã làm nên nó. Đó là các tác giả, các biên tập viên và các bạn đọc thân thiết. Tinh thần đó là sẵn sàng đóng góp vì cộng đồng với tất cả nhiệt huyết, trí tuệ và sự chuyên nghiệp. Trong lời ngỏ lần này, tôi với tư cách tổng biên tập, muốn gửi lời cảm ơn chân thành đến các tác giả, những người đã đóng góp các bài viết tuyệt vời của mình cho Epsilon, các cộng tác viên, những người đã giúp chúng tôi dịch các bài viết hay từ nhiều thứ tiếng, các bạn đọc, những người đã động viên và truyền cảm hứng cho công việc của chúng tôi. Và tất nhiên là tôi muốn cảm ơn các cộng sự trẻ tuổi của tôi, những thành viên ban biên tập, những người đã làm việc rất chuyên nghiệp và hoàn toàn bất vụ lợi. (Nhưng tôi cũng tin rằng, tất cả mọi người đều đã thu được rất nhiều qua 13 số báo Epsilon). Trong số các tác giả của Epsilon, tôi muốn đặc biệt nhắc đến các tác giả Ngô Quang Hưng, Lý Ngọc Tuệ, Trần Quang Hùng, Nguyễn Duy Liên những người xứng đáng có những tuyển tập riêng các bài viết dành cho Epsilon. Không dành được nhiều thời gian cho Epsilon nhưng các GS Hà Huy Khoái, Đàm Thanh Sơn, Ngô Bảo Châu luôn có những quan tâm đặc biệt dành cho chúng tôi, gợi ý đề tài và tạo cảm hứng cho chúng tôi tiếp tục những khởi đầu của mình. Epsilon cũng đã chắp cánh cho những bài viết hay của các bạn học sinh, trong đó đặc biệt là mảng hình học. Nổi bật trong số các tác giả trẻ tuổi có thể nhắc đến bạn Nguyễn Trần Hữu Thịnh, học sinh lớp 12 chuyên toán trường THPT chuyên Lý Tự Trọng Cần Thơ. Và các bà đỡ cho các bài viết hình học là hai biên tập viên Trần Quang Hùng và Ngô Quang Dương. Epsilon đã hoàn thành nhiệm vụ giai đoạn thứ nhất của mình. Nói như thế nghĩa là chặng đường thứ nhất đã được đi qua. Nhưng cũng có nghĩa là sẽ còn chặng đường thứ hai. Trong thời gian tới, chúng tôi sẽ không ra các số định kỳ vào ngày 13 của các tháng chẵn nữa. Thay vào đó sẽ là các tuyển tập theo các tác giả, theo các chủ đề, theo các chuyên mục. Và những sản phẩm mới này sẽ bắt đầu xuất hiện ngay trong năm 2017. Có nghĩa là Epsilon vẫn còn tiếp tục. Và giờ đây, hãy cùng chúng tôi điểm lại những thăng trầm của Epsilon trong suốt 800 ngày qua. Tạp chí Epsilon, Số 13, 02/2017 Epsilon - Một chặng đường và Những cột mốc Ý tưởng về Epsilon được hình thành từ khoảng cuối năm 2014, và hiện thực hoá vào tháng 2 năm 2015, với số Epsilon đầu tiên. Trong phần này, chúng tôi tạm điểm qua những cột mốc quan trọng trong suốt chặng đường phát triển của Epsilon. • 13/2/2015: Epsilon số 1 ra đời với 8 tác giả, 9 bài viết qua 154 trang. • 16/2/2015: Trang FB chính thức ra đời. • 13/4/2015: Epsilon chính thức có logo và định dạng bìa mới. Tạp chí bắt đầu nhận được những bài viết của những “cây đa cây đề” trong giới. Ban Biên tập tăng lên 5 thành viên. Lần đầu tiên số lượt tải đạt con số 4000. • 13/6/2015: Epsilon số 3 ra đời với logo được nâng cấp. Đây cũng là logo được giữ nguyên cho đến số cuối cùng. Tạp chí tiếp tục phát triển cùng với số thành viên Ban Biên tập tăng lên thành 6 người. • 13/8/2015: Epsilon số 4 phiên bản beta ra đời. Đây cũng là số Epsilon duy nhất không có phiên bản chính thức. • 13/10/2015: Epsilon số 5 ra đời, đây cũng là một trong những số dài nhất với 245 trang (đứng thứ 2 sau số cuối cùng bạn đọc đang xem). Số lượng thành viên của ban biên tập cũng gia tăng thành 7 người. Định dạng trang của Epsilon cũng được cập nhật. • 29/10/2015: Số lượng người ủng hộ trang FB của Epsilon chính thức vượt qua 2.000 người. • 13/12/2015: Epsilon số 6 với 18 bài viết trong 177 trang ra đời. Thành viên ban biên tập tiếp tục tăng thêm và bắt đầu cố định ở con số 8 – 9 thành viên. Số người quan tâm lên đến hơn 20.000 và số lượt tải đã vượt quá 2.000. • 13/2/2016: Epsilon đã đi hơn 1 năm và đón chào số 7 với 200 trang bài. Đây cũng là số đầu tiên Epsilon bắt đầu áp dụng định dạng chuẩn cho cộng tác viên dễ dàng viết bài. Bắt đầu từ số này, định dạng Epsilon thống nhất trong mọi mặt cho đến số cuối cùng. • 13/4/2016: Epsilon số 8 ra đời với phong độ ổn định qua gần 15.000 người quan tâm. • 13/6/2016: Epsilon số 9 ra mắt với 205 trang viết. Đây là số đầu tiên nhận được hơn 200 yêu thích từ bạn đọc. • 13/8/2016: Epsilon số 10 ra đời, lần đầu tiên số lượt tải vượt 10.000 lượt và từ đó giữ vững cho đến các số cuối cùng. • 13/10/2016: Epsilon số 11 ra mắt, với hơn 48.000 người quan tâm và đây vẫn là một kỷ lục của báo, một thành công ngoài dự đoán của ban biên tập. • 13/12/2016: Epsilon số 12 ra mắt với hơn 12.000 lượt tải từ bạn đọc. • 10/1/2017: Tạp chí Pi, người anh của Epsilon ra đời, báo hiệu giai đoạn chạy đà của Epsilon đã chuẩn bị hoàn thành. • 13/2/2017: Epsilon cuối cùng, Epsilon số 13 ra mắt, lập kỷ lục là số dài nhất (327 trang), giới thiệu nhiều bài toán nhất (390 bài), từ sự đóng góp của 30 tác giả và dịch giả. 4 Epsilon 13 13 70% 30% Bạn đọc của Epsilon Tính đến thời điểm ra mắt số cuối cùng, Epsilon có hơn 10.000 lượt tải và hơn 5.000 người ái mộ. Trong số đó có 70% bạn đọc là phái mạnh và và 30% là những người phụ nữ đáng mến. PI Ngày 13/2/2017, Epsilon chính thức cuối cùng, 12 11 Epsilon 13 ra mắt bạn đọc. Đều đặn các ngày 13 tháng chẵn, Epsilon luôn ra mắt Ngày 10/1/2017, tạp chí Pi, người anh của Epsilon ra đời, báo hiệu giai đoạn chạy đà của Epsilon đã chuẩn bị hoàn thành. 8 đúng hạn, với số lượng độc giả và người ái mộ gia tăng qua từng số báo. Tính trung bình, mỗi ngày Epsilon được 4.600 lượt truy cập từ cộng đồng người Việt ở 46 quốc gia trên thế giới. Có những bài viết của Epsilon đã lan toả đển hơn 48.000 người, một con số kỷ lục của Epsilon! 9 10 TÁC GIẢ227 BÀI TOÁN 92 BÀI VIẾT3.057 Epsilon 7 13/2/2016, Epsilon đã đi hơn 1 năm và đón chào số 7 với 200 trang bài. Đây cũng là số Thành quả Epsilon 6 5 Epsilon số 5 là một trong những số dài nhất với 248 trang, giới thiệu đầu tiên Epsilon bắt đầu áp dụng định dạng chuẩn cho cộng tác viên dễ dàng viết bài. Bắt đầu từ số này, định dạng Epsilon thống nhất trong mọi mặt cho đến số cuối cùng. Ngày 13/6/2016, Epsilon số 3 ra đời với logo được nâng cấp. Đây cũng là logo được giữ nguyên cho đến số cuối cùng. Epsilon 3 tổng cộng 322 bài toán. Cùng với số này, số lượng người ủng hộ trang FB của Epsilon chính thức vượt qua 2000 người. 4 Epsilon 2 Ngày 13/4/2015, Epsilon chính thức có logo và định dạng bìa mới. Lần đầu tiên số lượt tải đạt con số 4000. Ngày 16/2/2015, trang FB chính thức, và cũng là trang duy nhất của Epsilon ra đời. FB Ngày 13/2/2015, Epsilon số 1 chính thức ra đời với 8 tác giả, 9 bài viết, giới thiệu với bạn đọc 209 bài toán qua 154 trang báo. Epsilon 1 Hành trình EPSILON 13 số 92 tác giả và dịch giả 227 bài viết 180 Bài viết giới thiệu nhiều bài toán nhất: 180 bài. "Giới thiệu về kỳ thi học bổng du học Nga" Epsilon 11 - Lê Phúc Lữ Đứng thứ nhì là "Về bài bất đẳng thức trong đề thi VMO 2015" với 84 bài. Bài viết nhiều trang nhất: 54 trang. 54 2.704 trang 3.057 bài toán 850.644 từ "Về bài bất đẳng thức trong đề thi VMO 2015" Epsilon 1 - Võ Quốc Bá Cẩn. Đứng thứ nhì là "Cực trị tập hợp" với 52 trang, Epsilon 3 - Trần Minh Hiền. 11 Chuyên đề thường xuyên nhất: 11 số "Cổ điển - hiện đại" và "Toán học giải trí" Bạn đọc và người ái mộ Epsilon ở qu 46 ốc gia trên thế giới Người ái mộ Epsilon ở Việt Nam đa số đến từ Hà Nội và Sài Gòn. ĐÔNG BẮC TÂY BẮC HÀ NỘI THÁI NGUYÊN ĐỒNG BẰNG SÔNG HỒNG BẮC TRUNG BỘ HẢI PHÒNG 28% HUẾ ĐÀ NẴNG NAM TRUNG BỘ 23.5% TÂY NGUYÊN BUÔN MA THUỘT ĐÔNG NAM BỘ TP. HỒ CHÍ MINH BIÊN HÒA Tác giả đóng góp nhiều bài nhất: Chủ biên Trần Nam Dũng với 33 bài viết. 33 CẦN THƠ ĐỒNG BẰNG SÔNG CỬU LONG 48.200 Số lần quan tâm kỷ lục với một tin bài. 12.000 Số lượt tải cho một số báo. Số bài viết nhiều nhất của một tác giả không phải từ ban biên tập: 7 bài. Đến từ hai cây bút quen thuộc: Nguyễn Tiến Dũng và Lý Ngọc Tuệ. 7 Đây cũng là số lượng bài nhiều nhất từ 1 tác giả trong một số Epsilon: Chủ biên Trần Nam Dũng với Epsilon - 5. 4.600 Số lượt truy cập trung bình mỗi ngày. 2 Có 2 tác giả cùng có mặt trong đủ 13 số Epsilon: Trần Nam Dũng và Trần Quang Hùng. Tạp chí Epsilon, Số 13, 02/2017 Kết thúc cũng chính là khởi đầu Năm mới Đinh Dậu là thời điểm Epsilon trọn vẹn với 13 kỳ. Chúng tôi tin rằng mọi kết thúc của hành trình tri thức đều chỉ là trạm dừng chuẩn bị cho những khám phá sâu sắc hơn. Ý nghĩa đó được gửi gắm trong thiết kế bìa của số 13: những vòng tuần hoàn có thủy có chung. “Thư bất tận ngôn”, lời đã tận, tâm ý còn chưa dứt. Lời kết của hôm nay của Epsilon, cũng là lời chúc đầu năm ban biên tập dành cho quý độc giả và kỳ vọng của chính chúng tôi: một khởi đầu mới, một hành trình mới chuẩn bị mở ra... 7 MỤC LỤC Ban Biên tập Epsilon - Một chặng đường . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 Ngô Quang Hưng Vượt định kiến bằng Lăng ba vi bộ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 Nguyễn Ái Việt Quan niệm của Kant về không gian và thời gian . . . . . . . . . . . . . . . . . . . . . . 21 Đặng Nguyễn Đức Tiến Toán học và Phát hiện ảnh giả mạo - Phần kết . . . . . . . . . . . . . . . . . . . . . . . 26 Trần Thanh Hải Kiểm chứng là mô hình . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37 Henry Trần Các phương pháp sai phân hữu hạn cho phương trình đạo hàm riêng . . . . . . . . . . . 43 W. Timothy Gowers (Dịch giả: Nguyễn Vũ Duy Linh) So sánh toán IMO và toán nghiên cứu? Trường hợp lý thuyết Ramsay . . . . . . . . . . . 67 Đặng Nguyễn Đức Tiến Những bài toán cân tiền - Phần kết . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 81 Dương Đức Lâm Vài nét về phương trình Navier-Stokes . . . . . . . . . . . . . . . . . . . . . . . . . . . 87 Trần Quang Hùng Về mội bài toán trong kỳ thi Olympic hình học Sharygin năm 2014 . . . . . . . . . . . . 97 Ngô Quang Dương Hai điểm Brocard . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 123 Nguyễn Trần Hữu Thịnh Một số kết quả về đẳng cự trong tam giác . . . . . . . . . . . . . . . . . . . . . . . . . 139 Nguyễn Đình Hoàng, Nguyễn Đức Bảo Một mở rộng cho đường tròn Mixtilier . . . . . . . . . . . . . . . . . . . . . . . . . . . 154 Võ Hoàng Hưng, Nguyễn Đặng Minh Huy, Võ Hoàng Trọng, Võ Anh Kiệt Sóng lưu động và ứng dụng vào mô hình lan truyền dịch bệnh . . . . . . . . . . . . . . . 158 Trần Minh Hiền Số Fermat - Tính chất và ứng dụng . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 182 8 Tạp chí Epsilon, Số 13, 02/2017 Ian Stewart Những bí ẩn của số nguyên tố . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 198 M. A. Lukomskaia (Dịch giả: Hoàng Đức Tân) Định lý Van Der Waerden về cấp số cộng và một số tổng quát hoá . . . . . . . . . . . . 205 Lê Xuân Đại Một số phương pháp giải bài toán tồn tại trong số học . . . . . . . . . . . . . . . . . . . 209 Lê Phúc Lữ Sử dụng giới hạn trong giải toán . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 233 Nguyễn Văn Huyện Phân tích bình phương bằng tam thức bậc hai . . . . . . . . . . . . . . . . . . . . . . . 250 Võ Quốc Bá Cẩn Dồn biến bằng quy nạp . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 263 Kiều Đình Minh Xây dựng dãy nghiệm trong phương trình hàm đa thức . . . . . . . . . . . . . . . . . . . 283 Nguyễn Duy Liên Số hoàn hảo và những số bạn bè . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 288 Ban Biên tập Tuổi trẻ của một người phụ nữ đoạt huy chương Fields . . . . . . . . . . . . . . . . . . . 299 Phạm Văn Thuận MYTS - Cuộc thi tìm kiếm tài năng toán học . . . . . . . . . . . . . . . . . . . . . . . . 304 Nguyễn Hùng Sơn Ba Lan và các kỳ thi toán khu vực . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 316 Ban Biên tập Bài toán hay - Lời giải đẹp . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 323 9 Tạp chí Epsilon, Số 13, 02/2017 VƯỢT ĐỊNH KIẾN BẰNG LĂNG BA VI BỘ Ngô Quang Hưng (LogicBlox) 1. Hội xu ngửa Tương truyền rằng, nhà vua ở một vương quốc vĩ đại nọ rất yêu khoa học. Tên miền của vương quốc này là NN. Ông ta muốn tìm hiểu cơ động học của tiền xu vào những đêm nguyệt thực, vì đây là những đêm thiên địa dung hòa, vũ trụ tiết lộ bí mật của nó. Cứ mỗi lần nguyệt thực, ông yêu cầu mỗi người dân thảy một đồng xu xem nó sấp hay ngửa. Sau một thời gian, dân chúng cũng nhiễm tinh thần yêu chân lý của nhà vua, và họ đưa ra những mô hình dự đoán sấp ngửa. Ngưu tầm ngưu, mã tầm mã, mô hình tầm mô hình. Hiệp hội mười đồng xu ngửa ra đời trong hoàn cảnh ấy. Mô hình dự đoán của hiệp hội này rất đơn giản: các đồng xu thảy trong một đêm nguyệt thực luôn ra mặt ngửa. Vương quốc nọ có khoảng 100 triệu dân. Hiệp hội mười đồng xu ngửa có trên dưới 100 nghìn thành viên. Họ có cả một website tên là “xungửa.còm” rất đông khách vãng lai. Tất cả các đồng xu thảy bởi 100 nghìn thành viên này trong 10 lần nguyệt thực gần đây nhất đều cho ra mặt ngửa, vị chi là 1 triệu đồng xu ngửa. Các trải nghiệm của họ hoàn toàn nhất quán với mô hình. Họ lý luận rằng xác suất mà cả một triệu đồng xu đều ngửa là một phần 2 lũy thừa một triệu. Mà 2 mũ 130 thôi đã nhiều hơn tổng số nguyên tử trên toàn vũ trụ rồi. Do đó lý thuyết của họ được minh chứng bằng khoa học, xác suất mà họ sai gần như bằng 0. Trời sinh cả Du lẫn Lượng. Song song với họ, còn có hiệp hội mười đồng xu úp, rồi điều tra dân số thường niên của nhà vua cho thấy còn có cả hiệp hội hiệp hội năm ngửa, năm sấp, hiệp hội sấp ngửa năm lần, hiệp hội sấp sấp ngửa ngửa sấp hai lần, và cỡ chừng 1019 hiệp hội khác. Các hiệp hội này tranh cãi nhau chí tử, sắp sửa bạo loạn đến nơi. Ông vua nọ rất buồn, cố gắng đứng ra hòa giải. Phụng thiên thừa mệnh, hoàng đế chiếu rằng: đến 7 đêm nguyệt thực kế tiếp, tự thân vua sẽ thảy đồng xu, và hiệp hội nào đoán đúng cả 7 đồng xu sẽ là kẻ chiến thắng, hội trưởng sẽ được phong chức quốc sư, tiền tài quyền lực không bút nào tả xiết. Nguyệt thực thì mỗi năm có từ 0 đến 3 lần, phải chờ đến 5 năm sau kết quả mới được công bố. Kết quả là: còn đến cả chục hiệp hội đoán đúng cả 7 đồng xu! Ông vua thấy thế buồn quá ngã vật ra chết lăn quay cù quày, ôm xuống tuyền tài cái mộng giải thích cơ động học đồng xu. Mặc dù chẳng hội nào chiếm được chức thái sư, kể từ ngày đó, các hiệp hội này danh tiếng nổi như cồn, trở thành các trường phái nghiên cứu môn cơ động học đồng xu đêm nguyệt thực mà hiện nay có rất nhiều môn đệ tử trên toàn thế giới. 10 Tạp chí Epsilon, Số 13, 02/2017 2. Từ ngữ dùng để phỉ báng, xưa và nay Đó là chuyện xưa. Ngày nay, ở một quốc gia khác với tên miền VN, cũng có nhiều môn phái lớn. Chỉ hơi khác là các mặt đồng xu ở quốc gia này được in nhiều thứ hơn là sấp/ngửa: Đồng xu Ngửa Sấp 1 Mũi tẹt Mũi tẹt hơn 2 Làm cho Tuổi Trẻ Làm cho Thanh Niên 3 Thi Đại Học được ≥ 13.5 điểm (vừa đậu!) Thi Đại Học được < 13.5 điểm 4 Sinh ra trong gia đình khá giả Sinh ra trong gia đình nghèo 5 Bố mẹ cho genes tốt Bố mẹ không cho genes tốt 6 Sinh bên này vĩ tuyến 17 Sinh bên kia vĩ tuyến 17 7 Cao trên 1 mét 45 Cao dưới 1 mét 45 8 Vòng ngực trên 72cm Vòng ngực dưới 72cm 9 Cha mẹ đặt tên là Lê Văn Kiểm Cha mẹ đặt tên là Tăng Minh Phụng 10 . . . . . . Và hiệp hội mười xu ngửa trong quốc gia này có tên rất lạ là hiệp hội èo lít. Những người còn nhớ văn hóa vương quốc NN cổ xưa không thể hiểu được tại sao mười xu ngửa trong quốc gia VN lại được gọi là èo lít, chắc là cần thương hiệu mới vì sợ vi phạm tác quyền. Nhưng khác nhau chỉ về tên gọi, còn hiện tượng thì vẫn như ở NN: các hiệp hội vào In Tờ Lét phỉ nhau chí tử. Thậm chí thành viên các hiệp hội còn dùng những từ như “ngu”, “dốt”, “cộng sản”, “chống cộng Bolsa”, “hèn”, “đểu”, vân vân, để gọi nhau. Hồi xưa ở vương quốc NN người ta hay chửi nhau rằng: “mày là cái đồ sấp ngửa ngửa sấp”. 3. Đập đầu vào tường mãi, một trong hai thứ sẽ vỡ Trong vương quốc với tên miền VH, xu ngửa = nhà xuất bản nhận in bản thảo, xu sấp = nhà xuất bản từ chối in bản thảo. Năm 1995, một phụ nữ người Anh nộp bản thảo của mình và nhận được 12 đồng xu sấp liên tục. Thay vì gia nhập hội một tá xu sấp, bà ta thử thêm xu mười ba và lần này là xu ngửa từ nhà xuất bản Bloomsbury. Đồng xu ngửa này cũng xém nữa là sấp nếu không nhờ một cô bé 8 tuổi tên Alice Newton, con gái của giám đốc Bloomsbury, đã đọc chương một và đòi bố cho xem chương hai. Tuy nhận in, một biên tập viên của Bloomsbury gợi ý rằng phụ nữ nọ nên đi tìm việc khác vì viết sách trẻ em rất ít tiền. Người phụ nữ đó tên là Joanne Rowling. Bản thảo đánh trên máy đánh chữ có tựa đề “Harry Potter và hòn đá của Triết Gia”. Đồng xu ngửa số 13 biến Rowling thành người đầu tiên trong lịch sử thế giới trở thành tỉ phú tiền đô nhờ viết sách, và là người giàu thứ 1140 trên thế giới, theo tạp chí Forbes năm 2011.1 Chỉ trong phạm vi sách trẻ em, bản thảo quyển “And To Think That I Saw It On Mulberry Street” nhận được khoảng 27, 28 đồng xu sấp. Đó là bản thảo đầu tay của Theodor Seuss Geisel, được 1Năm 2016 bà không còn trong danh sách tỉ phú, mặc dù kiếm được rất nhiều tiền từ cả sách lẫn phim. Vì, bà làm từ thiện rất nhiều! 11 Tạp chí Epsilon, Số 13, 02/2017 biết nhiều hơn qua cái tên Dr. Seuss. Phần còn lại là lịch sử. Trong top 100 các sách thiếu nhi bán chạy nhất mọi thời đại, 16 quyển là của Dr. Seuss. Ông viết khoảng 60 sách thiếu nhi, bán được cỡ 220 triệu bản. Thế nhỡ những người như Rowling và Dr. Seuss gia nhập hội mười xu sấp hơi sớm một chút thì sao? Một tác giả Mỹ đã nhận toàn xu sấp, và tự tử chết. Mẹ ông ta đem một bản thảo đến nhà văn Walker Percy và Percy giúp đem in. Bản thảo nọ là quyển A Confederacy of Dunces. Tác giả đã chết tên là John Kennedy Toole. Năm 1981, tiểu thuyết này được có mỗi . . . giải Pulitzer. Trong thế giới điện ảnh (ĐA), xu ngửa = phim có lời nhiều, xu sấp = phim lời ít. Các hội sấp ngửa tương tự như thế giới VH nhiều không kể xiết (xem thêm [6] có nhiều ví dụ). 4. Các bệnh viện phụ sản có đồng hồ nguyên tử Chiêm tinh học là một giáo phái xu ngửa có truyền thống vài nghìn năm. Các tín đồ tin rằng giờ/ngày/tháng/năm sinh và vị trí trăng sao có thể dùng để đoán vận mệnh, tính cách cá nhân và các sự kiện xã hội. Không ít nghiên cứu khoa học đã cho thấy chiêm tinh học đoán chính xác bằng với ... đoán bừa [1, 5]. Gần đây hơn, các nhà khoa học đã ghi lại hành trình cá nhân của 2000 người sinh trong khoảng vài phút của nhau, hồi đầu tháng 3 năm 1958, mà theo chiêm tinh học thì họ sẽ có “số phận” tương tự. Họ đánh giá khoảng 100 đặc điểm, bao gồm chỉ số IQ, nghề nghiệp, sức khỏe tinh thần, khả năng nghệ thuật, toán học, khoa học, thể thao, khả năng đọc, viết, vân vân. Đây là tất cả các đặc điểm mà chiêm tinh học khẳng định có thể “đoán” dùng hồ sơ khai sinh. Kết quả là Chiêm Tinh Học hoàn toàn sai [2]. Tín đồ chiêm tinh học cãi: “cách nhau vài phút là làm số phận khác nhau lắm rồi”. Thế nhưng nếu bạn đi xem chiêm tinh gia đoán số phận thì họ sẽ vui lòng lấy dữ liệu ngày giờ sinh rất không chính xác mà bạn đưa ra. Bạn có bao giờ đi một cái bệnh viện phụ sản mà ở đó có đồng hồ nguyên tử, hay đồng hồ caesium chưa? Mà đồng hồ nguyên tử cũng chỉ đúng đến 1 phần 10 mũ 10 giây thôi. Vả lại, kể cả khi có đồng hồ nguyên tử thì tính giờ sinh từ lúc nào nhỉ? Ông bố đứng bên cạnh cầm đồng hồ (nguyên tử) quả lắc, nhăm nhăm thấy bà mụ vừa lấy con mình ra là .. bấm ngay à? Nếu thò cái đầu ra thì có gọi là “ra đời” chưa? Nếu phải ra ngoài hẳn thì mới tính vào giờ sinh thì những đứa bé chết trong các ca sinh khó khăn là không có “số mệnh” à? Còn những đứa bé phải mổ thì tính giờ sinh thế nào? Lý luận như trên của tín đồ chiêm tinh thuộc về vương quốc tất cả các đồng xu hai mặt đều ngửa. Đoán kiểu nào cũng đúng, bằng chứng ngược kiểu gì cũng sai. Trong vương quốc này, hiệu ứng Forer được thấy ở khắp nơi. Năm 1948, nhà tâm lý học Bertram R. Forer đưa cho sinh viên của ông một bộ câu hỏi xác định cá tính2. Sau khi các sinh viên trả lời bộ câu hỏi xong, thì mỗi sinh viên nhận được một bản “đánh giá cá tính” dựa trên các câu trả lời của bản thân sinh viên họ. 2Personality test 12 Tạp chí Epsilon, Số 13, 02/2017 Mỗi sinh viên sẽ chấm điểm bản đánh giá cá tính của bản thân mình xem đúng hay sai, điểm từ 0 (hoàn toàn sai) đến 5 (hoàn toàn đúng). Các bản đánh giá cá tính này được các sinh viên cho điểm trung bình 4.26: rất ấn tượng! Chỉ có một vấn đề nhỏ: Ferer đã phát cho tất cả các sinh viên cùng một bản đánh giá cá tính mà ông chép lại từ các horoscopes nhan nhản trên các tạp chí. Bản đánh giá cá tính này có nội dung như sau: Bạn có nhu cầu là người khác ngưỡng mộ bạn, tuy nhiên bạn khá nghiêm khắc với bản thân. Mặc dù bạn có một vài nhược điểm trong tích cách, con người bạn có cách khác để khắc phục các nhược điểm này. Bạn có nhiều khả năng tiềm tàng mà bạn chưa chuyển chúng thành lợi thế được. Nhìn bên ngoài thì bạn có kỷ luật, tự kiểm được bản thân, nhưng bên trong thì bạn không tự tin lắm. Thỉnh thoảng bạn rất nghi ngờ rằng bạn đã có các quyết định đúng đắn hay chưa, hoặc có làm việc đúng đạo lý hay không. Bạn thích có một chút thay đổi và sự đa dạng, và cảm thấy không thoả mãn khi bị gò bó, giới hạn. Bạn tự hào là con người suy nghĩ độc lập; và không chấp nhận dễ dàng các ý kiến của người khác mà không có bằng chứng. Bạn đã nhận ra rằng quá thành tâm bộc lộ mình không phải là điều khôn ngoan. Đôi lúc bạn không sống quá nội tâm, giao thiệp rộng, nhưng lại cũng có những lúc sống tâm trạng, cố thủ. Một vài mơ ước của bạn không thực tế lắm. Các chiêm tinh gia là các nhà tâm lý đại tài, nhưng khả năng dự đoán tương lai của họ thì bằng với khả năng bệnh viên phụ sản Từ Dũ có đồng hồ nguyên tử trên từng giường đẻ. Vài chục năm trước, một người Tây Ban Nha trúng sổ số độc đắc. Chuỗi số độc đắc kết thúc bằng con số 48. Rất tự hào về “thành tựu” của mình, ông ta tiết lộ bí mật: “tôi nằm mơ thấy số 7 trong 7 đêm liền, mà 7 lần 7 là 48, do đó tôi tìm mua các số kết thúc bằng 48, nhờ đó trúng độc đắc”. Ông này có thể bầu làm vua của vương quốc các đồng xu 2 mặt ngửa.3 5. Bọn cướp biển và hiện tượng ấm toàn cầu Năm 2005, ban giáo dục tiểu ban Kansas đòi dạy “Intelligent Design” — một thông điệp tôn giáo giả danh khoa học — trong các trường phổ thông. Để minh họa cho tính nhố nhăng của lý luận của ban giáo dục, Bobby Henderson đã làm một cái sơ đồ (Hình 1) so sánh tổng số cướp biển và nhiệt độ toàn cầu (xem ảnh), và sau đó thành lập đại giáo phái Quỷ Mì Ý Bay4có đến vài chục triệu tín đồ (để chế diễu ban giáo dục nọ). Chúng ta sẽ bàn về giáo phái Quỷ Mì Ý Bay trong một dịp khác, điều ta cần là cái sơ đồ giảm cướp biển thì tăng nhiệt độ toàn cầu ở trên. Một giáo phái xu ngửa có rất nhiều tín đồ có tên là Objectivism. Giáo chủ là Ayn Rand, với Alan Greenspan là một (cựu) giáo dân. Sau vụ khủng hoảng tài chính năm 2008, Greenspan thừa nhận5: 3Xem Stanley Meisler, Spain lottery — Not even war stops it. Los Angeles Times, Dec 30, 1977. 4Church of Flying Spaghetti Monster 5http://www.nytimes.com/2008/10/23/business/worldbusiness/23iht-gspan.4. 17206624.html 13 Tạp chí Epsilon, Số 13, 02/2017 Hình 1: Đồng biến giữa số cướp biển và nhiệt độ toàn cầu “Tôi đã sai lầm khi tin rằng vì lợi ích bản thân, các tổ chức – đặc biệt là là các ngân hàng – sẽ cố bảo vệ cổ đông và tiền mặt của chính họ.” Khoan xét đến việc Objectivism là đúng hay sai (tín đồ của họ bảo vệ tới cùng, cho rằng Greeenspan không phải là free marketeer thật sự), trong riêng thế giới của Greenspan thì năm 2008 cướp biển không giảm mà quả đất vẫn ấm lên. 6. Shakespeare và một triệu con khỉ Định lý vô hạn các con khỉ6 đại khái nói rằng, cho thật nhiều các con khỉ gõ lung tung vào các bàn phím, thì với xác suất cực gần với 1, chúng sẽ gõ được Hamlet của Shakespeare. Ta có thể chứng minh điều này bằng lý thuyết xác suất không khó khăn gì (xem Mục 10). Trong một hội nghị năm 1996, Robert Wilensky nói: Chúng ta từng nghe bảo rằng một triệu con khỉ ngồi ở một triệu bàn phím có thể gõ toàn bộ các tuyệt tác của Shakespeare. Bây giờ, may nhờ có Internet, ta biết rằng điều này không đúng sự thật. Con khỉ đang gõ bài này thấy rất nhột. Các nhà nghiên cứu tại trường đại học Plymouth ở Anh đã thí nghiệm hồi năm 2003: bỏ một máy tính vào chuồng khỉ ở vườn thú Paignton ở Tây Nam nước Anh. Bọn khỉ lấy đá đập tán loạn vào máy tính; sau đó thì tiểu tiện, đại tiện vào bàn phím, cuối cùng mới gõ một đống chữ S, và 6https://en.wikipedia.org/wiki/Infinite_monkey_theorem 14 Tạp chí Epsilon, Số 13, 02/2017 vài chữ A, J, L, M, cho ra 5 trang sản phẩm. Mike Phillips, một trong số các nhà nghiên cứu này, nói: “rõ ràng tiếng Anh không phải tiếng mẹ đẻ của khỉ”. Gạt đùa bỡn sang một bên. Định lý khỉ thật sự nói rằng, bất kỳ cái gì — nếu tồn tại — thì dù hiếm hoi đến mấy mà có đủ người tìm thì tìm vẫn ra. Thậm chí không cần một “chiến lược” tìm kiếm gì cả. Các con khỉ chỉ gõ loạn cào cào lên thôi. Bỏ một cây kim lên bãi cát. Một người vốc 10 nắm cát bất kỳ thì khả năng tìm ra kim trong đó là không tưởng. Nhưng nếu có một triệu người, mỗi người vốc 10 nắm cát bất kỳ, thì nhiều khả năng là tìm được kim. Khi độ hiếm hoi giảm xuống (đến không hiếm hoi) thì tổng số khỉ cần thiết sẽ giảm xuống. Nếu một nửa bãi cát có kim thì chỉ cần một gã vốc một nắm cát là đủ. Nếu một gã nào đó trong một triệu gã tìm kim bãi cát ở trên mà tìm được kim thì không phải hắn có công năng đặc dị gì. Con khỉ gõ được Hamlet thì vẫn là con khỉ. Điểm này được Taleb lập đi lập lại trong hai quyển Fooled by Randomness [8] và The Black Swan [9]. Chỉ cần sự ngẫu nhiên, một vài mutual funds sẽ có những thời điểm lời khủng khiếp, một vài cá nhân sẽ có những thành công vượt bực (Bill Miller của Legg Mason Capital Management chẳng hạn). Những hội sấp ngửa “sống sót” trong vương quốc NN là hoàn toàn ngẫu nhiên, có thể chứng minh được bằng lý thuyết xác suất (xem Mục 10). 7. Từ công ty đoán giá chứng khoán đến hợp tác xã đánh đề Mỗi sáng chủ nhật, bạn nhận được một email từ công ty Đoán Giá Xì Tốc Inc. dự đoán giá chứng khoán của AT&T tuần tới sẽ tăng hay giảm. Email này để minh chứng là họ nói đúng, và nói với bạn rằng nếu bạn trả cho họ 100USD, họ sẽ gửi dự đoán tuần kế tiếp cho. Hơn thế nữa, công ty Đoán Giá Xì Tốc Inc. sẽ bồi hoàn toàn bộ 100USD nếu họ đoán sai. Hấp dẫn chưa? Bạn chưa tin tưởng lắm, vì sợ họ lừa đảo gì đó. Tuần sau, bạn thấy họ đã đoán đúng tuần trước, và lại nhận được một email y chang như thế. Họ đoán đúng liên tục 7 tuần liền! À ha. Chắc công ty này (CEO tên là NQH) phải sở hữu thiên tài đoán giá xì tốc. Đến đây thì bạn tin sái cổ. Xác suất đoán ngẫu nhiên mà trúng 7 lần liên tục là 1/128, rất thấp! Công ty đó có “thiên tài” thế này. Tuần đầu tiên họ gửi email đến 128 người, một nửa số đó đoán stock tăng, một nửa đoán stock giảm. Tuần sau họ chỉ gửi email đến 64 người mà lượt email đầu đã đoán trúng! Cứ thế 7 tuần liền. Dĩ nhiên, họ không chỉ gửi ra 128 emails mà sẽ gửi 128 triệu email. Nếu chỉ 1/100 số người nhận “7 lần đoán trúng” này bị lừa, cho họ 100USD, thì họ đã kiếm được 10 triệu USD trong 7 tuần. Chẳng qua, bạn tin “thiên tài” của họ vì bạn chỉ có bằng chứng “khẳng định” cái thiên tài đó mà không biết về các bằng chứng phủ định. Tất cả các thành viên hội xu ngửa trong vương quốc NN đều mắc phải lỗi này, gọi là lỗi “thiên kiến khẳng định” (confirmation bias). Báo Tuổi Trẻ ngày 30/8/2008 đưa tin sau đây: TT (TP.HCM) – Chiều 30-8, Cục Cảnh sát điều tra tội phạm về trật tự xã hội (C14) – Bộ Công an đã tống đạt quyết định khởi tố bị can và đồng loạt thực hiện lệnh 15 Tạp chí Epsilon, Số 13, 02/2017 khám xét nhà riêng, bắt tạm giam sáu người về hành vi lừa đảo chiếm đoạt tài sản. Các đối tượng này là những mắt xích quan trọng trong đường dây lừa đảo kết quả xổ số kiến thiết (XSKT) có qui mô trên toàn quốc vừa bị lực lượng C14 phối hợp với Công an tỉnh Quảng Bình triệt phá vào tháng tám vừa qua. Trước đó đã có bốn người khác liên quan trong đường dây này bị khởi tố, bắt tạm giam cùng hành vi lừa đảo. Theo điều tra, những người trong đường dây này đã mạo danh người của công ty XSKT các địa phương, khu vực trên toàn quốc, hằng ngày gọi điện thoại cho hàng ngàn người ở khắp các tỉnh thành và cho mỗi người một con số. Chúng quả quyết đó là số “trúng” do công ty XSKT “làm” và yêu cầu người được cho nên mua (vé số) hoặc đánh đề lô số đó. Cứ mỗi tên trong đường dây có nhiệm vụ điện thoại hơn 100 người/ngày và cho mỗi người một số theo thứ tự từ số 00 đến số 99. 8. Khi những con giun đất hiển linh Hình 2: Bộ mặt trên sao Hỏa, 1976 Năm 1986, phi thuyền Viking I bay quanh sao Hỏa chụp ảnh. Qua vùng Cydonia phi thuyền này đã chụp được một vùng đồi núi mà dưới bóng sáng tối trong giống mặt người (giống một Pharaoh Ai Cập). Ảnh này (Hình 2) lại được các “lý thuyết gia” conspiracy theorists vẽ ra đủ thứ lý thuyết lăng nhăng cộng với cả phim ảnh và talk shows. Hình 3 là ảnh chụp hồi 2001: Các nhà khoa học ở NASA thấy thích thú về bức ảnh . . . rồi thôi, vì họ có nhiều việc quan trọng để làm. Trong một mớ hỗn mang rộng lớn, bao giờ cũng có các góc nhỏ có một trật tự nào đó. Hiện tượng này xuất hiện rất nhiều trong phương pháp xác suất, theo nghĩa của Paul Erdos, khi ta chứng minh rằng trong một không gian mẫu đủ lớn thì các trật tự cục bộ7sẽ tồn tại. Nhìn mãi lên mây sẽ thấy một số đám mây trông giống con rồng, con chó, con ... giun đất. Không hiểu tại sao đến bây giờ người ta không viết truyền thuyết về con giun đất hiển linh. Trong mớ hỗn mang nhân quả của hiện tượng ấm toàn cầu, cái “trật tự” cướp biển giảm làm tăng nhiệt độ quả đất không dùng để kết luận ra cái gì được hết! 7Local pattern 16 Tạp chí Epsilon, Số 13, 02/2017 Hình 3: Bộ mặt trên sao Hỏa, 2001 9. Vượt định kiến bằng Lăng Ba Vi Bộ Hội viên hội xu ngửa đã có mô hình sai vì họ khái quát hóa từ một vài “mẫu” địa phương. Nhiều định kiến xuất phát từ cùng một lỗi như thế. Ai đó gặp vài anh Việt Kiều rồi kết luận Việt Kiều ở Mỹ làm nails đánh bài. Người khác gặp vài anh du học sinh rồi kết luận du học sinh Việt Nam ở bẩn và không biết xem bóng bầu dục. Thử tưởng tượng Rowling kết luận, sau 12 lần bị từ chối, rằng Harry Potter sẽ không bao giờ được nhận xuất bản. Những đồng xu trong vương quốc NN được ném độc lập với nhau. Trong cuộc sống chúng ta thường gặp các đồng xu xâu lại với nhau thành chuỗi bằng một sợi dây vô hình nào đó. Người Bắc có nhiều bạn bè người Bắc, Người Nam có nhiều bạn bè người Nam, họ giúp nhau thắt chặt những định kiến vùng miền. Kết quả của đồng xu kế tiếp “đồng biến”8chặt chẽ với đồng xu trước. Gia đình ba mẹ tin vào chiêm tinh học sẽ tiêm nhiễm cho con niềm tin này. Đồng xu của em bé vừa ra đời đã có mặt nặng mặt nhẹ. Giả sử ta có một ly nước chanh, có đường ở dưới nhưng chưa khuấy lên, thì không thể nếm nước trên bề mặt (cho dù nếm cả ngụm) để kết luận là ly nước không có đường. Đầu tiên phải khuấy nó lên. Tiếc rằng, trên thực tế thì không thể “khuấy” Việt Kiều không làm móng tay và Việt Kiều làm móng tay rồi mới làm bạn ngẫu nhiên với họ. Nhưng điều có thể làm là nếm ly nước ở nhiều chỗ: bên phải một cái, dưới đáy một cái, bên trái một cái, v.v. Phương pháp này trong lý thuyết xác suất gọi là phương pháp Monte Carlo. Nhưng làm bạn với Việt Kiều Cali, New York, Chicago, Ithaca, v.v. một cách ngẫu nhiên như thế cũng rất khó vì giới hạn Vật Lý. Có thể phần nào giải quyết tình trạng này bằng Markov Chain Monte Carlo, gọi nôm na là Lăng Ba Vi Bộ. 8Correlate 17 Tạp chí Epsilon, Số 13, 02/2017 Một phần không nhỏ những gì diễn ra trong cuộc sống và xã hội là kết quả của sự ngẫu nhiên (NN). Trong một miền hỗn mang to lớn, nếu nhìn vào một góc nhỏ nào đó ta có thể tìm được một trật tự nhất định. Trật tự đó chẳng có ý nghĩa gì ghê gớm. Không thể đánh giá con người hay sự vật/việc chỉ dùng kết quả thành bại được. Sẽ là một lỗi logic cơ bản nếu bài này kết luận rằng tất cả thành bại đều do ngẫu nhiên (vì các loại ví dụ kể trên chỉ là một số đồng tiền ngửa ủng hộ luận điểm này!). Dĩ nhiên tài năng có ảnh hưởng đến kết quả, nhưng con người có xu hướng đánh giá thấp vai trò của sự ngẫu nhiên. Sẽ có ít định kiến hơn nếu chúng ta hiểu ý nghĩa của xác suất, không bước trên lối mòn định sẵn mà cần “Lăng Ba Vi Bộ” tìm Thiên Nga Đen. Nếu thi thoảng có gặp nhiều xu sấp, thì không nên gia nhập hội xu sấp ngay. Đây là lý do tại sao những người kiên trì thường thành công, thiên tài có thể “tu luyện” được. Ngược lại, Einstein cảnh báo rằng: “định nghĩa của sự điên rồ là làm một thứ lập đi lập lại mà mong đợi kết quả khác nhau”. Cuối cùng: thế nhỡ đâu tất cả những gì nhân loại chứng kiến/đo đạc được cho đến nay đều là xu ngửa thì sao? Nhỡ đâu ba định luật Newton và sự tiến hóa sinh vật cũng là xu ngửa. Nhỡ đâu mai mặt trời không mọc nữa và quả đất xoay chiều? Đây là vấn đề qui nạp9của David Hume, vượt quá khuôn khổ bài viết. Rất hy vọng có thể quay lại đề tài này trong một bài viết tới. 10. Một ít tính toán Đã đến lúc chúng ta trả lại một ít chặt chẽ Toán học cho bài viết. 10.1. Mười xu ngửa và định lý khỉ vô hạn Giả sử anh Tám Tàng ở vương quốc NN thảy n đồng xu với xác suất xấp ngửa là 1/2. Thì xác suất có n mặt ngửa là 1/2n. Xác suất mà n đồng xu cho ra một pattern xấp ngửa tuỳ ý cũng là 1/2n; bộ pattern “tất cả đều ngửa” chẳng có ý nghĩa đặc biệt gì. Nếu vương quốc NN có N anh Tám Tàng, thì tính trung bình sẽ có N/2ncông dân đều thảy được n xu ngửa. Do đó, với N = 108, n = 10, ta biết là tính trung bình có khoảng 108/210 ≈ 100, 000 (trăm nghìn) công dân thảy được 10 đồng tiền ngửa liên tục. Điều này đúng với tất cả 210 = 1024 patterns xấp ngửa. Còn nếu n = 17 thì vẫn sẽ có cỡ 108/217 ≈ 750 người có cùng pattern sấp ngửa. Nguyên tắc này có thể áp dụng ở chỗ khác với xác suất khác. Giả sử Tám Tàng chọn mua chứng khoán ngẫu nhiên, với xác suất “đầu tư” có lời là 1/2 mỗi năm. (Khi kinh tế đang phát triển thì mua bừa mấy cái chứng khoán Blue Chip có lời còn chắc hơn 1/2.) Vậy thì xác suất mà Tám Tàng có lời 15 năm liên tục là 1/215. Trong 100 triệu nhà đầu tư ngẫu nhiên như vậy, sẽ có khoảng 108/215 ≈ 3000 nhà đầu tư có lời liên tục 15 năm liền. Về định lý vô hạn khỉ, ta biết rằng Hamlet có 30,557 từ, mỗi từ cùng lắm là 20 ký tự, và do đó Hamlet có ít hơn 105 ký tự. Một con khỉ gõ ngẫu nhiên một chuối 105 ký tự, trong bộ ký tự 26 9https://plato.stanford.edu/entries/induction-problem/ 18 Tạp chí Epsilon, Số 13, 02/2017 ký tự, thì xác suất mà nó gõ được Hamlet là p = 26−105. Tất nhiên là xác suất này rất nhỏ. Giả sử ta có N con khỉ, mỗi con gõ độc lập 105 ký tự. Gọi X là số khỉ số khỉ gõ được Hamlet, thì E[X] = Np (trị kỳ vọng của X). Gõ được Hamlet = xu ngửa, gõ linh tinh = xu xấp. Chọn N sao cho Np ≥ 8, dùng bất đẳng thức Chernoff 10, ta có Prob[X < Np/2] <1 eN p/8 và do đó khi N lớn, không những là có một con khỉ gõ được Hamlet, mà có ít nhất Np/2 khỉ gõ được, với xác suất tiến đến 1. 10.2. Trật tự cục bộ và số Ramsey Một party ở vương quốc NN có 6 người tham dự. Bạn có thể chứng minh rằng trong 6 người đó luôn tồn tại 3 người từng cặp quen nhau, hoặc 3 người từng cặp không quen nhau (bài tập!). Tổng quát hơn một chút, giả sử ta muốn chứng minh một khẳng định sau: “trong một party N người tham dự, luôn có m người từng cặp quen nhau hoặc n người từng cặp không quen nhau”. Ta chọn (N, m, n) như thế nào để chứng minh khẳng định này? Ta sẽ chứng minh rằng, với N đủ lớn (so với m, n), thì khẳng định trên luôn đúng. Khẳng định này là một ví dụ của phát biểu ở trên, rằng “trong một mớ hỗn mang đủ lớn, luôn tồn tại một trật tự cục bộ”. Trong một party lớn, tìm thấy một nhóm người quen lẫn nhau thì không có gì đáng ngạc nhiên cả. Ramsey [7] trả lời câu hỏi trên bằng cách gọi R(m, n) là số nguyên N nhỏ nhất sao cho khẳng định trên là đúng, và chứung minh một chặn trên cho R(m, n). Ta theo Erdos và Szekeres [ ˝ 3] chứng minh một chặn trên đẹp: R(m, n) ≤ R(m − 1, n) + R(m, n − 1). Xét một party có N = R(m − 1, n) + R(m, n − 1) người. Chọn một anh Tám Tàng bất kỳ và phân hoạch những người còn lại tại hai tập: tập X người quen Tám Tàng, và Y người không quen tám tàng. Như vậy N = 1 + |X| + |Y |, và do đó hoặc |X| ≥ R(m − 1, n) hoặc |Y | ≥ R(m, n − 1). Giả sử |X| ≥ R(m − 1, n) thì ta tìm được m − 1 người quen lẫn nhau trong tập X hoặc n người từng cặp không quen trong tập X. Nếu có n người từng cặp không quen thì ta xong. Nếu có m − 1 người quen lẫn nhau, thì họ cùng với Tám Tàng tạo thành m người quen lẫn nhau. Từ bất đẳng thức R(m, n) ≤ R(m − 1, n) + R(m, n − 1), bằng quy nạp ta chứng minh được R(m + 1, n + 1) ≤m+n n (bài tập!). Tìm chặn trên cho các số Ramsey R(m, n) và tổng quát hoá của chúng là một nhánh nghiên cứu thú vị và rất khó của toán tổ hợp hiện đại [4]. Paul Erdos chứng minh chặn dưới cho ˝ R(n, n), dùng lý luận sau đây. Có tất cả 2(N2 )cách để cấu thành một tổ hợp quen/không quen của tất cả những người tham dự party. Gọi S là một tập n người nào đó; gọi S là tập “đơn sắc” nếu những người trong S quen nhau từng cặp hoặc không quen nhau từng cặp. Trong số 2(N2 )tổ hợp trên, có đúng 2×2(N2 )−(n2)tổ hợp mà S là tập đơn sắc. Để dễ hình dung, tưởng tượng một đồ thị hai phần, bên trái là 2(N2 )tổ hợp, bên phải là Nn cách chọn tập S. Ta nối S với một tổ hợp bên trái nếu S là tập đơn sắc cho tổ hợp đó. Thì, các đỉnh bên phải có bậc là 21+(N2 )−(n2). (Theo nguyên tắc Dirichlet, ta có thể nghĩ về S như một chuồng 10http://www.cse.buffalo.edu/~hungngo/classes/2011/Fall-694/lectures/tail. pdf 19 Tạp chí Epsilon, Số 13, 02/2017 bồ câu, và mỗi tổ hợp là một con bồ câu.) Nếu 2(N2 ) >Nn 21+(N2 )−(n2), thì tồn tại một tổ hợp không “nối” với tập đơn sắc nào, và do đó R(n, n) > N. Giả sử n ≥ 3, ta chọn N = b2n/2c. Thì, N n 21+(N2 )−(n2) b2n/2c. Tài liệu [1] CARLSON, S. A double-blind test of astrology. Nature 318 (1985), 419–425. [2] DEAN, G., MATHER, A., NIAS, D., AND SMIT, R. Tests of astrology: A critical review of hundreds of studies, 2016. [3] ERDOS¨ , P., AND SZEKERES, G. A combinatorial problem in geometry. Compositio Math. 2 (1935), 463–470. [4] GRAHAM, R. L., ROTHSCHILD, B. L., AND SPENCER, J. H. Ramsey theory, second ed. Wiley-Interscience Series in Discrete Mathematics and Optimization. John Wiley & Sons, Inc., New York, 1990. A Wiley-Interscience Publication. [5] MADDOX, J. Defending science against anti-science. Nature: International weekly journal of science 368, 6468 (1994), 185. [6] MLODINOW, L. The Drunkard’s Walk: How Randomness Rules Our Lives. Pantheon, May 2008. [7] RAMSEY, F. P. On a Problem of Formal Logic. Proc. London Math. Soc. S2-30, 1, 264. [8] TALEB, N. Fooled by randomness: The hidden role of chance in life and in the markets, vol. 1. Random House Incorporated, 2005. [9] TALEB, N. N. The black swan: The impact of the highly improbable, vol. 2. Random house, 2007. 20 Tạp chí Epsilon, Số 13, 02/2017 QUAN NIỆM CỦA KANT VỀ KHÔNG GIAN VÀ THỜI GIAN Nguyễn Ái Việt (Viện Công Nghệ Thông Tin, Đại Học Quốc gia Hà Nội) TÓM TẮT Chúng ta đều nhận thức không gian mà chúng ta đang sống gắn liền với một khái niệm toán học, đó là không gian Euclide 3 chiều. Chúng ta coi điều đó là hiển nhiên từ giáo trình hình học không gian ở trường trung học. Những người chịu khó tìm hiểu hơn một chút, sẽ biết thêm không thời gian là không gian Euclide 4 chiều, thêm một chiều thời gian. Tuy nhiên, giữa khái niệm toán học và không gian, thời gian là một khoảng cách, có thể dẫn tới việc xem xét lại việc sử dụng khái niệm toán học có phù hợp hay không. Việc gán ghép không gian và thời gian với các không gian Euclide không hoàn toàn hiển nhiên. Chúng ta hãy xem nhà triết học Imannuel Kant quan niệm thế nào về không thời gian. Từ những quan niệm đó chúng ta có thể đặt những câu hỏi gì và có thể tìm những khái niệm toán học mới phù hợp hơn ra sao. Có thể trong tương lai, chúng ta sẽ phát hiện ra rằng không thời gian mà chúng ta đang sống sẽ có những cấu trúc toán học khác xa với những gì chúng ta đang sử dụng hôm nay. Quan niệm về không thời gian Trước Kant, Newton đã đưa ra khái niệm không gian và thời gian tuyệt đối [1]. Leibnitz ngược lại, cho rằng không gian và thời gian là tương đối, phụ thuộc vào vật chất, vì vậy con người nhận thức được không gian và thời gian nhờ quan sát vật chất vận động [1]. Không có vật chất, không gian và thời gian không tồn tại. Kant đưa ra quan niệm phức tạp hơn: không gian và thời gian là trực giác tiên nghiệm (à priori). Mặc dù quan niệm của Kant về không thời gian phủ định quan niệm về không gian và thời gian tuyệt đối tồn tại khách quan ngoài ý thức của Newton, quan niệm của ông cũng phủ nhận quan niệm của Leibnitz, khi cho rằng không gian và thời gian tồn tại trong ý thức trước khi có quan sát về nó. Quan niệm của Kant dựa trên phương pháp luận rất tinh tế về nhận thức. 1. Phương pháp luận của Kant về "cảm giác" và "trực giác" Theo Kant [2], ý thức được chia thành "ý thức chủ quan", gồm các "cảm giác" (sensation) và "ý thức khách quan", gồm "trực giác"(intuition) và "khái niệm"(concept). Việc phân chia này rất 21 tinh tế, cần phải nhận chân thật kỹ để tránh hiểu sai. Tạp chí Epsilon, Số 13, 02/2017 Với cách phân tích này, chúng ta sẽ lần lượt xét các câu hỏi sau. Câu hỏi thứ nhất, "cảm giác" có hoàn toàn chủ quan hay không? Nếu chúng ta thừa nhận việc có cảm giác là nhờ tiếp xúc với thực tế khách quan. Câu hỏi thứ hai cũng có liên quan tới câu hỏi thứ nhất, liệu "trực giác" là hình dung về sự vật cụ thể có hoàn toàn khách quan hay không? Xét đồng thời cả hai câu hỏi này, chúng ta có thể thấy Kant đã tách nhận biết của chúng ta thành hai phần riêng biệt, phần khách quan được định nghĩa là trực giác, phần chủ quan được định nghĩa là cảm giác. Tuy vậy, ở đây có vấn đề việc tách nhận biết như vậy có khả thi hay không? Vẫn có thể có khả năng trong cảm giác có thể có một phần khách quan, trong trực giác cũng có thể có một chút chủ quan. Cũng tương tự với việc cái lỗ trong cục pho mát không thể nào cắt được ra khỏi miếng pho mát mà không có một chút pho mát nào còn lại. "Cảm giác" hoàn toàn chủ quan, chỉ phụ thuộc vào chủ thể cảm nhận và "trực giác" hoàn toàn khách quan không chắc luôn luôn tồn tại. Kant không chỉ được ra một quy trình tách bạch cụ thể mà chỉ giả định có một quy trình như thế để tách cảm giác khỏi trực giác. Vì thế đây là một giả thuyết rất mạnh của Kant. Phương pháp luận của Kant về "trực giác" và "khái niệm" Việc phân biệt "trực giác" và "khái niệm" của Kant cũng đem lại nhiều cầu hỏi. Cho đến tận gần đây, người ta vẫn còn cố gắng tìm hiểu sự khác biệt giữa hai loại nhận thức này. Nếu đọc thật kỹ các tác phẩm của Kant, có thể thấy ông cho "trực giác" là các nhận thức đơn thể, trong khi "khái niệm" là khái quát hóa của các trực giác, không có tính đơn thể. Ví dụ "con bò nhà tôi" hay "con bò đen của nhà hàng xóm" là hai trực giác, có thể không liên quan đến nhau cho đến khi có khái niệm con bò có thể dùng để gợi ra hình dung có thể liên hệ với bất cứ con bò nào. Một cách toán học, khái niệm là bất biến với một số phép biến đổi giữa các trực giác, chẳng hạn đổi chỗ "con bò của tôi" với "con bò của nhà hàng xóm" có thể ảnh hưởng tới các khái niệm khác, nhưng không hề ảnh hưởng tới khái niệm con bò. Ngược với trực giác là nhận thức đơn thể, khái niệm có thể chia cắt được thành các khái niệm thành phần có thể định nghĩa độc lập với nhận thức về khái niệm ban đầu. Chính vì thế khái niệm có thể định nghĩa qua các khái niệm thành phần. Chẳng hạn tam giác có thể định nghĩa qua các đỉnh, các cạnh hoặc các góc. Các cạnh có thể định nghĩa từ các điểm. Vì khái niệm luôn có thể chia cắt thành các khái niệm, việc chia cắt này có thể thực hiện vô hạn. Tôi nghi ngờ ở quan niệm này của Kant. Hoặc có thể tôi bỏ sót ở một khâu nào đó chưa hiểu hết về việc chia cắt này, tôi vẫn nghĩ rằng quá trình chia cắt này phải dừng lại sau hữu hạn bước. Trong thực tế, không ai có thể nhận thức được vô hạn khái niệm. Mặt khác, trong vật lý ngày nay, các hạt cơ bản như quark, lepton và photon không thể chia cắt. Cũng có một cách phân tích khác về nguyên tắc có thể vô hạn, đó là khái niệm tam giác có thể tách ra thành tam giác cân và tam giác không cân. Tập tam giác cân lại tách ra thành tam giác đều và không đều,... Cứ mỗi lần thêm thuộc tính chúng ta có thể hạn chế khái niệm về một tập các khái niệm nhỏ hơn. Về nguyên tắc, chúng ta có thể thêm vô hạn thuộc tính. Tuy nhiên, trong thực tiễn, chỉ sau một vài bước phân tích người ta sẽ quay trở lại khái niệm ban đầu. Sau khi nhận thức được khái niệm ban đầu, người ta sẽ liên hệ được với mọi trường hợp riêng. 22 Tạp chí Epsilon, Số 13, 02/2017 Phương pháp luận của Kant về "thực nghiệm" và "tiên nghiệm" Kant lại tiếp tục chia các "khái niệm" và "trực giác" thành hai loại "thực nghiệm" (empirical) và "tiên nghiệm" (a priori). Ông gọi các "khái niệm" và "trực giác" tiên nghiệm (phi thực nghiệm) là "thuần túy". Ở đây cũng nảy sinh ra câu hỏi thứ tư, theo tôi là trầm trọng nhất. Làm thế nào có một ý thức khách quan đơn thể mà không cần đến thực nghiệm? Nói một cách khác, "trực giác" tiên nghiệm hình thành trong ý thức của chúng ta thế nào? Theo Kant [2], không gian và thời gian là "trực giác thuần túy". Ông lập luận rằng không gian và thời gian là các đối tượng cá thể, chỉ có duy nhất nên không thể khái quát hóa. Mặt khác, chúng cũng không thể chia tách thành các thành phần nhỏ, có thể xác định trước khi có hình dung về không gian và thời gian. Chẳng hạn, thời gian gồm các khoảnh khắc, quãng thời gian, không gian bao gồm các địa điểm, vị trí. Chúng ta không thể hình dung ra được thế nào khoảnh khắc, địa điểm mà không biết trước về thời gian và không gian. Kant nhấn mạnh rằng không gian và thời gian không dựa trên quan sát thực nghiệm. Khi chúng ta nói rằng không có gì, chúng ta đã có sẵn hình dung về một không gian trống rỗng và khi nói về một đối tượng, nó đã phải ở trong không gian. Như vậy, không gian là trực giác tiên nghiệm làm điểm tựa cho thể hiện bên ngoài. Tương tự, thời gian là trực giác tiên nghiệm bên trong. Tôi có một số nghi vấn về phương pháp ở đây. Thứ nhất, làm thế nào để liên kết "khái niệm" được định nghĩa là khái quát hóa của nhiều trực giác với quan hệ phần tử-toàn thể sử dụng trong lập luận trên. Có vẻ như định nghĩa khái niệm và tính chất chia cắt vô hạn của nó chẳng dính dáng gì đến nhau hoặc dẫm chân lên nhau. Nghi vấn thứ hai, cho dù không gian là một hình dung khách quan không chia cắt được và vì thế không phải là khái niệm (thông thường). Điều gì sẽ đảm bảo nó phải là "trực giác"? Lập luận của Kant cho thấy hình dung khách quan nếu không phải là khái niệm ẮT phải là trực giác. Điều đó đòi hỏi là việc phân chia ý thức khách quan của Kant phải thành hai phần đối lập. Tuy nhiên, có thể định nghĩa trực giác như là ý thức khách quan không (chưa) phải là khái niệm lại dẫm lên định nghĩa về ý thức đơn thể và ý thức khái quát. Có thể ý thức khách quan sẽ bao gồm ít nhất "khái niệm" "trực giác" và "khái niệm đặc biệt" (không gian và thời gian)? Như vậy, tôi không hoàn toàn bị thuyết phục không gian và thời gian là các trực giác. Vì vậy chúng ta sẽ tiếp tục xem xét các hệ luận để khẳng định các nghi vấn đó là có lý hay không có lý. Phủ nhận quan niệm không gian và thời gian của Newton và Leibnitz Trước hết, quan niệm của Kant phủ nhận quan niệm của Leibnitz về không gian và thời gian phụ thuộc vào vật chất, như vậy phải được nhận thức thông qua quan sát vật chất, vì vậy có tính thực nghiệm. Theo Kant, không gian và thời gian có sẵn trong ý thức trước mọi quan sát về vật chất. Điều đó có nghĩa là Kant khẳng định lập trường duy tâm. Ngày nay chúng ta hiểu rằng điều đó gián tiếp công nhận có ý thức thuần túy có sẵn (một định nghĩa tương tự như tâm linh). Ở đây cần nói thêm, tuy không gian và thời gian là tiên nghiệm, nhưng lại khách quan. Có nghĩa là mọi hình dung về không gian và thời gian phải là như nhau. Quan niệm của Kant cũng phủ định quan niệm của Newton về không gian và thời gian tuyệt đối, là thực tế khách quan, do không 23 Tạp chí Epsilon, Số 13, 02/2017 gian và thời gian của Kant tồn tại tiên nghiệm ngay trong ý thức. Quan niệm không gian và thời gian trong lý thuyết tương đối rộng Không thời gian trong thuyết tương đối rộng thường được xem là thống nhất với tương tác hấp dẫn. Năng xung lượng của vật chất sẽ sinh ra hấp dẫn, hấp dẫn sẽ làm cong không thời gian. Tuy nhiên, đây chưa hẳn là minh chứng cho quan niệm của Leibnitz. Trong thuyết tương đối, vật chất có ảnh hưởng tới metric của không thời gian, tức là ảnh hưởng tới đo đạc, quan sát của chúng ta về không thời gian chứ chưa phải là xác định không thời gian. Xuất phát điểm của lý thuyết tương đối rộng là đa tạp không thời gian 4 chiều, hấp dẫn chỉ là thuộc tính của đa tạp này và bị ảnh hưởng bởi vật chất tồn tại trên đa tạp này. Mặt khác, trong lý thuyết tương đối rộng, người ta vẫn nghiên cứu trường hợp không có vật chất, vẫn có tương tác hấp dẫn. Tương tác hấp dẫn phải dựa trên khái niệm không thời gian. Trong lý thuyết dây, không thời gian 4 chiều, hấp dẫn và vật chất đều được suy ra từ các sợi dây trong không gian nhiều chiều hơn. Câu hỏi là vì sao các sợi dây trong không gian nhiều chiều lại không tồn tại tiên nghiệm trong ý thức của chúng ta. Khái niệm về không thời gian của lý thuyết dây có vẻ không phù hợp với quan niệm của Kant. Các khái niệm toán học khác về không thời gian Chúng ta hãy thử áp dụng một vài quan niệm của Kant về không thời gian kết hợp với một số giả thuyết xem có những mô hình toán học nào phù hợp. Trước hết, chúng ta sẽ không nhất thiết phải cho rằng không gian Euclide là tiên nghiệm. Chúng ta sẽ giả thiết yếu hơn: đa tạp 4 chiều sẽ là thành phần tiên nghiệm của không thời gian. Cơ sở để cho thành phần 4 chiều là tiên nghiệm có thêm lý lẽ nếu chúng ta xét từ các quan điểm khác nhau. Về mặt toán học, các đa tạp và không gian topo 4 chiều có một vị trí đặc biệt và là bí ẩn nhất. Trong vật lý, các tích phân Feynman sẽ phân kỳ chỉ nếu như không thời gian là 4 chiều. Trong lý thuyết truyền tin, không thời gian 4 chiều thông tin sẽ được truyền với độ tin cậy cao nhất. Chúng ta sẽ giả thiết thêm là mọi hiện tượng vật lý (ít nhất là các tương tác) đều quy giản được về không thời gian. Nói một cách khác, không thời gian sẽ giải thích được các tương tác và một số quy luật như vi phạm chẵn lẻ, vi phạm đối xứng tự phát. Bên cạnh đó, chúng ta sẽ giả thiết thêm không thời gian phải là tối thiểu và tiết kiệm nhất. Như vậy chúng ta có thể xuất phát từ hình học Cartan-Einstein [3] được khẳng định nhờ thành công của lý thuyết tương đối rộng. Với các giả thiết như vậy, chúng ta thấy lý thuyết dây trong không gian nhiều chiều không đảm bảo "tiết kiệm" do có quá nhiều (vô hạn) đối tượng không quan sát được trong thực nghiệm, mặc dù mọi tương tác, hạt cơ bản chúng ta biết đều có thể quy giản. Các lý thuyết 5,6 và nhiều chiều liên tục không đáp ứng quan niệm về không thời gian 4 chiều tiên nghiệm của Kant, các chiều không gian trong các lý thuyết này đều bình đẳng, không gian 4 chiều không có vai trò gì. 24 Tạp chí Epsilon, Số 13, 02/2017 Trước hết, với không gian M4, E.Wigner [4] đã chứng tỏ rằng mọi hạt cơ bản đều có thể đặc trưng bằng khối lượng và spin. Nói một cách khác các thuộc tính đặc trưng cho hạt cơ bản là khối lượng và spin có thể quy giản về không gian Euclide 4 chiều. Các nghiên cứu gần đây [5] chứng tỏ rằng không thời gian không nhất thiết có cấu trúc Euclide M4 mà có thể có cấu trúc dS4,AdS4 hoặc mở rộng của chúng với các chiều gián đoạn Z2, Khi đó hình học Cartan-Einstein cần mở rộng sử dụng các công cụ của hình học không giao hoán[6]. Chẳng hạn lý thuyết Cartan-Einstein mở rộng cho không thời gian M4 × Z2 × Z2 có thể giải thích được mọi tương tác, vi phạm chẵn lẻ của tương tác điện yếu và giải thích tại sao các lepton quark tay phải lại không tham gia tương tác yếu. Lý thuyết Cartan-Einstein cho không thời gian dS4là một siêu cầu 4 chiều, có thể giải thích cấu trúc SU(2) × U(1) của tương tác yếu. Như vậy không thời gian Euclide không phải là cấu trúc toán duy nhất cho không thời gian, cho dù đa tạp 4 chiều là tiên nghiệm có sẵn trong ý thức của chúng ta theo quan niệm của Kant. Qua đây chúng ta cũng có thể thấy những ý tưởng triết học có thể ảnh hưởng tới khoa học tới hàng trăm năm sau./. Tài liệu tham chiếu [1] A.Grunbaum, Philosophical Problems of Space and Time, 2nd ed. Boston Studies in the ¨ Philosophy of Science. Vol XII. D. Reidel Publishing(1974) [2] I.Kant, Critique of Pure Reason, translated by Paul Guyer and Allen Wood. Cambridge: Cambridge University Press, 1998; Kant, Immanuel, Metaphysical Foundations of Natural Science, in Theoretical Philosophy after 1781, edited by Henry Allison and Peter Heath, translated by Michael Friedman, Cambridge: Cambridge University Press, 2002. [3] Cartan, E. (1922). Comptes Rendus 174, 437-439, 593-595, 734-737, 857-860, 1104- 1107. [4] Wigner, E. P. (1939), "On unitary representations of the inhomogeneous Lorentz group", Annals of Mathematics, 40 (1): 149–204, [5] Nguyen Ai Viet and K.C.Wali, Int.J.Mod.Phys. 11(3), (1996), 533; Nguyen Ai Viet and K.C.Wali, Int.J.Mod.Phys. 11(13), (1996), 2403. [6] A.Connes, Publ.Math. IHES 62 (1986), 41; A.Connes, Noncommutative Geometry, Aca demic Press, San Diego, CA, (1994), 661 p.,ISBN 0-12-185860-X;A.Connes J. Math. Phys. 36 (ii),(1995), 6194. 25 Tạp chí Epsilon, Số 13, 02/2017 TOÁN HỌC VÀ PHÁT HIỆN ẢNH GIẢ MẠO - PHẦN KẾT Đặng Nguyễn Đức Tiến (DCU, Ireland) GIỚI THIỆU Ở Epsilon 12, chúng tôi đã giới thiệu với bạn đọc phần đầu của bài viết về toán học và phát hiện ảnh giả mạo thông qua một phóng sự ảo. Trong phần tiếp theo này, chúng tôi sẽ giới thiệu với bạn đọc ba kỹ thuật dựa trên toán học để phát hiện ảnh chỉnh sửa. Vân tay của ảnh Kỹ thuật đầu tiên mà chúng tôi giới thiệu với bạn đọc ở đây, gọi là kỹ thuật lấy vân tay của ảnh. Như chúng ta vẫn biết đối với con người thì xác suất để hai người có dấu vân tay giống hệt nhau là cực thấp, gần như không xảy ra. Và đối với máy ảnh cũng vậy, máy ảnh cũng có ... vân tay! Hình 1 mô tả lại một quá trình tạo ra một bức ảnh số từ máy ảnh hay điện thoại và tất cả các bước trong quá trình này như chúng tôi đã nói ở bài trước, đều để lại những dấu vết nhất định trên ảnh. Trong số đó, cảm biến của ảnh để lại dấu vết rõ rệt và dễ khai thác nhất. Toàn bộ quá trình làm ra cảm biến, dù là bởi nhà sản xuất tốt nhất, đều để lại những "tì vết" nhất định ở sản phẩm, và những lỗi cực nhỏ này tạo ra nhiễu khi máy cảm ứng và ghi nhận ánh sáng. Chính những mẫu nhiễu này, tạo nên "vân tay" của một máy ảnh! CẢM BIẾN Thế giới thật Ống kính Các bộ lọc quang học CFA Pattern CCD/CMOS Nén ảnh JPEG Ảnh gốc Nội suy CFA Xử lý trên máy ảnh Cân bằng trắng, Hiệu chỉnh nét, v.v. Máy ảnh số Hình 1: Quá trình tạo ra một bức ảnh bởi một máy ảnh kỹ thuật số. 26 Tạp chí Epsilon, Số 13, 02/2017 Nhiễu cảm biến đặc sắc ở chỗ, nó khác nhau không chỉ từ hãng này với hãng khác (ví dụ Canon với Nikon) hay dòng máy này với dòng máy khác (ví dụ iPhone 6 với iPhone 7), mà còn khác nhau từ máy ảnh này với máy ảnh khác (ví dụ hai máy Nikon D700 sẽ có nhiễu khác nhau). Chính điều này đã làm cho nhiễu được xem như là vân tay của một máy ảnh. Và như vậy, khi xác định được mẫu nhiễu của một máy ảnh, đem ra so khớp với mẫu nhiễu từ một bức ảnh, ta có thể xác định được bức ảnh này có phải được chụp từ máy ảnh đang xem xét hay không mà không cần bất cứ một thông tin nào khác từ Exif (để biết Exif là gì, có thể xem lại ở bài trước). Điều này rất quan trọng, để có thể giúp nhiếp ảnh gia giữ được bản quyền của mình, và cũng giúp cho điều tra viên xác định nguồn gốc của máy ảnh. Để xác định được mẫu nhiễu của máy ảnh, trước tiên ta cùng xem xét lại quá trình tạo ảnh ở Hình 1. Quá trình này được xấp xỉ (và đơn giản hoá) lại một cách toán học như sau: I(x, y) = I0(x, y) + I0(x, y)K(x, y) + N(x, y) (1) Trong đó I là ảnh gốc mà chúng ta nhận được, I0là ảnh lý tưởng mà nếu như không có nhiễu, chúng ta giả định sẽ nhận được ảnh đúng như vậy, K là nhiễu của cảm biến, N là nhiễu do các yếu tố khác, và (x, y) là vị trí của điểm ảnh. Trong (1), chúng ta có N khác nhau từ ảnh này sang ảnh khác, còn K giống nhau (chỉ khác nhau giữa các máy ảnh) và đó chính là giá trị mà chúng ta cần tìm. I0K được gọi là PRNU, viết tắt của photo-response non-uniformity noise. Câu hỏi đặt ra là chúng ta chỉ có thông tin duy nhất là các ảnh I có được từ máy ảnh, làm sao để tìm ra K? Để làm được việc này, Jessica Fridrich, trong [1], đã đề xuất một phương pháp rất đơn giản nhưng hiệu quả với hai bước như sau: Bước 1. Khử nhiễu cho ảnh, tức là với một ảnh Ik, tìm cách tính ˆIk với mục đích là ˆIk gần I0k nhất. Khử nhiễu có thể áp dụng lọc tần số, hoặc các biến đổi khác, trong đó biến đổi Wiener là phương pháp được tác giả đề xuất. Sau đó tính sai biệt giữa I và ˆIk. Wk(x, y) = Ik(x, y) − ˆIk(x, y) ≈ Ik(x, y)K(x, y) + Nk(x, y)(2) Bước 2. Xấp xỉ K từ các Wk đơn giản hơn từ IK do trong (2) không còn chứa nội dung của Ik nữa. Từ (2), ta có thể viết lại: Wk(x, y)) IK(x, y)) = K(x, y) + Nk(x, y) Ik(x, y)(3) Và từ n ảnh có được từ cùng máy ảnh ta có thể xấp xỉ K bởi công thức sau: Pn k=1 Wk(x, y)Ik(x, y) Pn K(x, y) ≈ k=1 Ik(x, y)2(4) 27 Tạp chí Epsilon, Số 13, 02/2017 Sau khi tính được K từ một máy ảnh, từ một ảnh It bất kỳ, ta có thể xác định liệu It có phải được chụp bởi máy ảnh có nhiễu K hay không nếu độ tương quan của ảnh này và K đủ lớn. Độ tương quan ρt giữa một ảnh It và K được tính như sau: ρt = IK ⊗ Wt (5) với ⊗ là độ tương quan giữa 2 ma trận 2 chiều và được tính bởi công thức: A ⊗ B = n(Amn − A¯)(Bmn − B¯) qP P m P P m n(Amn − A¯)2 PmPn(Bmn − B¯)2 (6) với A¯ và B¯ là giá trị trung bình của A và B tương ứng. Và như vậy, chỉ bằng toán học, ta có thể xác định liệu một bức ảnh bất kỳ có phải chụp từ một máy ảnh xác định hay không mà không cần thông tin Exif! Kỹ thuật này tuy rất đơn giản, nhưng lại hiệu quả bất ngờ, có thể áp dụng được với cả ảnh nén. Bằng kỹ thuật này, vào năm 2009, toà án Scotland đã chứng minh được tội trạng của một kẻ quấy rối tình dục trẻ em. Một trong những bài tập rất quen thuộc của người viết bài này là chúng tôi yêu cầu các sinh viên sau giờ giảng hãy chụp mỗi người khoảng 10 tấm ảnh khác nhau bởi máy ảnh hoặc điện thoại của mình. Sau đó, các ảnh này được tính PRNU và so sánh độ tương quan của các ảnh giữa các máy khác nhau với nhiễu của chúng. Kết quả luôn đạt được là ảnh bởi máy nào thì luôn có độ tương quan với nhiễu cao hơn các máy khác, kể cả những điện thoại cùng hãng, cùng dòng. Phương pháp này cũng được áp dụng để phát hiện ảnh cắt ghép từ 2 nguồn ảnh khác nhau (xem ví dụ ở Hình 2). Hình 2: Ví dụ về sử dụng nhiễu của máy ảnh để xác định ảnh ghép. Ảnh bên trái là ảnh gốc, bị sửa chữa xoá đi người phụ nữ để được ảnh ở giữa. Sau khi phân tích bức ảnh có nhiễu khác nhau, vùng ảnh bị chỉnh sửa đã bị phát hiện và thể hiện ở ảnh bên phải. Nguồn ảnh: [1] Với những độc giả muốn có ý định thử nghiệm, chúng tôi cũng cung cấp đoạn mã đơn giản sau đây viết bằng Matlab để tính PRNU cho một máy ảnh. function[PRNU] = calculatePRNU(path) dim = 512; // chỉ lấy nhiễu ở 512x512 đầu ảnh. imageList = dir([path filesep ’*.jpg’]); 28 Tạp chí Epsilon, Số 13, 02/2017 noOfImages = size(imageList, 1); I = zeros(dim, dim, noOfImages); W = zeros(dim, dim, noOfImages); for i = 1:noOfImages tempImage = imread([path filesep imageList(i).name]); I(:, :, i) = tempImage(1:dim, 1:dim, 1); % kênh đỏ denoisedImage = wiener2(I(:, :, i), [5 5]); W(:, :, i) = I(:, :, i) - denoisedImage; end PRNU = sum(W .* I, 3) ./ sum(I .* I, 3); end Sau khi tính xong PRNU, bạn đọc có thể tính độ tương quan của một ảnh bất kỳ với PRNU vừa tính được như sau: W = testImage - wiener2(testImage); correlation = corr2(testImage .* PRNU, W); Histogram của ảnh nén nhiều lần Như chúng tôi đã nhiều lần đề cập, ảnh nén luôn luôn để lại những dấu vết quan trọng trong việc xác định mức độ chỉnh sửa của một bức ảnh. Trong phần này, chúng ta hãy cùng xem xét một hiện tượng rất thú vị của một bức ảnh được nén 2 lần. Trước khi bắt đầu, chúng tôi nhắc lại cơ bản nguyên lý của việc nén ảnh Jpeg: 1. Đầu tiên ảnh từ không gian màu RGB được đổi sang YCbCr. 2. Tiếp theo từng kênh ảnh sẽ được nén riêng lẻ (mức độ lấy mẫu theo kênh Y có khác so với 2 kênh còn lại, nhưng không quan trọng đối với nội dung sắp đề cập). 3. Mỗi kênh màu tiếp theo được chia thành từng khối 8×8, và giá trị của các điểm ảnh được đổi sang phạm vi [-128, 127]. 4. Các điểm ảnh được chuyển sang không gian tần số bởi biến đổi cô-sin rời rạc (DCT). Fc(wk, wl) = X7 m=0 X7 n=0 fc(wk, wl)cos(wkm)cos(wln) với fc là giá trị điểm ảnh ở không gian thường. 29 Tạp chí Epsilon, Số 13, 02/2017 5. Tiếp theo, các tần số sẽ được lượng hoá để giảm thông tin. Đây là mấu chốt của việc nén ảnh. Mỗi tần số sẽ được lượng hoá bởi một lượng q được chọn trước: Fˆc(wk, wl) = Fc(wk, wl) q(wk, wl) (7) Bảng giá trị q được chọn trước với tiêu chí các tần số càng quan trọng thì q càng nhỏ (bằng 1 đối với tần số ở (0, 0)) và ngược lại. Thông thường, để tăng hiệu quả tính toán thì các giá trị của Fc sẽ được xếp dạng zig-zag, nhưng chúng tôi tạm lược bỏ ở đây. Công thức (7) đôi khi được áp dụng bởi hàm làm tròn (round) thay vì hàm phần nguyên (floor). 6. Fˆc sau đó được nén bởi các thuật toán nén không mất mát, phổ biến nhất là dùng Huffman. Để giải nén ảnh Jpeg, quá trình nén được thực hiện ngược lại, với các hàm ngược (ví dụ như biến đổi cô-sin rời rạc ngược). Như vậy, dấu vết của việc nén ảnh Jpeg có thể tìm thấy ở đâu? Chính là ở bước lượng hoá theo công thức (7). Hãy cùng xét một giá trị u, được lượng hoá bởi giá trị a, ta sẽ có kết quả là: qa(u) = ju a k Để lấy lại giá trị gốc u từ qa(u), ta áp dụng biến đổi nghịch đảo: q−1 a(u) = au. Tuy nhiên, biến đổi này không phải là hàm nghịch đảo của qa(u) vì bản chất của hàm phần nguyên hay làm tròn là bất khả nghịch! Hãy xét tiếp: nếu như u được lượng hoá lần 1 bởi 1 lượng bằng b, sau đó nghịch đảo và lượng hoá lần 2 bởi một lượng bằng a thì ta có: qab(u) = ju b kb a Điều gì sẽ xảy ra ở đây? Histogram của các giá trị sau lượng hoá sẽ để lại dấu vết của lần nén trước. Hay nói cách khác, khi ảnh được nén 2 lần, khi xem xét các giá trị sau lượng hoá ở lần thứ 2, thì các giá trị lượng hoá ở lần thứ 1 sẽ xuất hiện trong histogram. Hãy xem ví dụ ở Hình 3, bắt đầu từ một dãy ngẫu nhiên U các số trong phạm vi từ 0 đến 128, ở hình (a) là historam của hãy này sau biến đổi q2(U) và hình (b) là kết quả histogram sau biến đổi q3(U) (lượng hoá với 2 và 3). Ta thấy dáng dấp của histogram giữa 2 hình rất giống nhau, và gần với phân phối chuẩn do hàm sinh ngẫu nhiên dựa trên phân phối Gauss. Ở hình (c) và (d) là kết quả của việc lượng hoá 2 lần: ở (c), ta thấy histogram sau biến đổi q23(U) thì dấu vết của lần lượng hoá 1 (q3(U)) thể hiện rất rõ ở việc mỗi 3 cột (bin) thì lại có 1 cột trống; đối với (d), ta thấy dấu vết ở lần lượng hoá đầu (q2(U)) thông qua việc cứ mỗi 2 cột thì có 1 cột giá trị thấp hơn, hay nói cách khác, ta thấy dáng dấp của 2 phân bố trong một phân bố cuối cùng. Vì sao lại có hiện tượng này? Chúng ta hãy cùng xem xét chi tiết hơn hiện tượng này: • Đối với lượng hoá 1 lần, chúng ta có: f(x) → fa(x) = qa(f(x)). Với phép biến đổi này, toàn bộ các giá trị trong đoạn [av, av + (a − 1)] → v. Và do vậy, histogram kết quả sẽ là: Pa−1 k=0 H(av + k) = Ha(v). Nghĩa là có đúng a cột từ histogram gốc đóng góp vào mỗi cột của histogram sau biến đổi. 30 Tạp chí Epsilon, Số 13, 02/2017 Hình 3: Lượng hoá 2 lần, dấu vết của lần lượng hoá thứ 1 sẽ xuất hiện ở histogram cuối cùng. • Với lượng hoá 2 lần, ta có: f(x) → fab(x) = qab(f(x)). Với ub ba = v, histogram sẽ là: uXmax u=umin H(u) = Hab(v) với umin = abv b và umax = ab(v + 1) b − 1 Số lượng cột của histogram gốc đóng góp vào cột v của histogram kết quả (sau 2 lần lượng hoá) do vậy là: n(v) = umax − umin + 1 = b la bv m − la b(v + 1) m n(v) = n(v + b) Do vậy, tính chu kỳ sẽ xuất hiện ở histogram kết quả! • Cụ thể trong ví dụ ở Hình (3), ta có với b = 3, a = 2 thì n(3k+2) = 0 và với b = 2, a = 3 thì n(2k + 1) = 2 và n(2k) = 4. Vấn đề cuối cùng là với một histogram kết quả, làm thế nào để tính chu kỳ của histogram, nếu có? Câu trả lời là ta có thể áp dụng biến đổi Fourier! Một lần nữa, để phục vụ cho bạn đọc muốn thử nghiệm, chúng tôi cung cấp đoạn mã sau sẽ minh hoạ toàn bộ quá trình thí nghiệm đã nêu trong phần này. 31 Tạp chí Epsilon, Số 13, 02/2017 q1 = 3; q2 = 2; data = randn(1, 20000); data = data - min(data); data = round(255 * data/max(data)); histogram = hist(data, max(data)); subplot(411); bar(histogram); xlim([min(data) max(data)]); title(’Dữ hiệu gốc’); c1 = floor(data/q1); histogram = hist(c1, max(c1)); subplot(412); bar(histogram); xlim([min(c1) max(c1)]); title([’Lượng hoá bởi ’ num2str(q1)]); c2 = floor(c1 * q1 / q2); histogram = hist(c2, max(c2)); subplot(413); bar(histogram); xlim([min(c2) max(c2)]); title([’Lượng hoá lần 1 bởi ’ num2str(q1) ... ’, lần 2 bởi ’ num2str(q2)]); subplot(414); f = abs(fftshift(fft(histogram))); plot(f); xlabel(’Quantization’); Bóng ma Jpeg Trong phần cuối của bài này, chúng tôi giới thiệu một kỹ thuật rất thú vị mà Hany Farid trong [2] gọi là hiện tượng Bóng ma Jpeg. Xét một dãy giá trị cb có được sau khi lượng hoá bởi b, và cab có được sau khi lượng hoá bởi b rồi lượng hoá lần 2 bởi a thì khác biệt giữa cb và cab (sau khi biến đổi nghịch đảo) khi a thay đổi sẽ như thế nào? Hay cụ thể hơn, d(a, ab) sẽ biến đổi như thế nào? 32 Tạp chí Epsilon, Số 13, 02/2017 14 12 10 4) 8 6 4 2 0 0 5 10 15 20 25 30 qb = 17, qa Hình 4: Lượng hoá 2 lần, d(a, ab) cực tiểu khi a = 1 và a = b. d(a, ab) = |cbb − caba| = jubkb − jubkba a Ta thấy rằng, khác biệt này sẽ cực tiểu khi a = 1, nghĩa là lần 2 không nén/lượng hoá gì cả, và khi a = b, nghĩa là lần 2 lượng hoá với cùng giá trị lần 1. Ta cũng thấy giá trị khác biệt d sẽ tăng dần khi a tăng dần (xem minh hoạ ở Hình 4). Và như vậy, với một ảnh nén một lần mà ta không biết bất kỳ tham số gì của bảng lượng hoá, thì bằng phương pháp này, ta có thể tìm ra giá trị lượng hoá bằng cách khảo sát các giá trị có thể có và chọn giá trị mà khoảng cách là cực tiểu! Một lần nữa, chúng tôi cung cấp mã nguồn matlab để bạn đọc có thể thử nghiệm hiện tượng thú vị này: c0 = randn(1, 500); c0 = c0 - min(c0); c0 = round(10000 * c0/max(c0)); N = 30; q1 = 17; c1 = floor(c0/q1); d = zeros(1, N); for q2 = 1:N c2 = floor(c1 * q1 / q2); 33 diff = c1 * q1 - c2 * q2; d(q2) = sum(diff .* diff); end plot(d/10000, ’x-’, ’marker’, ’o’); Tạp chí Epsilon, Số 13, 02/2017 xlabel([’q_b = ’ num2str(q1) ’, q_a tăng từ 1 đến ’ ... num2str(N)]); ylabel(’Khác biệt (x10^4)’); axis square; Chúng ta tiếp tục đi đến một hiện tượng thú vị hơn. Giả sử chúng ta có cab rồi, và chúng ta tiếp tục lượng hoá lần thứ 3 bởi 1 lượng x thì khoảng cách d(ab, xab) sẽ như thế nào? Không khó đoán ra, chúng ta sẽ có d(ab, xab) sẽ đạt cực tiểu khi x = 1 hoặc x = a và sẽ tăng dần khi x tăng dần. Tuy nhiên, vâng, tuy nhiên, khi khảo sát ta sẽ thấy rằng, d(ab, xab) sẽ đạt cực trị địa phương khi x = b, và hiện tượng này gọi là bóng ma Jpeg, vì vùng ảnh này sẽ "lờ mờ" xuất hiện trong cách tính khoảng cách d (xem minh hoạ ở Hình 5). 8 7 6 ) 4 5 4 3 2 1 0 0 5 10 15 20 25 30 Hình 5: Lượng hoá 3 lần, d(ab, xab) cực tiểu khi x = 1 và x = a và đạt cực trị địa phương khi x = b. Cụ thể ta thấy d bằng 0 khi x = 1 và x = a = 17 và d đạt cực tiểu địa phương khi x = b = 23. Với hiện tượng này, chỉ bằng việc nén ảnh với nhiều mức độ khác nhau và tính toán khác biệt, chúng ta có thể không chỉ tìm ra giá trị dùng để nén ảnh mà còn chỉ rõ ảnh được nén bao nhiêu lần cũng như phát hiện ra ảnh ghép! Chúng tôi kết thúc bài viết ở đây với 2 ví dụ minh hoạ (lời giải thích được đặt ở chú thích). Hi vọng qua bài viết này, bạn đọc tĩnh táo hơn khi xem xét một bức ảnh số cũng như có thể tự mình thử nghiệm cũng như tạo ra vài công cụ để có thể phát hiện ảnh chỉnh sửa. 34 Tạp chí Epsilon, Số 13, 02/2017 Hình 6: Ảnh gốc chưa nén (góc trên trái), được trích ra vùng trung tâm, nén với mức nén 65, sau đó toàn bộ ảnh được nén với mức nén 85. Qua khảo sát các mức nén khác nhau, ta thấy ảnh đạt cực tiểu (đen toàn bộ) khi nén ở mức 85) và xuất hiện bóng ma ở mức nén 65. Nguồn ảnh: [2]. Hình 7: Một bức ảnh ghép (trên trái), qua phân tích sự khác biệt của chính ảnh này với các mức nén khác nhau (50, 55, 60, 65, 70, 75, 80, 85, và 90, theo thứ tự từ trái sang phải, từ trên xuống dưới) cho thấy vùng ghép (bóng ma - máy bay chiến đấu) được nén 2 lần với lần 1 nén ở mức 60 và sau đó toàn bộ ảnh kết quả được nén ở mức 90. 35 Tạp chí Epsilon, Số 13, 02/2017 Tài liệu [1] Fridrich, Jessica Digital Image Forensic Using Sensor Noise, IEEE Signal Processing Mag azine, vol. 26, no. 2, pp. 26-37, 2009. [2] Hany, Farid, Exposing Digital Forgeries from JPEG Ghosts, IEEE Transactions on Infor mation Forensics and Security, vol. 1, no. 4, pp. 154-160, 2009. 36 Tạp chí Epsilon, Số 13, 02/2017 KIỂM CHỨNG LÀ MÔ HÌNH Trần Thanh Hải (Vienna, Áo) GIỚI THIỆU Kiểm chứng là mô hình (model checking) là một trong những phương pháp phổ biến nhất để xác định tính đúng đắn của hệ thống. Ý tưởng của phương pháp này rất dễ hiểu và hiện thực hóa: hệ thống được biểu diễn bằng máy chuyển trạng thái, các trạng thái có thể tồn tại được sinh ra và kiểm tra. Sự bùng nổ tổ hợp các trạng thái là khuyết điểm lớn nhất của phương pháp này. Trong bài báo này, chúng tôi trình bày hướng tiếp cận trừu tượng hóa (abstraction) để vượt qua trở ngại này. 1. Chứng minh tính đúng đắn của hệ thống Lỗi là một phần không thể tránh khỏi trong quá trình phát triển các hệ thống máy tính. Tổ chức NIST (viết tắt của US National Institute of Standards and Technology) ước tính các lỗi lập trình và thuật toán gây ra thiệt hại 60 tỉ đô là mỗi năm cho nên kinh tế Mỹ [7]. Ngoài ra, các kỹ sư phần mềm có thể dành tới một nửa quãng thời gian làm việc để sửa lỗi. Thực ra, ngay từ thưở ban đầu của máy tính, cộng đồng nghiên cứu đã phát triển nhiều phương pháp để đánh tính đúng đắn của chương trình. Hai phương pháp phổ biến để đảm bảo rằng chương trình không có lỗi là viết một chứng minh thông thường dựa trên các định lý và viết một chứng minh bằng cách liệt kê. Dưới đây, chúng ta sẽ cùng nhìn lại ưu khuyết điểm của hai phương pháp này. Viết một chứng minh toán học là cách thức tin cậy nhất để đảm bảo tính đúng đắn của một hệ thống (bao gồm thuật toán, phần cứng và phần mềm). Tuy nhiên, viết một chứng minh hoàn chỉnh là một việc không thể dễ dàng vì nó đòi hỏi rất nhiều công sức và kiến thức. Khó khăn đầu tiên là làm cách nào để biểu diễn hệ thống một cách đơn giản. Nếu phải xem xét toàn bộ các yếu tố như sự giới hạn về tài nguyên, sự tương tác giữa các hệ thống với con người, các tính chất mà hệ thống nên có . . . thì hiện tại chúng ta vẫn chưa có một cách biểu diễn tiện lợi và chính xác. Do đó, ở đây chúng ta chỉ bàn về các cách tiếp cận dựa trên ngôn ngữ tự nhiên, mã giả và luận lý. Mã giả (pseudocode) và ngôn ngữ tự nhiên hiện được sử dụng rộng rãi để mô tả và chứng minh tính đúng đắn (một lớp) hành vi của hệ thống. Tuy nhiên, kiểm tra các lập luận được trình bày bằng mã giả và ngôn ngữ tự nhiên không hề dễ dàng. Ngay cả ở những công bố khoa học có ảnh hưởng lớn trong lĩnh vực khoa học máy tính, vẫn có những sai sót trong chứng minh chỉ được phát hiện sau nhiều năm. Các yếu tố như bất đồng bộ (asynchrony), tổ hợp các kịch bản hoạt 37 Tạp chí Epsilon, Số 13, 02/2017 động. . . gây ra nhiều khó khăn trong việc kiểm tra các lập luận chứng minh, ngay cả đối với các chuyên gia [5]. Để việc kiểm tra chứng minh trở nên dễ dàng hơn, các hệ thống chứng minh với sự hỗ trợ của máy tính (hoàn toàn tự động hoặc cần tương tác với người) đã được phát triển. Các sản phẩm tiêu biểu như Coq, Isabelle, SMT solvers (CVC4, Z3, . . .) đã được áp dụng thành công trong nhiều dự án của giới khoa học lẫn giới công nghiệp. Các công cụ này cho phép người dùng biểu diễn hệ thống dưới dạng các công thực luận lý (logical formulas) và hỗ trợ các phép suy diễn (inference rules) để kiểm tra tính đúng đắn của các bước chứng minh (hay định lý). Tuy nhiên, vì mới chỉ được phát triển khoảng vài chục năm gần đây nên các công cụ chứng minh chỉ hỗ trợ một số tiên đề trong vài lĩnh vực hẹp của toán học. Một khó khăn khác là không tồn tại một thuật toán (undecidable problem) để tự động tìm ra chứng minh cho một công thức toán học bất kỳ. Do vậy, viết một chứng minh hoàn chỉnh với sự hỗ trợ của máy tính vẫn đòi hỏi rất nhiều công sức, trí tuệ và đặc biệt là thời gian [8]. Trong nhiều, viết một chứng minh hoàn chỉnh là điều gần như không thể, ví dụ như cho các thuật toán phân tán (distributed algorithms). Các kỹ sư tại Amazon đã thử sử dụng một công cụ hỗ trợ chứng minh là TLAPS trong các dự án của họ. Tuy nhiên, sau cùng họ đành phải bỏ cuộc và nghi ngờ tính khả thi của việc viết một chứng minh đầy đủ trong các dự án tiếp theo của họ [6]. Do những khó khăn trên, việc tồn tại một hướng tiếp cận đơn giản trở nên rất quan trọng. Qua quan sát, các nhà khoa học máy tính nhận ra nếu khi biểu diễn hệ thống bằng một máy trạng thái thì số trạng thái có thể tồn tại cũng không phải quá nhiều, từ vài ngàn trở lên. Kiểm tra hết toàn bộ những trường hợp là không khả thi với con người; tuy nhiên với sự phát triển mạnh mẽ của máy tính thì ý tưởng này dần trở thành hiện thực. Đầu những năm 1980, Edmund M. Clarke, E. Allen Emerson và Joseph Sifakis đã lần đầu thành công trong việc hoàn thiện hệ thống lý thuyết và phát triển các công cụ dưa trên ý tưởng liệt kê [4]1. Đối với người sử dụng, ngoài việc mô hình hệ thống và các tính chất mong đợi thành những công thức luận lý (như khi viết chứng minh với sự hỗ trợ của máy tính) thì gần như tất cả những gì họ cần làm là nhấp vài nút đơn giản để chương trình và đợi kết quả máy tính trả về. Hướng tiếp cận dựa trên liệt được đặt tên là kiểm chứng là mô hình (model checking). Ý nghĩa của tên gọi này là kiểm chứng xem một hệ thống có phải là một mô hình (model - thuật ngữ trong ngành luận lý) của một công thức luận lý (dùng để biểu diễn các tính chất của hệ thống). Dĩ nhiên, khuyết điểm lớn nhất của phương pháp này là sự bùng nổ không gian trạng thái. Để vượt qua trở ngại này, nhiều hướng giải quyết đã được đề xuất: trừu tượng hóa (abstraction), biểu diễn với biểu tượng (symbolic representation), . . .. Nhờ các cải tiến trên, kiểm chứng là mô hình đã được sử dụng rộng rãi để chứng minh tính đúng đắn của các hệ thống phần cứng lẫn phần mềm. Trong những phần tiếp theo, chúng ta sẽ lần lượt tìm hiểu kỹ hơn về kiểm chứng là mô hình và trừu tượng hóa. 1Vào năm 2007, cả 3 nhà khoa học Edmund M. Clarke, E. Allen Emerson và Joseph Sifakis đã đều được trao tặng giải thưởng Alan Turing cho những đóng góp của họ trong việc phát triển phương pháp kiểm chứng là hệ thống. 38 Tạp chí Epsilon, Số 13, 02/2017 2. Kiểm chứng là mô hình Từ những năm 1980, các thuật toán kiểm chứng là mô hình đã lần lượt được giới thiệu. Các thuật toán này thường dựa trên cách biểu diễn hệ thống bằng những công thức trong luận lý với thì. Để áp dụng các thuật toán này, chúng ta cần trải qua 3 bước [4]: • Mô hình hóa: Người dùng biểu diễn hệ thống theo chuẩn đầu vào của thuật toán. Hệ thống có thể biểu diễn bằng máy automata hoặc một công thức luận lý với thì. Đôi khi, chúng ta cần phải loại bỏ các thông tin không cần thiết trong quá trình mô hình hóa. • Đặc tả: Người dùng mô tả các tính chất về hành vi của hệ thống. Thông thường, các tính chất được biểu diễn bằng một loại ngôn ngữ với thì như CTL, LTL hay TLA+. import java.util.Random; public class Rand { public static void main (String[] args) { Random random = new Random(42); // (1) int a = random.nextInt(2); // (2) System.out.println("a=" + a); //... lots of code here int b = random.nextInt(3); // (3) System.out.println(" b=" + b); int c = a/(b+a -2); // (4) System.out.println(" c=" + c); } } Hình 1: Chương trình Java minh họa [2] • Kiểm chứng: Các phần mềm kiểm chứng sẽ tự động sản sinh và kiểm tra các trạng thái có thể tồn tại. Tuy nhiên, đôi khi người dùng cần phải tham gia vào để lựa chọn loại trừu tượng hóa, phân tích kết quả trả về. . . Chúng ta hãy cùng xem xét đoạn mã nguồn như trong Hình 1. Công cụ kiểm chứng Java PathFinder sẽ sản sinh ra các trường hợp thực thi như trong Hình 2. Dựa vào đó, chúng ta dễ dàng kiểm tra rằng có một trường hợp c < 0 và có lỗi xảy ra do thực hiện phép chia bằng 0 2. Dễ thấy rằng, nếu hai biến a, b chỉ là hai số ngẫu nhiên kiểu Int thì chúng ta sẽ có 264 trường hợp cần xem xét. 2Ở đây, chúng ta chỉ tập trung minh họa ý tưởng của kiểm chứng với mô hình nên không bàn tới việc mô hình hóa hệ thống và đặc tả tính chất như thế nào với Java PathFinder. 39 Tạp chí Epsilon, Số 13, 02/2017 Hình 2: Các trạng thái được sản sinh bởi chương trình Java PathFinder [2] Một ưu điểm khác của phương pháp này là cho phép chúng ta giải thích nguyên nhân lỗi một cách trực quan và sinh động. Ví dụ như khi giải thích lỗi chia cho 0 của chương trình Java trên, công cụ kiểm chứng hoàn toàn có thể đưa ra một trường hợp cụ thể là a = b = 1. Mặc dù ý tưởng của phương pháp kiểm chứng là mô hình rất đơn giản và gặp khó khăn về số trạng thái cần kiểm tra, hướng tiếp cận này đã giải quyết thành công nhiều vấn đề trong các dự án của giới khoa hoa và giới công nghiệp. Các ví dụ tiêu biểu như [1] • Sự cố gián đoạn mạng viễn thông AT&T: lỗi biên dịch câu lệnh brean trong ngôn ngữ C. • Vỡ phi thuyền Ariane 5: lỗi ép kiểu float sang kiểu int. • Bộ vi điều khiển Pentium FDIV: lỗi liên quan tới phép chia số thực. 3. Trừu tượng hóa Trừu tượng hóa là một phương pháp phổ biến để vượt qua những khó khăn do sự bùng nổ tổ hợp các trạng thái gây nên [4]. Ý tưởng cơ bản của trừu tượng hóa là thay vì xem xét không gian trạng thái hiện có, chúng ta sẽ tìm và xem xét một không gian trạng thái nhỏ hơn. Ta sử dụng các ký hiệu S để chỉ không gian hiện tại và Sˆ để chỉ không gian nhỏ hơn. S và Sˆ còn thường được gọi là không gian cụ thể (concrete) và không gian trừu tượng (abstract). Ta ký hiệu s, sˆ lần lượt là một trạng thái trong S, Sˆ. Việc chuyển đổi giữa hai không gian S và Sˆ được xác định dựa trên hai hàm f : S → Sˆ và g : Sˆ → S. Do Sˆ là không gian nhỏ hơn nên nhiều hai trạng thái cụ thể s1, s2 hoàn toàn có thể được ánh xạ vào một trạng thái trừu tượng sˆ. Có nhiều cách khác nhau để xác định S, f, g ˆ nhưng tất cả đều phải đảm bảo yếu tố vững chắc (soundness): • Nếu tồn tại lỗi trên không gian S thì phải tồn tại một lỗi tương ứng trên không gian Sˆ. Điều ngược lại hay tính toàn bộ (completeness) không quá quan trọng. Thực ra, trong rât nhiều trường hợp, chúng ta hoàn toàn không thể tìm được S, f, g ˆ đảm bảo cả hai tính chất vững chắc và toàn bộ. Mỗi loại trừu tượng hóa thường chỉ phù hợp với một số hệ thống và tính chất nhất định. Hiện tại, nhiều phương pháp trừu tượng hóa đã được đề xuất. Dưới đây chúng ta sẽ xem xét phương pháp trừu tượng hóa với vị từ. 40 Tạp chí Epsilon, Số 13, 02/2017 3.1. Trừu tượng hóa với vị từ Trừu tượng hóa với vị từ (predicate) là một trong những hướng tiếp cận mạnh nhất hiện nay để vượt qua sự bùng nổ không gian trạng thái [3]. Các vị từ được dùng để trừu tượng hóa các biến dữ liệu của chương trình ban đầu và được xem như một biến bool của chương trình trừu tượng. Tập các vị từ sẽ thể hiện mối quan hệ giữa các biến dữ liệu trong chương trình ban đầu. Như vậy, ta có Sˆ = {p1, . . . , pk} với pilà các vị từ được chọn. Hai hàm f và g sẽ được xây dựng giữa trên mối quan hệ tồn tại như sau: • Nếu s là một trạng thái bắt đầu trong S thì f (s) phải là một trạng thái bắt đầu trong sˆ. • Nếu tồn tại một phép chuyển trạng thái từ s1 tới s2 trong S thì tồn tại một phép chuyển trạng thái từ f (s1) tới f (s2) trong Sˆ. Ví dự với chương trình Java trong Hình 1, chúng ta có thể sử dụng vị từ (p0 , a = b) để kiểm tra lỗi chia cho 0. Nếu p0 = TRUE, chúng ta biết rằng trường hợp chia cho 0 sẽ xảy ra. Để giới hạn các giá trị mà a, b, c có thể nhận, chúng ta có thể sử dụng các vị từ sau p1 , a ≥ 0 p2 , a < 2 p3 , b ≥ 0 p4 , b < 2 p5 , c ≥ −232 + 1 p6 , c < 232 Điều đáng quan tâm là khi chúng ta thay đổi giá trị mà a, b có thể nhận thành toàn bộ các số có kiểu Int, để kiểm chứng trường hợp có trường hợp c = 0 hay không, ta chỉ cần thay đổi các vị từ p1, p2, p3, p4 thành p01 , a ≥ −232 + 1 p02 , a < 232 p03 , c ≥ −232 + 1 p04 , b < 232 và như thế không gian trạng thái trừu tượng của chúng ta vẫn chỉ có 27trạng thái dù không gian trạng thái ban đầu đã tăng thành (232)3. Dễ thấy rằng, việc chọn lựa vị từ đóng yếu tố rất quan trọng vì chúng sẽ được dùng để chứng minh tính chất của hệ thống và chúng cũng quyết định số lượng trạng thái. Trước đây, người dùng sẽ phải tự cung cấp các vị từ phù hợp cho các chương trình kiểm chứng. Hiện nay, trong nhiều trường hợp, các chương trình đã có thể tự động tìm kiếm các vị từ phù hợp để chứng minh tính chất mong muốn [3]. 41 4. Tổng kết Tạp chí Epsilon, Số 13, 02/2017 Kiểm chứng là mô hình là một phương pháp tự động để chứng minh tính đúng đắn của chương trình. Liệt kê và kiểm tra tất cả các trạng thái có thể xảy ra là ý tưởng chính của phương pháp này. Tuy nhiên, khuyết điểm của nó la không phù hợp với các hệ thống có quá nhiều hoặc vô hạn trạng thái. Trừu tượng hóa là một phương pháp phổ biến để vượt qua khuyết điểm trên. Tuy nhiên, mỗi phương pháp trừu tượng hóa chỉ phù hợp với một lớp hệ thống và tính chất nhất định. Việc phát triển thêm nhiều hướng tiếp cận để giảm thiểu sự bùng nổ không gian trạng thái là một trong những hướng nghiên cứu quan trọng của lĩnh vực kiểm chứng là hệ thống. Tài liệu [1] Introduction to model checking. https://moves.rwth-aachen.de/teaching/ ss-15/introduction-to-model-checking. Accessed: 2017-01-30. [2] Java pathfinder. http://babelfish.arc.nasa.gov/trac/jpf. Accessed: 2017- 01-30. [3] Edmund Clarke, Orna Grumberg, Somesh Jha, Yuan Lu, and Helmut Veith. Counterexample-guided abstraction refinement. In International Conference on Computer Aided Verification, pages 154–169. Springer, 2000. [4] Edmund M Clarke, Orna Grumberg, and Doron Peled. Model checking. MIT press, 1999. [5] Leslie Lamport. Specifying systems: the TLA+ language and tools for hardware and soft ware engineers. Addison-Wesley Longman Publishing Co., Inc., 2002. [6] Chris Newcombe, Tim Rath, Fan Zhang, Bogdan Munteanu, Marc Brooker, and Michael Deardeuff. How amazon web services uses formal methods. Communications of the ACM, 58(4):66–73, 2015. [7] Michael Newman. Software errors cost us economy $59.5 billion annually. NIST Assesses Technical Needs of Industry to Improve Software-Testing, 2002. [8] Natarajan Shankar. Automated deduction for verification. ACM Computing Surveys (CSUR), 41(4):20, 2009. 42 Tạp chí Epsilon, Số 13, 02/2017 CÁC PHƯƠNG PHÁP SAI PHÂN HỮU HẠN CHO PHƯƠNG TRÌNH ĐẠO HÀM RIÊNG (TIẾP THEO) Henry Tran Wayne State University, Michigan, USA LỜI BAN BIÊN TẬP Bài viết của tác giả Henry Tran có nguyên bản là tiếng Anh, có ba phần chính gồm: • Lý thuyết và ứng dụng lập trình MATLAB trong phương trình Parabolic. • Lý thuyết và ứng dụng lập trình MATLAB trong phương trình Hyperbolic. • Lý thuyết và ứng dụng lập trình MATLAB trong phương trình Elliptic. Chúng tôi đã đăng phần đầu ở Epsilon số 11. Ở số báo này, chúng tôi sẽ đăng tiếp hai phần còn lại, về Hyperbolic và Elliptic. 1. Các dạng toán Hyperbolic 1.1. Phương trình đạo hàm riêng dạng Hyperbolic Một phương trình đạo hàm riêng bậc hai có dạng a∂2u ∂xy + c∂2u ∂x2+ 2b∂2u ∂x + e∂u ∂y2+ d∂u được gọi là bài toán hyperbolic nếu ma trận ∂y + f = 0 M = thỏa mãn điều kiện det (M) = ac − b2 < 0. a b b c , Phương trình sóng là một dạng cơ bản của PDEs trong bài toán hyperbolic của không gian một chiều với a = 1. 43 Tạp chí Epsilon, Số 13, 02/2017 1.2. Bài toán mô hình phương trình sóng Phương trình sóng được viết dưới dạng ∂t2u (x, t) = ∂2 ∂2 ∂x2u (x, t) Chúng ta có thể viết lại thành h2[u (x + h, t) − 2u (x, t) + u (x − h, t)] = 1k2[u (x, t + k) − 2u (x, t) + u (x, t − k)] 1 Ta cũng có công thức u (x, t + k) = ρu (x + h, t) + 2 (1 − ρ) u (x, t) + ρu (x − h, t) − u (x, t − k) (∗). Điều kiện ổn định ở đây là ρ =k2 h2 ≤ 1. Phương trình sóng và các điều kiện ban đầu là  ∂t2 u (x, t) = ∂2 ∂2  ∂x2 u (x, t) u (x, 0) = f (x) ut (x, 0) = 0 u (0, t) = u (1, t) = 0 trong đó 0 ≤ x ≤ 1 and 0 ≤ t. Nhắc lại rằng ut (x, t) = 1k[u (x, t + k) − u (x, t)] . Từ t = 0, ta có ut (x, 0) = 1k[u (x, k) − u (x, 0)] . Do đó, ta cũng có hệ phương trình tương tự   ∂2 ∂t2 u (x, t) = ∂2 ∂x2 u (x, t) u (x, 0) = f (x) 1 k[u (x, k) − u (x, 0)] = 0 u (0, t) = u (1, t) = 0 44 Tạp chí Epsilon, Số 13, 02/2017 với 0 ≤ x ≤ 1 and 0 ≤ t. Từ phương trình của điều kiện ban đầu với điều kiện đầu tiên của ut (x, 0) = 0 là 1 k[u (x, k) − u (x, 0)] = 0, chúng ta có thể kết luận điều kiện đầu tiên của u (x, k) = u (x, 0) = f (x). Thay t = 0 trong (∗), ta được u (x, k) = ρu (x + h, 0) + 2 (1 − ρ) u (x, 0) + ρu (x − h, 0) − u (x, −k). Sử dụng xấp xỉ sai số trung tâm, ta có 1 2k[u (x, k) − u (x, −k)] = 0. Do đó, ta có điều kiện thứ hai của hệ điều kiện biên của (x, k) là u (x, k) = 12ρ [f (x + h) + f (x − h)] + (1 − ρ) f (x). 1.3. Công thức tường minh 1.3.1. Phương pháp tường minh sử dụng công thức Từ phương trình ban đầu, bằng việc dùng biến h, k lần lượt ký hiệu cho số gia của các biến x, t, chúng ta có h2[u (x + h, t) − 2u (x, t) + u (x − h, t)] = 1k2[u (x, t + k) − 2u (x, t) + u (x, t − k)] . 1 Nó cũng có thể viết thành dạng u (x, t + k) = ρu (x + h, t) + 2 (1 − ρ) u (x, t) + ρu (x − h, t) − u (x, t − k). Ở đây, điều kiện ổn định là ρ =k2 h2 ≤ 1. Chúng ta có năm điểm được biểu diễn ở lược đồ sau 45 Tạp chí Epsilon, Số 13, 02/2017 1.3.2. Giải phương trình sóng và lập trình tính toán a) Ví dụ Chúng ta có hệ phương trình  ∂2 ∂t2 u (x, t) = ∂2 ∂x2 u (x, t) u (x, 0) = f (x) 1 k[u (x, k) − u (x, 0)] = 0 u (0, t) = u (1, t) = 0 Sử dụng phần mềm MATLAB để giải với f (x) = sin2πx, T = 1, L = 1, , nt = 200, nx = 32. Điều kiện ban đầu là u (0, t) = u (1, t) = 0 và 1 k[u (x, k) − u (x, 0)] = 0 hay u (x, k) = 12ρ [f (x + h) + f (x − h)] + (1 − ρ) f (x) b) Lập trình tính toán (xem thêm phần Phụ lục bên dưới) Nghiệm chính xác là uexact (x, t) = 12[sin2π (x + t) + sin2π (x − t)] tại T = 1. Chúng ta có các kết quả về nghiệm xấp xỉ bởi phương pháp sai phân hữu hạn và nghiệm chính xác với T = 1 trong các hình minh họa. Trong 2D: với T = 1, L = 1, nt = 200, nx = 8, 16, 32, 64. 46 Tạp chí Epsilon, Số 13, 02/2017 47 Tạp chí Epsilon, Số 13, 02/2017 So sánh giữa phương pháp sai phân hữu hạn và nghiệm chính xác Minh họa của nghiệm gần đúng bởi phương pháp tường minh với T = 1 48 Tạp chí Epsilon, Số 13, 02/2017 Minh họa của nghiệm chính xác với T = 1 Bằng cách tính các sai số giữa nghiệm gần đúng và nghiệm chính xác, ta có bảng sau 2. Các dạng toán Elliptic Phương trình đạo hàm riêng dạng Elliptic Một phương trình đạo hàm riêng bậc hai có dạng a∂2u ∂xy + c∂2u ∂x2+ 2b∂2u ∂x + e∂u ∂y2+ d∂u được gọi là bài toán hyperbolic nếu ma trận ∂y + f = 0. M = thỏa mãn điều kiện det (M) = ac − b2 > 0. a b b c 49 , Tạp chí Epsilon, Số 13, 02/2017 Phương trình Helmholtz là dạng đơn giản của PDEs trong bài toán elliptic của không gian một chiều với a = 1. 2.1. Bài toán mô hình phương trình Helmholtz Giả sử hàm số u = u(x, y) có hai biến là x và y, hàm này không xác định được cụ thể nhưng là duy nhất. Ta giả sử vùng R được cho trước là mặt phẳng hai chiều xy ∇2u + fu = g (x, y) là biết trước trên R(∗∗), với ∇2u (x, y) = ∂2u ∂x2 +∂2u ∂y2, f = f (x, y) vàg = g (x, y) là các hàm được định nghĩa trong R. Nếu f là hàm hằng thì (∗∗) được gọi là phương trình Helmholtz. Nếu thayf = g = 0 vào (∗∗), ta có phương trình Laplace: ∇2u (x, y) = ∂2u ∂x2+∂2u ∂y2= 0. Nếu thay f = 0, g 6= 0 vào (∗∗), ta có phương trình Poisson ∇2u (x, y) = ∂2u ∂x2+∂2u ∂y2= g (x, y). 2.2. Công thức tường minh Xét bài toán elliptic: ∇2u + fu = g nằm trong Ω = [0, 1] u = 0 trên ∂ Ω = [0, 1] Tương tự các phần trước, ta sẽ tìm nghiệm gần đúng của bài toán trên bằng phương pháp sai phân hữu hạn. Chúng ta bắt đầu bởi công thức đơn giản fxx =∂2f ∂x2≈1h2[f (x + h, y) − 2f (x, y) + f (x − h, y)] và fyy =∂2f ∂y2≈1h2[f (x, y + h) − 2f (x, y) + f (x, y − h)] Sử dụng (∗∗), ta có 5 điểm trong phương trình Laplace ∂x2+∂2u ∇2u =∂2u 50 ∂y2 Tạp chí Epsilon, Số 13, 02/2017 gần bằng 1 h2[u (x + h, y) + u (x − h, y) + u (x, y + h) + u (x, y − h) − 4u (x, y)] Phương trình này được minh họa trong hình bên dưới Trở lại bài toán ban đầu, ta định nghĩa xi = ih, yj = jh where i, j ≥ 0. Ta sẽ viết các hàm như sau uij = u (xi, yj ), fij = f (xi, yj ), gij = g (xi, yj ) và 5 điểm sẽ bao gồm (∇2u)ij ≈1h2[ui+1,j + ui−1,j + ui,j+1 + ui,j−1 − 4 + ui,j ] Các điểm này cần thể hiện bởi mô hình với 5 hệ số. Phương trình (∗∗) được viết dưới dạng −ui+1,j − ui−1,j − ui,j+1 − ui,j−1 +4 − h2fi,j uij = h2gi,j Dạng của phương trình được mô tả trong hình bên dưới Xét bài toán của elliptic trong trường hợp n = 3. Ta sẽ dùng đồ thị trong hệ trục tọa độ cho bài toán này như hình bên dưới 51 Ta có các điểm trên biên là Tạp chí Epsilon, Số 13, 02/2017 Các điểm này đều thuộc biên nên chúng phải bằng 0. Dù vậy, trong một số trường hợp khác, có những điểm thuộc biên khác 0. Bằng cách phân tích độc lập, chúng ta có 9 điểm trên lưới như bên dưới. Mô hình này bao gồm 9 điểm lưới ở trong. Để xem xét các điểm trên biên, ta có 9 phương trình của hệ như sau  − u21 − u01 − u12 − u10 + (4 − h2f11)u11 = −h2g11 − u31 − u11 − u22 − u20 + (4 − h2f21)u21 = −h2g21 − u41 − u21 − u32 − u30 + (4 − h2f31)u31 = −h2g31 − u22 − u02 − u13 − u11 + (4 − h2f12)u12 = −h2g12 − u32 − u12 − u23 − u21 + (4 − h2f22)u22 = −h2g22  − u42 − u22 − u33 − u31 + (4 − h2f32)u32 = −h2g32 − u23 − u03 − u14 − u12 + (4 − h2f13)u13 = −h2g13 − u33 − u13 − u24 − u22 + (4 − h2f23)u23 = −h2g23 − u43 − u23 − u34 − u32 + (4 − h2f33)u33 = −h2g33 52 Tạp chí Epsilon, Số 13, 02/2017 Tiếp theo, chúng ta sẽ xây dựng hệ phương trình bởi công thức Au = b, trong đó A là ma trận của hệ tuyến tuyến với kích thước 32 × 32. Ta có u = [u11, u21, u31, u12, u22, u32, u13, u23, u33] .   trong đó A =  x11 −1 0 −1 0 0 0 0 0 −1 x22 −1 0 −1 0 0 0 0 0 −1 x33 0 0 −1 0 0 0 −1 0 0 x44 −1 0 −1 0 0 0 −1 0 −1 x55 −1 0 −1 0 0 0 −1 0 −1 x66 0 0 −1 0 0 0 −1 0 0 x77 −1 0 0 0 0 0 −1 0 −1 x88 −1 0 0 0 0 0 −1 0 −1 x99 x11 = 4 − h2f11, x22 = 4 − h2f21, x33 = 4 − h2f31, x44 = 4 − h2f12, x55 = 4 − h2f22, x66 = 4 − h2f32, x77 = 4 − h2f13, x88 = 4 − h2f23, x99 = 4 − h2f33 b =  − h2g11 + u10 + u01  − h2g21 + u20 − h2g31 + u30 + u41 − h2g12 + u02 − h2g22 − h2g32 + u42 − h2g13 + u14 + u03 − h2g23 + u24 − h2g33 + u34 + u43   trong đó u10, u01,u20, u30,u41, u02,u42, u14,u03, u24, u34, u43 là các điểm trên biên nên chúng đều phải bằng 0. Nếu f (x, y) < 0 thì A là ma trận chéo hóa. Tổng quát, ta có hệ phương trình Mu = b, trong đó M là ma trận của hệ phương trình tuyến tính với kích thước n2 × n2. Ta có u = [u11, u21, . . . , un1, u12, u22, . . . , un2,, . . . , u1n, u2n, . . . , unn ] . 53 Ma trận tổng quát M là  Tạp chí Epsilon, Số 13, 02/2017  M = x11 −1 0 −1 0 0 . 0  −1 x22 −1 0 −1 0 −1 . −1 0 −1 0 −1 . −1 0 0 0 −1 xnn −1 0 0 0 −1 x(n+1)(n+1) −1 0 . 0 −1 . −1 0 0 −1 xn2n2 trong đó x11 = 4 − h2f11, x22 = 4 − h2f21, xnn = 4 − h2fn1, x(n+1)(n+1) = 4 − h2f12, xn2n2 = 4 − h2fnn và hai đường chéo chứa các số −1 nằm bên cạnh đường chéo chính. Nếu mod (i, n) 6= 0, i = 1, . . . , n2sẽ dẫn đến M (i, i + 1) = −1 và M (i + 1, i) = −1. Ngược lại, nếu mod (i, n) = 0 thì M (i, i + 1) = M (i + 1, i) = 0. Trong hai đường chéo còn lại, số thuộc dòng thứ i và cột thứ i + n thuộc vào phần trên đường chéo chính hoặc số thuộc dòng thứ i + n và cột thứ i nằm dưới đường chéo chính là −1. Cụ thể là M (i, i + n) = −1, i = 1, . . . , n2và M (i + n, i) = −1, i = n + 1, . . . , n2. Tổng quát, ta sẽ viết ma trận b như bên dưới b =   − h2g11 + u10 + u01  − h2g21 + u20 . . − h2gn1 + u(n+1) 1 + u(n−1) 1 + un 0 − h2g12 + u02 − h2g22 . . − h2gn2 + u(n+1)2 + u(n−1) 2 . . − h2g1n + u0n + u1(n+1) − h2g2n + u2(n+1) . . − h2gn n + u(n+1)n + un(n+1) + un(n−1) Nếu f (x, y) < 0 thì A là ma trận chéo hóa. 54 Tạp chí Epsilon, Số 13, 02/2017 2.3. Ví dụ và lập trình tính toán. 2.3.1. Ví dụ. ∇2u + fu = g nằm trong Ω = [0, 1] Xét bài toán elliptic u = q trên ∂ Ω = [0, 1] và q là uexact = q = sinπx + cosπy hoặc uexact = q = sinπ (x + y), trong đó f = 1, hoặc f = xy. 2.3.2. Lập trình tính toán (xem thêm phần Phụ lục) Chúng ta sẽ dùng các hàm sau đây trong chương trình MATLAB: case 1: u = sin(pi*x)*sin(pi*y); case 2: u = x*y*(x-1)*(y-1); case 3: u = x^2 + y^2; case 4: u = x^3 + y^3; case 5: u = sin(pi*x)*cos(pi*y); case 6: u = sin(pi*x) + cos(pi*y); case 7: u = sin(pi*(x+y)); case 8: u = sin(pi*(x^2+y^2)); case 9: u = x^2; case 10:u = x; Ta sẽ vẽ đồ thị của nghiệm gần đúng với f = 1 và uexact = q = sinπx+cosπy; g = ∇2uexact + fuexact Đồ thị của nghiệm gần đúng với phương pháp sai phân hữu hạn với n = 20 55 Tạp chí Epsilon, Số 13, 02/2017 Trong đồ thị, các biên đều bằng 0. Bằng cách phân tích thêm, ta có thể thấy rằng • Với x = 0 thì u(1, y(j)) = cos(πy(j)) • Với x = 1 thì u(N + 1, y(j)) = cos (πy (j)) • Với y = 0 thì u(x(i), 1) = sin(πx(i)) + 1 • Với y = 1 thì u(x(i), N + 1) = sin(πx(i)) − 1 Ta sẽ vẽ đồ thị của nghiệm chính xác với hàm cụ thể cần xét là uexact = sinπx+cosπy, nghiệm chính xác của nó được vẽ trong hình bên dưới Đồ thị của nghiệm chính xác với n = 20 Ta sẽ vẽ đồ thị của nghiệm gần đúng với f = 1 thì uexact = q = sinπ (x + y) ; g = ∇2u + fuexact. Dưới đây là đồ thị của nghiệm cần đúng tìm được bằng phương pháp sai phân hữu hạn với n = 20 56 Tạp chí Epsilon, Số 13, 02/2017 Các giải thích bổ sung thêm cho điều kiện ban đầu: • Với x = 0 thì u(1, y(j)) = sin πy(j) • Với x = 1 thì u(N + 1, y(j)) = sin π (1 + y (j)) • Với y = 0 thì u(x(i), 1) = sin πx (i) • Với y = 1 thì u(x(i), N + 1) = sin π (x (i) + 1) Tiếp theo, ta sẽ vẽ đồ thị của nghiệm chính xác với uexact = sinπ (x + y), n = 20 57 Tạp chí Epsilon, Số 13, 02/2017 Ta có bảng hội tụ của nghiệm trong các trường hợp sau Với f = 1; uexact = sinπ (x + y) 3. Kết luận 3.1. Các bài toán Hyperbolic Phương pháp sai phân hữu hạn cho PDEs của bài toán hyperbolic với dạng đơn giản nhất là phương trình sóng của một chiều. Giá trị của h và k thỏa mãn điều kiện ổn định là ρ =k2 h2 ≤ 1. Điều này có nghĩa là nx ≥ nT và ta cần chọn giá trị thích hợp cho nT và nx trong chương trình MATLAB. Nghiệm hội tụ khi ta cố định giá trị của nT nhưng thay đổi giá trị của nx. Chúng ta cũng thấy rằng nếu chọn nx ≥ nT thì đồ thị sẽ không còn đúng dạng nữa. 58 Tạp chí Epsilon, Số 13, 02/2017 Chúng ta đã tính được sai số giữa nghiệm chính xác và nghiệm gần đúng bởi các giá trị khác nhau của nx. Điều này chứng tỏ rằng bậc hội tụ là 1. Thông qua bảng hội tụ, ta đã vẽ được đồ thị để so sánh các giá trị của nghiệm chính xác và nghiệm gần đúng trên cùng một hệ trục tọa độ. Cuối cùng, ta cũng đã thể hiện được đồ thị của hàm số đã chọn trong không gian ba chiều. Lý thuyết về bài toán dạng hyperbolic có nhiều mô hình từ đơn giản đến phức tạp trong Toán học, chẳng hạn như phương trình đối lưu, Lax, Upwind, Lax-Wendroff, phương trình Navier Stokes. Thêm nữa, bài toán này trong những năm gần đây cũng được nghiên cứu và phát triển phục vụ cho khoa học và kỹ thuật. Phương trình sóng có nhiều ứng dụng trong vật lý như các sóng của chuỗi, sóng giật trong không khí, sóng cơ học lượng tử, các mô hình âm thanh của sóng địa chấn, sóng âm trong chất lỏng và gas, v.v. 3.2. Các bài toán Elliptic Phương pháp sai phân hữu hạn cho PDEs của bài toán elliptic phức tạp hơn hai dạng toán trước. Ở đây, chúng ta đã dùng phương trình Helmholtz để xét bài toán này. Phương trình đó bao gồm các phương trình Laplace và Poisson, phụ thuộc vào giá trị khác nhau của các hàm f và g. Chúng ta cần ký hiệu các điểm trên lưới ở trong và ở trên biên, sau đó xây dựng ma trận của hệ phương trình tuyến tính tổng quát rồi tìm các giá trị của b. Sự hội tụ của nghiệm xảy ra khi ta chọn giá trị đủ lớn nào đó của N. Với các giá trị khác nhau của N, ta có thể thấy rằng độ hội tụ của nghiệm xấp xỉ và kết luận được điểm tương quan giữa các mô hình tương tự nhau trong nghiệm gần đúng và nghiệm chính xác trên cùng một hệ trục tọa độ. Hơn nữa, từ các đồ thị của không gian ba chiều, ta cũng đã vẽ được các điểm trên biên và bên trong một cách rất rõ ràng. Mặt khác, ta cũng có thể thay đổi các hàm f và g trong MATLAB để vẽ các đồ thị khác. Các bài toán elliptic của PDEs có nhiều ứng dụng trong vật lý tĩnh điện, kỹ thuật cơ khí và vật lý lý thuyết. 4. Phụ lục 4.1. Các bài toán hyperbolic MATLAB program 3: Bài toán mô hình phương trình sóng function hyperfdm_sol(L,T,nT,nx) % Matlab Program : Hyperbolic problems: %Wave equation: u_xx=u_tt %where u(x,0)=sin(pi*x). Use the explicit method. %The exact solution: u_exact=(1/2)*(sin(2*pi*(x+t))+sin(2*pi*(x-t))) 59 Tạp chí Epsilon, Số 13, 02/2017 %L = 1.; % Length of the wire %T = 1; % Final time % Choose nT= 200. Number of time steps dt = T/nT; % Choose nx= 4,8,... Number of space steps dx = L/nx; rho = dt^2/(dx^2); % Stability parameter rho <= 1 when nx <= nT. % Initial temperature of the wire % initilalize u u = zeros(nx+1,nT+1); u3 = zeros(nx+1,nT+1); x = zeros(nx+1,1); time = zeros(nT+1,1); for i = 1:nx+1 x(i) = (i-1)*dx; u(i,1) = f0(x(i)); end %Temperature at the boundary (t=0) for k =1:nT+1 u(1,k) = 0.; u(nx+1,k) = 0.; time(k) = (k-1)*dt; end %Implementation of the exact solution for k=1:nT+1 for i = 1:nx+1 u3(i,k) = u_exact(x(i),time(k)); end end %Implementation of the explicit method for i = 2:nx %k=2, the first time step u(i,2) = (1/2)*rho*(f0(x(i+1))+f0(x(i-1)))+(1-rho)*f0(x(i)); end % The second time step for k = 3:nT+1 % Time Loop for i = 2:nx % Space Loop u(i,k) = rho*u(i+1,k-1)+2*(1-rho)*u(i,k-1)+ rho*u(i-1,k-1)-u(i,k-2); end end disp(error2); % Graphical representation of the temperature at different selected times figure hold on %The graphic of the exact solution in 2D plot(x,u3(:,1),’-r’,’MarkerFaceColor’,’r’) 60 Tạp chí Epsilon, Số 13, 02/2017 %The graphic of the explicit method in 2D plot(x,u(:,1),’*b’,’MarkerFaceColor’,’b’) xlabel(’x’) ylabel(’temperature’) legend({’Exact solutions’ ’Finite difference method’},’location’,’NE’); title(’The comparison of the finite difference method and the exact solutions for h = 1/64, at T=1’) hold off %The graphic of the explicit method in 3D figure mesh(x,time,u’) title(’The the finite difference method for h = 1/32,at T=1’) xlabel(’x’) ylabel(’time’) zlabel(’Temperature’) %The graphic of the exact solution in 3D figure mesh(x,time,u3’) title(’The exact solutions for h=1/32,at T=1’) xlabel(’x’) ylabel(’time’) zlabel(’Temperature’) Trong đó, ta dùng chương trình con để tính u0: function u = u_exact(x) % Initial Condition u =sin(2*pi*x); Tính nghiệm chính xác uexact(x) function u3 = u_exact(x,t) % The exact solution u3 =(1/2)*(sin(2*pi*(x+t))+sin(2*pi*(x-t))); 4.2. Các bài toán của Elliptic MATLAB program 4: Bài toán mô hình phương trình Helmholtz function FDM_singlerun(N) % Solves the following elliptic PDE using a finite difference method % u_xx + u_yy + f u = g in [0,1] % u = exact_u on the boundary of [0,1] 61 h = 1/N; global x y P x = zeros(N+1,1); y = zeros(N+1,1); P = zeros(N+1,N+1); global u_type f_type %u_type = 1; %u = sin(pi*x)*sin(pi*y) %u_type = 2; %u = x*y*(x-1)*(y-1) %u_type = 3; %u = x^2 + y^2 %u_type = 4; %u = x^3 + y^3 %u_type = 5; %u = sin(pi*x)*cos(pi*y) u_type = 6; %u = sin(pi*x) + cos(pi*y) %u_type = 7; %u = sin(pi(x+y)) %u_type = 8; %u = sin(pi(x^2+y^2)) %u_type = 9; %u = x^2 %u_type = 10; %u = x %f_type = 1; %f = 0 f_type = 2; %f = 1 %f_type = 3; %f = x*y %f_type = 4; %f = x^2+y^2 % Define the grid for i = 1:N+1; x(i) = (i-1)*h; end for j = 1:N+1; y(j) = (j-1)*h; end % Enforcing boundary conditions: % For x=0 and x=1 for j = 1:N+1 P(1, j) = exact_u(0,y(j)); P(N+1,j) = exact_u(1,y(j)); end % For y=0 and y=1 for i = 1:N+1 P(i,1) = exact_u(x(i),0); P(i,N+1) = exact_u(x(i),1); end % Generate the LHS matrix A A = zeros((N-1)^2,(N-1)^2); for i = 1:(N-1)^2 A(i,i) = 4; end % Add contributions from the f u term for j = 1:N-1 62 Tạp chí Epsilon, Số 13, 02/2017 Tạp chí Epsilon, Số 13, 02/2017 %disp([’j = ’,num2str(j)]) for i = 1:N-1 %disp([’i = ’,num2str(i)]) A((j-1)*(N-1)+i,(j-1)*(N-1)+i) = A((j-1)*(N-1)+i,(j-1)*(N-1)+i) - h^2*f(x(i+1),y(j+1)); end end for i = 1:(N-1)^2-1 if mod(i,N-1) ~= 0 A(i,i+1) = -1; end end for i = 1:(N-1)^2-3 A(i,i+(N-1)) = -1; end for i = 2:(N-1)^2 if mod(i,N-1) ~= 1 A(i,i-1) = -1; end end for i = N:(N-1)^2 A(i,i-(N-1)) = -1; end %disp(A) % Generate the RHS vector b. b = zeros((N-1)^2,1); for j = 1:N-1 for i = 1:N-1 b((j-1)*(N-1)+i) = b((j-1)*(N-1)+i) - h^2*g(x(i+1),y(j+1)); end end % Add contributions to b from the BC % Contributions corresponding to y = 0 for i = 1:N-1 b(i) = b(i) + P(i+1,1); %b(i) = b(i) + P(1,i+1); end % Contributions corresponding to y = 1 for i = 1:N-1 b((N-1)^2-(N-1)+i) = b((N-1)^2-(N-1)+i) + P(i+1,N+1); %b((N-1)^2-(N-1)+i) = b((N-1)^2-(N-1)+i) + P(N+1,i+1); end % Contributions corresponding to x = 0 for i = 1:N-1 b((i-1)*(N-1)+1) = b((i-1)*(N-1)+1) + P(1,i+1); %b((i-1)*(N-1)+1) = b((i-1)*(N-1)+1) + P(i+1,1); 63 Tạp chí Epsilon, Số 13, 02/2017 end % Contributions corresponding to x = 1 for i = 1:N-1 b(i*(N-1)) = b(i*(N-1)) + P(N+1,i+1); %b(i*(N-1)) = b(i*(N-1)) + P(i+1,N+1); end u = A\b; u_temp = zeros(N-1,N-1); for j = 1:N-1 u_temp(:,j) = u((j-1)*(N-1)+1:j*(N-1)); end for j = 2:N P(2:N,j) = u_temp(:,j-1); end % Plot the approximate solution of u(x,y) in 3D figure; surface(x,y,P’); view(3) title(’\Delta u + f u = g’) xlabel(’x’); ylabel(’y’); zlabel(’u(x,y)’) % Plot the exact solution of u(x,y) in 3D [X,Y] = meshgrid(0:1/N:1,0:1/N:1); %Z = sin(pi*X)*sin(pi*Y); %case 1; %Z = X*Y*(X-1)*(Y-1); %case 2; %Z = X^2 + Y^2; %case 3; %Z = X^3 + Y^3; %case 4; %Z = sin(pi*X)*cos(pi*Y); %case 5; %Z = sin(pi*X) + cos(pi*Y); %case 6; Z = sin(pi*(X+Y)); %case 7; %Z = sin(pi*(X^2+Y^2)); %case 8; %Z = X^2; %case 9; %Z = X; %case 10; figure title(’The exact solution of u(x,y)= sin(pi*(x+y))’) surface(X,Y,Z); view(3) get_error() Trong đó hàm Laplace là function Laplace_u = Laplace_u(x,y) global u_type 64 Tạp chí Epsilon, Số 13, 02/2017 switch u_type case 1; Laplace_u = -2*pi^2*sin(pi*x)*sin(pi*y); % u = sin(pi*x)*sin(pi*y) case 2; Laplace_u = 2*(x^2+y^2-x-y); %u = xy(x-1)(y-1) case 3; Laplace_u = 4; %u = x^2 + y^2 case 4; Laplace_u = 6*(x+y); %u = x^3 + y^3 case 5; Laplace_u = -2*pi^2*sin(pi*x)*cos(pi*y); % u = sin(pi*x)*cos(pi*y) case 6; Laplace_u = -pi^2*(sin(pi*x)+cos(pi*y)); % u = sin(pi*x) + cos(pi*y) case 7; Laplace_u = -2*pi^2*sin(pi*(x+y)); % u = sin(pi(x+y)) case 8; Laplace_u = 4*pi*cos(pi*(x^2+y^2)) - 4*pi^2*y^2*sin(pi*(x^2+y^2)); % u = sin(pi(x^2+y^2)) case 9; Laplace_u = 2; % u = x^2 case 10;Laplace_u = 0; % u = x otherwise; disp(’Missing u_type!’) end Hàm g là: function g = g(x,y) % \Delta u + f u = g g = Laplace_u(x,y) + f(x,y)*exact_u(x,y); Hàm f là: function f = f(x,y) global f_type switch f_type case 1; f = 0; case 2; f = 1; case 3; f = x*y; case 4; f = x^2 + y^2; otherwise; disp(’Missing f_type!’) end Tính toán sai số: function get_error() global x y P error N = length(x)-1; error_mat = zeros(N+1,N+1); for i = 1:N+1 65 Tạp chí Epsilon, Số 13, 02/2017 for j = 1:N+1 error_mat(i,j) = abs(P(i,j)-exact_u(x(i),y(j))); end end error = max(max(error_mat)); Các hàm u chính xác: function u = exact_u(x,y) global u_type switch u_type case 1; u = sin(pi*x)*sin(pi*y); case 2; u = x*y*(x-1)*(y-1); case 3; u = x^2 + y^2; case 4; u = x^3 + y^3; case 5; u = sin(pi*x)*cos(pi*y); case 6; u = sin(pi*x) + cos(pi*y); case 7; u = sin(pi*(x+y)); case 8; u = sin(pi*(x^2+y^2)); case 9; u = x^2; case 10;u = x; otherwise; disp(’Missing u_type!’) end Tài liệu Xem trong bài viết Epsilon số 11. 66 Tạp chí Epsilon, Số 13, 02/2017 SO SÁNH TOÁN IMO VÀ TOÁN NGHIÊN CỨU? TRƯỜNG HỢP LÝ THUYẾT RAMSEY W.Timothy Gowers Người dịch: Nguyễn Vũ Duy Linh TÓM TẮT Mặc dù các thí sinh IMO và các nhà nghiên cứu toán học đều cố gắng giải những bài toán khó nhưng có những sự khác biệt quan trọng giữa hai hoạt động này. Một phần là vì các bài toán nghiên cứu sử dụng các khái niệm và kiến thức của chương trình đại học được loại bỏ khỏi các bài toán IMO. Tuy nhiên có những khác biệt căn bản hơn. Để minh họa điều này, ta sẽ xem xét một số kết quả và câu hỏi trong lý thuyết Ramsey, lĩnh vực vừa là nguồn đề tài cho các bài toán IMO và các bài toán nghiên cứu. 1. Mở đầu Nhiều người đặt câu hỏi ở mức độ nào những thành tích ở cuộc thi toán quốc tế (IMO) sẽ dự báo cho những thành công trong nghiên cứu toán học. Đây là một câu hỏi thú vị: Nhiều ngôi sao IMO sau đó đã có một sự nghiệp nghiên cứu rất thành công, trong khi những người khác sau đó bỏ toán hoàn toàn (và thường cũng có những thành công nổi bật ở các lĩnh vực khác). Có lẽ điều đúng nhất mà ta có thể nói là khả năng làm bài tốt ở cuộc thi IMO tương thích với khả năng làm nghiên cứu tốt, nhưng không hoàn toàn. Điều này không có gì ngạc nhiên, bởi vì hai hoạt động này có những điều tương đồng và những sự khác biệt quan trọng. Điểm tương đồng chính là rất rõ ràng: Trong cả hai trường hợp người ta đều cố gắng giải các vấn đề toán học. Trong bài viết này, tôi muốn đặt trọng tâm vào những sự khác biệt bằng cách xem xét một lĩnh vực của toán học, lý thuyết Ramsey vốn là nguồn đề tài của cả các bài toán Olympiad và các bài toán nghiên cứu quan trọng. Tôi hy vọng chỉ ra rằng có một con đường khá liên tục từ vấn đề này sang vấn đề khác, nhưng hai điểm kết thúc của con đường này lại hoàn toàn khác nhau. Các tài liệu trình bày về lý thuyết Ramsey thường mở đầu bằng bài toán sau đây. Bài toán 1. Có sáu người trong phòng, hai người bất kỳ trong số họ hoặc là bạn của nhau hoặc là kẻ thù của nhau. Chứng minh rằng hoặc là có ba người sao cho hai người bất kỳ trong số họ là bạn của nhau, hoặc là có ba người sao cho hai người bất kỳ trong số họ là kẻ thù của nhau. 67 Tạp chí Epsilon, Số 13, 02/2017 Nếu bạn chưa gặp bài toán này (tôi vẫn nghĩ rằng hầu hết thí sinh IMO đều gặp phải), bạn nên giải nó trước khi đọc tiếp. Nó không khó, nhưng người ta học hỏi được nhiều khi tự giải nó. Để cho tiện, chúng ta phát biểu lại bài toán trước khi giải nó bằng cách lược bỏ đi những yếu tố không liên quan tới toán học (đó là người, tình bạn và tính thù) và chỉ xem xét đến yếu tố trừu tượng mấu chốt của bài toán. Một cách làm là biểu diễn mỗi người bằng một điểm trong đồ thị và nối mỗi cặp điểm bởi một đường (không nhất thiết phải là đường thẳng). Chúng ta được một đối tượng gọi là đồ thị đầy đủ bậc 6: Để biểu diễn tình bạn và tính thù, chúng ta nối hai người bạn bằng một đường màu đỏ và nối hai kẻ thù bằng một đường màu xanh. Như vậy chúng ta có 6 điểm mà mỗi cặp điểm được nối bằng một đường màu đỏ hay màu xanh. Thuật ngữ chuẩn của lý thuyết đồ thị gọi các điểm là đỉnh và các đường là cạnh. (Chúng ta chọn các từ này vì có một lớp đồ thị quan trọng sinh ra từ các đỉnh và cạnh của một đa diện. Trong ví dụ như vậy sẽ có các cặp điểm không nối với nhau bằng các cạnh trừ khi đa giác là một tứ diện: Do vậy chúng là những đồ thị không đầy đủ). Công việc của chúng ta giờ là chứng minh rằng phải có một tam giác màu đỏ hay một tam giác màu xanh trong đó tam giác trong ngữ cảnh này là một tập hợp của ba cạnh nối liền ba đỉnh. Để chứng minh điều này, hãy lấy một đỉnh bất kỳ. Đỉnh này được nối với năm đỉnh khác bằng các cạnh, như vậy theo nguyên lý chuồng bồ câu có ít nhất ba trong các cạnh này có cùng màu. Không làm mất tính tổng quát, giả sử đó là màu đỏ. Như vậy có ba đỉnh nối với đỉnh đầu tiên bằng cạnh đỏ. Nếu hai trong số ba đỉnh này nối với nhau bằng cạnh đỏ, chúng ta sẽ có một tam giác đỏ. Nếu không, cả ba cặp điểm tạo thành một nhóm nối với nhau bằng cạnh xanh và cho ta một tam giác xanh từ đó thu được điều phải chứng minh. Chúng ta hãy định nghĩa R.k; l/ là số nhỏ nhất n thỏa mãn nếu bạn tô xanh hay đỏ mỗi cạnh của một đồ thị đầy đủ bậc n thì bạn có thể tìm thấy k đỉnh trong đó hai đỉnh bất kỳ trong chúng nối với nhau bằng cạnh đỏ hay l đỉnh trong đó hai đỉnh bất kỳ trong chúng nối với nhau bằng cạnh xanh. Chúng ta vừa mới chứng minh xong R.3; 3/ 6 6: (Nếu bạn chưa thử, bạn có thể tìm được một cách tô xanh hay đỏ các cạnh một đồ thị đầy đủ có năm đỉnh thế nào cho không tồn tại một tam giác xanh hay đỏ). Điều này chưa cho chúng ta thấy rõ ngay định nghĩa trên là hợp lý: Định lý Ramsey khẳng định rằng R.k; l/ tồn tại và hữu hạn cho mỗi k và l: Một tổng quát hoá đơn giản của lý luận mà chúng ta dùng để chứng minh R.3; 3/ 6 6 có thể được dùng để chứng minh kết quả sau của Erdos và Szekeres, kết quả này chứng minh định lý Ramsey và cho chúng ta thông tin về độ lớn của R.k; l/: Định lý 1. Với mỗi k và l; chúng ta có bất đẳng thức R.k; l/ 6 R.k 1; l/ C R.k; l 1/: Một lần nữa, nếu như bạn chưa thấy kết quả này bao giờ, bạn cần tự mình chứng minh nó (bài toán này dễ hơn một bài toán IMO điển hình). Và bạn có thể dùng lý luận quy nạp chứng minh rằng bất đẳng thức trên suy ra R.k; l/ 6kCl2 k1 (chủ yếu để ý rằng R.k; 1/ D 1; hay an toàn hơn một chút R.k; 2/ D k; và từ đó bắt đầu phép quy nạp). Điều này cho chúng ta biết R.3; 4/ 6 10: Dầu vậy, trên thực tế câu trả lời chính xác là 9: Chứng minh nó là một bài toán thú vị hơn – không khó lắm, nhưng cần thêm ý tưởng. 68 Tạp chí Epsilon, Số 13, 02/2017 Từ điều này và bất đẳng thức của Erdos và Szekeres, chúng ta có thể suy ra R.4; 4/ 6 R.3; 4/C R.4; 3/ D 18; đây là câu trả lời chính xác: Để thấy rõ bạn cần xem xét một đồ thị đầy đủ bậc 17 có các cạnh được tô xanh hay đỏ sao cho không có bốn đỉnh nào nối lại với nhau bằng cạnh đỏ và cũng không có bốn đỉnh nào nối với nhau bằng cạnh xanh. Một đồ thị như vậy là tồn tại và hơn thế khá đẹp: Như mọi khi, tôi sẽ không làm hỏng cuộc vui bằng cách nói ra đó là cái gì. Chúng ta sẽ không phải đi xa hơn thế trước khi chúng ta bước vào vương quốc của những điều chưa biết. Áp dụng bất đẳng thức Erdos–Szekeres một lần nữa, ta có R.3; 5/ 6 R.2; 5/ C R.3; 4/ D 5 C 9 D 14: Giá trị này là chính xác. Và ngoài ra R.4; 5/ 6 R.4; 4/ C R.3; 5/ D 32: Năm 1995; McKay và Radziszowski, với sự giúp đỡ của máy tính, chứng minh rằng, trên thực tế R.4; 5/ D 25: Cho đến nay, người ta vẫn chưa tìm ra giá trị chính xác của R.5; 5/: Điều mà ta biết tốt nhất về R.5; 5/ là nó nằm trong khoảng 43 và 49: Ngay cả khi giá trị này là 43; phép tìm kiếm thô trên máy tính duyệt qua 2.432 / phép tô màu xanh đỏ đồ thị đầy đủ bậc 43 là quá lâu để khả thi. Tất nhiên là có những cách giảm nhẹ phép tìm kiếm nhưng cho tới nay vẫn chưa khả thi trên máy tính. Kể cả khi có ai đó tính được R.5; 5/; chúng ta cũng khó biết được R.6; 6/ là bao nhiêu (chúng ta biết nó nằm trong khoảng 102 và 165). Các bạn có thể hỏi tại sao chúng ta không đề ra một lý thuyết chứ không phải là kiểu suy luận xấu xí kiểm tra một lượng lớn các đồ thị trên máy tính? Lý do là những đồ thị lớn nhất không có k đỉnh nối với nhau bằng cạnh đỏ hay l đỉnh nối với nhau bằng cạnh xanh thường không có tính cấu trúc. Do đó những đồ thị cho thấy R.3; 3/ > 5; R.3; 4/ > 8 và R.4; 4/ > 17 thường làm lệch hướng suy luận vì chúng rất có cấu trúc. Đây có vẻ là ví dụ của cái gọi là “luật của những số nhỏ” (ví dụ đơn giản hơn là ba số nguyên tố đầu tiên 2; 3 và 5 là ba số Fibonacci liên tiếp. Sự kiện này không có gì đáng kể khi nhiều số nhỏ trùng khớp ngẫu nhiên). Do vậy chúng ta cảm thấy không thỏa mãn khi không có một lý thuyết nào đưa ra công thức chính xác cho R.k; l/; và điều tốt nhất mà người ta có thể làm là đưa ra một phương pháp tìm kiếm thông minh trên máy tính cho k và l nhỏ. Điều này có vẻ như là một thất bại, nhưng Godel đã dạy chúng ta rằng chúng ta không thể giả sử mọi thứ mà chúng ta muốn biết đều có chứng minh. Trong trường hợp của những số Ramsey nhỏ, chúng ta không học được gì trực tiếp từ định lý Godel, vì về nguyên tắc chúng ta có thể tính ra chúng bằng các phương pháp tìm kiếm thô mặc dầu chúng không thực tế lắm. Mặc dầu vậy thông điệp tổng quát bảo rằng những sự kiện đẹp đẽ không nhất thiết phải có những chứng minh đẹp đẽ vẫn được áp dụng và có một tác động đến cuộc sống của những nhà nghiên cứu toán học, nó có thể được tóm tắt trong chiến lược giải quyết vấn đề tổng quát sau (tôi không đề nghị chiến lược này cho những thí sinh thi olympic toán). Chiến lược 1. Khi một vấn đề làm bạn bế tắc, đôi khi điều tốt nhất là đầu hàng 69 Tạp chí Epsilon, Số 13, 02/2017 Trên thực tế, tôi cũng không hoàn toàn đề nghị chiến lược này cho những nhà nghiên cứu toán học trừ khi nó đi cặp với nguyên tắc lạc quan hơn sau đây (một lần nữa tôi không đề nghị chiến lược này cho những thí sinh thi olympic toán). Chiến lược 2. Nếu bạn không thể trả lời câu hỏi thì hãy thay đổi nó. 2. Tiệm cận của số Ramsey Một trong những đường lối chung nhất để thay đổi một câu hỏi toán học khi chúng ta rơi vào một tình huống như trên, như khi chúng ta không thể tính một đại lượng một cách chính xác, là tìm xấp xỉ tốt nhất cho nó, hay là ít nhất chứng minh rằng đại lượng đó phải nằm giữa L và U, trong đó chúng ta cố gắng làm cho L (gọi là chặn dưới) và U (gọi là chặn trên) càng gần nhau càng tốt. : Chúng ta vừa mới tìm được chặn trên cho R.k; l/ đó chính là kCl2 k1 Để cho đơn giản, chúng ta xét trường hợp k D l: Khi đó chúng ta thu nhận được chặn trên 2k2 k1 : Liệu chúng ta có thể tìm được một chặn dưới so sánh được với nó? Trước khi trả lời câu hỏi này, chúng ta thử nghĩ xem 2k2 k1 lớn cỡ bao nhiêu. Một xấp xỉ khá tốt (nhưng không phải bằng những phương tiện tốt nhất được biết) được cho bởi công thức .k /12 4k1có tốc độ tăng tương đương với 4k(vì tỷ số các giá trị liên tiếp của hàm số này ngày càng gần 4). Đó là một hàm khá lớn theo k: Liệu có hy vọng gì tìm được một chặn dưới của một cái gì đó cỡ như vậy? Nếu thuật ngữ “tìm kiếm” có nghĩa là viết xuống một qui tắc khi nào tô một cạnh đỏ và khi nào tô cạnh ấy xanh thì câu trả lời sẽ là tìm kiếm chặn dưới lớn cỡ hàm mũ là một bài toán vô cùng khó không giải được (mặc dầu ta cũng có vài kết quả thú vị nếu đi theo hướng này). Tuy vậy vào năm 1947; Erdos đã tìm ra một phương pháp đơn giản mà hiệu quả cho phép tìm ra chặn dưới có độ lớn hàm mũ mà không đi theo hướng trên. Thay vì trình bày chứng minh của Erdos, tôi sẽ cho các bạn biết ý tưởng của chứng minh đó. Để thuận tiện chúng ta đưa vào thuật ngữ sau. Nếu chúng ta có một đồ thị đầy đủ bậc n có các cạnh được tô màu xanh đỏ thì chúng ta sẽ gọi tập hợp các đỉnh là đơn sắc nếu hai đỉnh bất kỳ của tập hợp đó được nối bằng các cạnh cùng màu. Ý tưởng chứng minh. Đừng cố gắng tìm một cách tô màu thoả mãn bài toán. Vì vậy, chọn các màu một cách tuỳ ý và chứng minh rằng số trung bình của các tập hợp đơn sắc cỡ k nhỏ hơn 1: Nếu chúng ta có thể làm được điều này thì phải có một đồ thị không có tập hợp đơn sắc cỡ k vì ngược lại số trung bình sẽ ít nhất bằng 1: Lý luận này cần một lượng tính toán đơn giản đến ngạc nhiên, và chúng cho thấy R.k; k/ tối thiểu phải bằng p2k (trên thực tế, người ta đạt được một ước lượng lớn hơn một chút, nhưng không đủ lớn để ảnh hưởng đến vấn đề đang bàn cãi). Tin tốt là chặn dưới có độ lớn hàm mũ. Tin xấu là p2k nhỏ hơn 4krất nhiều. Liệu có ai đó có thể cải thiện chặn trên hay chặn dưới không? Đây là một trong những vấn đề mở trung tâm của lý thuyết tổ hợp. 70 Tạp chí Epsilon, Số 13, 02/2017 Bài toán 2. Liệu có tồn tại hằng số ˛ > p2 thế nào cho với mọi k đủ lớn chúng ta có chặn dưới R.k; k/ > 1k; hay là hằng số ˇ < 4 thế nào cho với mọi k đủ lớn chúng ta có chặn trên R.k; k/ 6 ˇk? Sau đây là một câu hỏi tham vọng hơn. Bài toán 3. Liệu đại lượng R.k; k/ 1k có hội tụ về một giới hạn và nếu có thì giới hạn đó bằng bao nhiêu. Có khả năng R.k; k/ 1k dần về một giới hạn. Ba khả năng có thể xảy ra là giới hạn đó bằng p2; 2 hay 4: Tôi không có một lý lẽ thuyết phục nào cho thấy số nào có khả năng hơn hai số còn lại. Trong vài chục năm người ta chỉ đạt được một chút tiến bộ đối với những vấn đề này. Như vậy chúng ta đầu hàng sao? Chắc chắn không. Có một sự khác biệt rất lớn giữa những vấn đề rất khó khăn này và vấn đề rất khó là tính toán R.6; 6/ mà người ta mong đợi một lý thuyết đẹp đẽ: Chỉ là quá khó khăn để tìm ra nó. Đầu hàng với các phương pháp tìm kiếm chẳng qua chỉ vì nó quá khó đối với tinh thần nghiên cứu toán học. (Đôi khi một nhà toán học đơn lẻ được khuyên nên đầu hàng một vấn đề sau khi phí một thời gian dài cho nó mà không đi đến đâu. Nhưng ở đây tôi nói đến nỗ lực tập thể: Tất cả các nhà tổ hợp lúc này hay lúc khác cố gắng cải thiện chặn trên chặn dưới của R.k; k/ và tôi nói rằng điều này nên tiếp tục cho đến khi thực hiện xong). 3. Lý thuyết Ramsey nói chung là gì? Một định lý điển hình của lý thuyết Ramsey liên quan đến một cấu trúc có nhiều cấu trúc con tương tự như cấu trúc ban đầu. Nó nói rằng nếu bạn tô màu các phần tử của cấu trúc chính bằng hai màu (hay tổng quát hơn bằng r màu với r là một số nguyên dương nào đó), thì bạn ắt phải tìm thấy một cấu trúc con có tất cả các phần tử được tô bằng cùng một màu. Chẳng hạn, định lý Ramsey khẳng định trong trường hợp k D 1; cấu trúc chính là đồ thị đầy đủ bậc R.k; k/ (hay nói một cách chính xác hơn, các cạnh của đồ thị đầy đủ) và các cấu trúc con là tất cả đồ thị con đầy đủ bậc k: Vài định lý Ramsey còn cho biết kích thước của cấu trúc con phụ thuộc như thế nào vào kích thước của cấu trúc chính và số lượng các màu. Đây là một ví dụ khác, định lý nổi tiếng của Van der Waerden. Định lý 2. Cho r và k là hai số nguyên dương. Tồn tại số tự nhiên n sao cho nếu bạn tô màu các số của một cấp số cộng X có chiều dài n bằng r màu thì bạn ắt phải tìm thấy một cấp số cộng Y bên trong X có chiều k sao cho mọi số của Y được tô bằng cùng một màu. Tôi có thể nói nhiều về định lý Van der Waerden và các nhánh rẽ của nó, nhưng điều đó sẽ làm mờ nhạt các bài toán IMO và các bài toán nghiên cứu mà tôi quan tâm. Thay vào đó, tôi muốn đi theo một hướng khác. 71 Tạp chí Epsilon, Số 13, 02/2017 4. Một cấu trúc vô hạn và một định lý Ramsey tương ứng Cho đến giờ, các cấu trúc mà chúng ta tô màu – các đồ thị đầy đủ và các cấp số cộng – đều là hữu hạn. Có một phiên bản của định lý Ramsey đúng cho các đồ thị đầy đủ vô hạn (phát biểu và chứng minh định lý này là một bài tập thú vị dành cho các bạn), nhưng tôi muốn quan tâm tới một cấu trúc phức tạp hơn: Không gian của mọi dãy nhị phân vô hạn tận cùng bằng không. Ví dụ về một dãy như vậy là 001001110110000000000000000000000000000000000000000000000000 : : : Nếu s và t là hai dãy như vậy, và nếu chữ số 1 cuối cùng trong s đứng trước chữ số 1 đầu tiên trong t thì chúng ta viết s < t: (Một cách hình dung cho dễ là mọi hành động trong s đều đã chấm dứt khi hành động trong t bắt đầu.) Trong trường hợp đó, s C t sẽ là một dãy nhị phân vô hạn khác tận cùng bằng các chữ số 0: Chẳng hạn bạn có thể cộng 001001110110000000000000000000000000000000000000000000000000 : : : vào 000000000000000110001100011000000000000000000000000000000000 : : : Và bạn sẽ nhận được dãy 001001110110000110001100011000000000000000000000000000000000 : : : Bây giờ giả sử rằng chúng ta có các dãy s1 < s2 < s3 < s4 < Điều này có nghĩa là mỗi si là một dãy các chữ số 0 và 1; và tất cả những chữ số 1 trong siC1 đi sau tất cả những chữ số 1 trong si: (Để ý rằng (s1; s2; s3; : : :) là một dãy của các dãy). Do vậy nếu chúng ta lấy tổng của hữu hạn các dãy si phân biệt, chúng ta sẽ nhận được một dãy khác nằm trong không gian của chúng ta. Chẳng hạn chúng ta có thể lấy tổng s1 C s2, hay là s3 C s5 C s6 C s201: Tập hợp của mọi tổng có thể có kiểu như vậy gọi là không gian con sinh bởi s1; s2; s3; : : : Giờ đây toàn bộ không gian của những dãy mà chúng ta nói đến có thể xem như không gian con sinh bởi các dãy 1000000 : : : ; 0100000 : : : ; 0010000 : : : ; 0001000 : : : ; và cứ thế tiếp tục. Vậy cấu trúc của toàn bộ không gian đằng nào đi nữa cũng đồng nhất với một không gian con bất kỳ của nó. Đây là ứng cử viên lý tưởng cho định lý kiểu Ramsey. Chúng ta thậm chí còn đoán được định lý này nói gì. Định lý 3. Giả sử các dãy nhị phân tận cùng bằng không được tô bằng hai màu. Thế thì ắt phải có một tập hợp vô hạn các dãy s1 < s2 < s3 < sao cho tất cả mọi dãy trong không gian con sinh bởi si được tô bằng cùng một màu. Đó là cho dù bạn tô màu các dãy bằng cách nào đi chăng nữa, bạn có thể tìm được một dãy các dãy si sao cho s1; s2; s1 C s2; s3; s1 C s3; s2 C s3; s1 C s2 C s3; s4; : : : có cùng một màu. Đây là định lý do Hindman tìm ra, nó quá khó để có thể xem như một bài tập. Dầu vậy, có một bài tập đơn giản là một khi bạn đã có định lý Hindman cho hai màu, bạn có thể suy ra định lý tương tự như vậy cho hữu hạn màu. Định lý Hindman thường được phát biểu dưới dạng tương đương dễ hiểu hơn nhưng ít liên quan đến điều tôi đề cập lúc này. Chứng minh sự tương đương giữa hai định lý này là một bài tập khác không khó lắm. 72 Tạp chí Epsilon, Số 13, 02/2017 Định lý 4. Giả sử những số nguyên dương được tô bởi hai màu. Thế thì có thể tìm được những số nguyên dương n1 < n2 < n3 < sao cho tổng hữu hạn các ni có cùng màu. Phiên bản này của định lý liên quan đến phép cộng. Điều gì xảy ra nếu chúng ta quan tâm đến phép nhân? Chúng ta hầu như không biết chắc, vì câu hỏi có vẻ ngây thơ sau đây là một bài toán không giải được. Bài toán 4. Giả sử các số nguyên dương được tô bằng hữu hạn màu. Phải chăng luôn luôn có thể tìm được các số nguyên n và m sao cho n; m; n C m và nm có cùng một màu? Liệu ít nhất có thể bảo đảm rằng m C n và mn có cùng một màu (ngoại trừ trường hợp tầm thường m D n D 2)? Bài toán này có vẻ giống như một bài toán IMO. Điểm khác nhau là ở chỗ nó khó hơn rất nhiều (và người ta không biết đã có ai đó giải nó chưa và nghĩ rằng nó phù hợp với một cuộc tranh tài toán học). 5. Từ lý thuyết tổ hợp đến hình học vô hạn chiều Chúng ta trình bày không gian ba chiều nhờ toạ độ. Một khi đã làm xong điều đó, chúng ta dễ dàng định nghĩa không gian d chiều với d là một số nguyên dương bất kỳ. Tất cả những điều mà chúng ta phải làm là trình bày các khái niệm bằng thuật ngữ toạ độ và kế đó tăng số lượng các toạ độ. Chẳng hạn một hình lập phương bốn chiều có thể được định nghĩa như tập hợp các điểm .x; y; z; w/ trong đó mỗi số x; y; z và w nằm trong khoảng 0 và 1: Nếu chúng ta muốn (như chúng ta thường làm với các bài toán trình độ đại học), chúng ta còn có thể mở rộng các khái niệm của chúng ta ra không gian vô hạn chiều. Chẳng hạn, một hình cầu vô hạn chiều bán kính 1 có thể được định nghĩa là tập hợp của mọi dãy .a1; a2; a3; : : :/ số thực thoả mãn a21 C a22 C a23 C D 1: (Ở đây tôi dùng chữ “hình cầu” theo nghĩa là mặt ngoài của quả cầu chứ không phải là một khối cầu đặc). Trong thế giới vô hạn chiều của chúng ta, chúng ta cũng muốn nói đến đường thẳng, mặt phẳng và những “siêu phẳng” đa chiều. Nói riêng, chúng ta quan tâm đến những siêu phẳng vô hạn chiều. Làm thế nào để chúng ta định nghĩa chúng? Vâng, một mặt phẳng đi qua gốc toạ độ trong không gian ba chiều có thể được định nghĩa bằng cách lấy hai điểm x D .x1; x2; x3/ và y D .y1; y2; y3/ và thành lập mọi tổ hợp x C y của hai điểm này. (Ở đây, x C y, khi viết dưới dạng toạ độ sẽ là ( x1 C y1; x2 C y2; x3 C y3//: Chúng ta có thể tiến hành tương tự trong không gian vô hạn chiều. Chúng ta lấy dãy các điểm p1; p2; p3; : : : (ở đây mỗi pi sẽ là một dãy vô hạn các số thực) và chúng ta lấy tất cả các tổ hợp (trong một số điều kiện nào đó có tính kỹ thuật) có dạng 1p1 C 2p2 C 3p3 C Giao của một mặt cầu vô hạn chiều với một siêu phẳng vô hạn chiều hoá ra là một mặt cầu vô hạn chiều khác. (Tạm gác yếu tố vô hạn chiều, điều này cũng giống như khi chúng ta cắt một 73 Tạp chí Epsilon, Số 13, 02/2017 mặt cầu bằng một mặt phẳng, chúng ta sẽ được một đường tròn). Chúng ta hãy gọi đây là mặt cầu con của mặt cầu nguyên thuỷ. Một lần nữa chúng ta cảm thấy rằng đây là điều kiện lý tưởng cho một định lý kiểu Ramsey vì chúng ta có một cấu trúc (một mặt cầu) với nhiều cấu trúc con (các mặt cầu con) giống với cấu trúc ban đầu một cách chính xác. Giả sử rằng chúng ta tô một mặt cầu vô hạn chiều với hai màu. Liệu chúng ta có thể tìm được một mặt cầu con được tô bởi một màu? Có một vài lý do để mong đợi một kết quả như vậy là đúng. Sau hết, nó khá tương tự với định lý Hindman ở chỗ cả hai phát biểu đều liên quan đến việc tô màu một đối tượng vô hạn chiều nào đó, định nghĩa bởi toạ độ, và tìm kiếm một đối tượng con vô hạn chiều cùng loại đơn sắc. Nó giống như trong định lý Hindman khi mọi toạ độ đều là 0 hay 1: Mặc dầu vậy, không may câu trả lời là không. Nếu p thuộc về một mặt cầu con thì –p phải thuộc về chính mặt cầu con đó. Như vậy chúng ta có thể tô màu p đỏ nếu toạ độ đầu tiên khác không là dương và tô p xanh nếu toạ độ đầu tiên khác không là âm. Bằng cách này p và –p luôn luôn nhận màu khác nhau. (Vì tổng bình phương các toạ độ của chúng bằng 1; chúng không thể bằng không tất cả). Nhận xét khó chịu này làm rõ một điểm khác nhau nữa giữa các bài toán IMO và các vấn đề trong nghiên cứu toán học. Nguyên lý 1. Một tỷ lệ lớn các giả thuyết phát sinh trong quá trình nghiên cứu của một ai đó hoá ra là dễ dàng hay là được phát biểu sai. Người ta phải may mắn lắm mới gặp phải một bài toán thú vị. Mặc dầu vậy, trong những trường hợp này, chúng ta có thể áp dụng một phương án của chiến lược mà tôi đề cập trước đó. Chiến lược 3. Nếu vấn đề mà bạn suy nghĩ hoá ra là không thú vị, hãy thay đổi nó. Đây là một thay đổi nhỏ trong bài toán tô màu các mặt cầu biến bài toán này từ một bài toán dở thành một bài toán tuyệt vời. Chúng ta hãy gọi một mặt cầu con là c-đơn sắc nếu như có một màu sao cho mỗi điểm của mặt cầu con nằm trong khoảng cách c tính từ một điểm nào đó được tô màu này. Chúng ta xét c nhỏ, như vậy về cơ bản chúng ta không yêu cầu mọi điểm của mặt cầu con đều là đỏ (chẳng hạn vậy), mà chỉ đơn thuần mỗi điểm của mặt cầu con gần với một điểm đỏ. Bài toán 5. Nếu như mặt cầu vô hạn chiều được tô bởi hai màu, và c là một số thực dương, liệu chúng ta luôn luôn có thể tìm được một mặt cầu con vô hạn chiều c đơn sắc? Đây là một vấn đề mở trong một thời gian dài và trở thành một câu hỏi chủ điểm trong lý thuyết không gian Banach, nó chính thức hoá ý tưởng của không gian vô hạn chiều và là một trong những khái niệm chủ đạo của toán học ở tầm nghiên cứu. Không may thay, nó cũng đã có câu trả lời phủ định, nhưng phản ví dụ cho vấn đề này là thú vị hơn nhiều và kém rõ ràng hơn nhiều so với phản ví dụ cho phiên bản xấu của vấn đề. Nó được tìm ra bởi Odell và Schlumprecht. 74 Tạp chí Epsilon, Số 13, 02/2017 Ví dụ của Odell và Schlumprecht làm tiêu tan hy vọng tìm ra một định lý kiểu Hindman cho không gian Banach (ngoại trừ một không gian đặc biệt khá tương tự với không gian các dãy nhị phân mà tôi có tìm được một định lý). Mặc dầu vậy, nó không phá vỡ hoàn toàn mối liên hệ giữa lý thuyết Ramsey và lý thuyết không gian Banach như chúng ta thấy trong phần kế tiếp. Trước khi chúng ta chấm dứt phần này, cho phép tôi đề cập thêm một sự khác nhau giữa các bài toán IMO và các bài toán nghiên cứu. Nguyên lý 2. Một vấn đề nghiên cứu có thể thay đổi từ chỗ không thể đạt được một điều gì hết sang một mục tiêu thực tiễn. Đối với ai đó chỉ có kinh nghiệm với những bài toán IMO, điều này có vẻ kỳ lạ: Làm sao mà cái khó của bài toán có thể thay đổi theo thời gian? Nhưng nếu bạn nhìn lại kinh nghiệm toán học của chính mình, bạn sẽ thấy nhiều ví dụ mà các bài toán “trở nên dễ dàng”. Chẳng hạn xét bài toán tìm số thực dương x sao cho x1x cực đại. Nếu bạn biết dùng đúng công cụ, bạn sẽ lý luận như sau. Logarithm của x1x là log x đương với cực đại hoá log x x; và logarithm là một hàm tăng, cho nên bài toán tương x. Lấy đạo hàm ta được 1log x x2; đạo hàm này triệt tiêu khi x D e và hàm số giảm tại đó. Như vậy cực đại đạt được tại x D e: Lời giải này nói chung không phức tạp trên cả hai phương diện hiểu được nó và tìm lời giải nhưng chỉ dành cho những ai hiểu biết một chút về giải tích. Cho nên bài toán là ngoài tầm tay những ai không biết giải tích và mục tiêu thực tiễn mà những người biết giải tích làm. Một điều tương tự như vậy xảy ra trong nghiên cứu toán học, nhưng điều mà tôi muốn nhấn mạnh thêm là nó có thể là một hiện tượng tập thể chứ không chỉ là một cá nhân đơn lẻ. Đó là có nhiều bài toán ngoài tầm tay đơn giản chỉ vì người ta chưa phát minh ra đúng thứ công cụ cần dùng. Bạn có thể thắc mắc rằng điều này không thực sự có nghĩa là bài toán ngoài tầm tay: Nó chỉ có nghĩa là một phần của việc giải toán là phát minh ra đúng kỹ thuật cần dùng. Trên một phương diện, điều này đúng, nhưng chúng ta đã không nhận thấy một sự kiện là những kỹ thuật toán học thường dùng để giải nhiều bài toán, nhưng các bài toán này lại không phải là chính các bài toán đã thúc đẩy người ta phát minh ra những kỹ thuật này. (Chẳng hạn, Newton và Leibniz không hề phát minh ra giải tích để chúng ta cực đại hoá hàm x1x ). Như vậy, có thể xảy ra là Bài toán B trở thành một mục tiêu thực tế bởi vì có ai đó đã phát minh ra đúng kỹ thuật cần dùng trong khi suy nghĩ Bài toán A: Tôi đề cập tất cả những điều này tại đây vì Odell và Schlumprecht xây dựng phản ví dụ của mình bằng cách sửa đổi (theo cách thông minh nhất) một ví dụ của Schlumprecht xây dựng vài năm trước đây vì một mục tiêu hoàn toàn khác. 6. Nói thêm một chút về không gian Banach Tôi nhận thấy tôi chưa giải thích thật rõ ràng không gian Banach là gì, và tôi cần nhấn mạnh rằng khái niệm khoảng cách trong không gian vô hạn chiều chỉ là sự tổng quát hoá định lý Pythagore và khoảng cách của một điểm .a1; a2; a3; : : :/ đến gốc toạ độ được định nghĩa là q a21 C a22 C a23 C 75 Tạp chí Epsilon, Số 13, 02/2017 Mặc dầu vậy, các khái niệm khoảng cách khác có thể được dùng và tiện dụng. Chẳng hạn với mọi p > 1 chúng ta có thể định nghĩa khoảng cách từ .a1; a2; a3; : : :/ đến gốc toạ độ là .ja1jp C ja2jp C ja3jp/1p : Tất nhiên có những dãy mà con số này là vô hạn. Chúng ta xem như những dãy này không thuộc về không gian. Ban đầu không dễ nhận ra rằng khái niệm khoảng cách là hợp lý, nhưng hoá là nó có nhiều tính chất rất hay. Ký hiệu a và b cho các dãy .a1; a2; a3; : : :/ và .b1; b2; b3; : : :/; và ký hiệu jjajj và jjbjj cho các khoảng cách từ a và b đến gốc toạ độ (thường được gọi là chuẩn của a và b), chúng ta có thể diễn đạt lại các tính chất đó như sau. (i) jjajj D 0 nếu và chỉ nếu a D .0; 0; 0; : : :/: (ii) jj ajj D j j jjajj với mọi a: (iii) jja C bjj 6 jjajj C jjbjj với mọi a và b: Cả ba tính chất này đều quen thuộc với chúng ta giống như khái niệm khoảng cách thông thường trong không gian. (Để ý rằng chúng ta có thể định nghĩa khoảng cách từ a đến b là jja bjj). Một không gian Banach dãy là tập hợp các dãy trang bị một chuẩn thoã các tính chất (i) – (iii) nói trên, cùng với một điều kiện có tính chất kỹ thuật (gọi là tính đầy đủ) mà tôi không thảo luận ở đây. Một ví dụ đặc biệt khi jjajj được định nghĩa bằng P1 iD1a2ilà một loại không gian Banach rất đặc biệt gọi là không gian Hilbert. Tôi sẽ không nói không gian Hilbert là gì ngoại trừ đặc điểm không gian này có các tính chất đối xứng rất tốt. Một trong những tính chất lý thú này là mỗi không gian con của không gian Hilbert về căn bản rất giống với không gian sinh ra nó. Chúng ta đã thấy chuyện này: Khi chúng ta cắt một mặt cầu vô hạn chiều bởi một siêu phẳng vô hạn chiều, chúng ta nhận được một mặt cầu vô hạn chiều khác. Tính chất mọi không gian con đều “đẳng cấu” với cả không gian ban đầu có vẻ như không đúng cho mọi không gian khác, do vậy Banach tự đặt ra cho mình câu hỏi sau đây vào những năm 1930: Bài toán 6. Phải chăng mỗi không gian đẳng cấu với mọi không gian con vô hạn chiều của nó thì đẳng cấu với một không gian Hilbert? Phát biểu giảm nhẹ hơn là, phải chăng không gian Hilbert là không gian duy nhất có đặc tính lý thú này? Cái khó của câu hỏi này là hai không gian vô hạn chiều có thể đẳng cấu với nhau theo nhiều cách, do vậy loại bỏ chúng ra để chọn ra một không gian phi Hilbert và một không gian con khéo chọn nào đó có vẻ là điều khó khăn. Đây là một ví dụ khác cho thấy một bài toán có thể thay đổi từ chỗ không giải được sang chỗ có thể giải được nhờ phát triễn liên hệ với những bài toán khác, và có thể nói tôi vừa đủ may mắn ở vào đúng vị trí và vào đúng thời điểm. Một công trình của Komorowski và Tomczak–Jaegermann (một cách ngẫu nhiên, tôi đề cập tới vài nhà toán học mà tên gọi không có ý nghĩa lắm với hầu hết những độc giả của bài báo này, nhưng tôi quyết định chống lại cách 76 Tạp chí Epsilon, Số 13, 02/2017 giới thiệu họ bằng cách mở đầu “một nhà toán học gọi là”) cho thấy nếu như tồn tại một phản ví dụ cho bài toán thì nó khá là hiểm hóc theo một nghĩa nào đó. Không chắc là có một không gian hiểm hóc đến mức thỏa mãn yêu cầu, nhưng vài năm trước đây Maurey và tôi đã xây dựng một không gian rất hiểm hóc, và không gian hiểm hóc của chúng tôi hiểm hóc đến mức với mọi lý do khác nhau nó không thể là phản ví dụ cho câu hỏi của Banach. Nó làm tăng khả năng câu trả lời khẳng định cho câu hỏi của Banach bởi vì ví dụ đẹp không thoã mãn, ví dụ hiểm hóc cũng không thoã mãn. Để có một cách tiếp cận như công trình này, tôi cần phải chứng minh một phát biểu loại sau đây. Phát biểu 1. Mỗi không gian Banach vô hạn chiều có một không gian con vô hạn chiều thoả mãn mọi không gian con của nó là đẹp hay mọi không gian con của nó là hiểm hóc. Bây giờ chúng ta đã thấy hơi hướng của lý thuyết Ramsay: Chúng ta có thể xem các không gian con đẹp là “đỏ” và các không gian con hiểm hóc là “xanh”. 7. Một định lý yếu kiểu Ramsey cho các không gian con Mặc dầu vậy, có một điểm khác biệt quan trọng giữa phát biểu 1 và các phát biểu ban đầu của chúng ta về lý thuyết Ramsey, đó là đối tượng mà chúng ta tô màu là những không gian vô hạn chiều chứ không phải là là các điểm. (Tuy nhiên tôi muốn chỉ ra rằng trong định lý Ramsey chúng ta tô màu các cạnh chứ không phải các điểm, do vậy ý tưởng tô màu một cái gì đó không phải là điểm không phải là hoàn toàn mới) Chúng ta làm sao để đưa chúng vào chương trình làm việc của chúng ta? Trên thực tế điều này không khó lắm. Các cấu trúc mà chúng ta tô màu có thể xem như “cấu trúc của mọi không gian con của một không gian đã cho”. Nếu chúng ta lấy một không gian con tuỳ ý thì mọi không gian con của nó tạo thành một cấu trúc tương tự như cấu trúc ban đầu, do vậy chúng ta có thể suy tính chứng minh một định lý kiểu Ramsey. Điều tốt nhất mà chúng ta hy vọng chứng minh sẽ là một cái gì đó như sau: Nếu bạn tô màu xanh hay đỏ tất cả các không gian con của một không gian thì ắt phải có một không gian con mà mọi không gian con của nó được tô bằng cùng một màu. Tuy nhiên, không ngạc nhiên lắm khi điều này hoá ra quá viển vông để hy vọng do những nguyên nhân buồn tẻ và lý thú. Lý do buồn tẻ tương tự như lý do chúng ta không thể tô các điểm của của một mặt cầu vô hạn chiều và hy vọng là có thể tìm được một mặt cầu con đơn sắc vô hạn chiều. Lý do lý thú là ngay cả khi chúng ta phát biểu lại bài toán đi tìm những không gian con mà chúng gần như tất cả có cùng một màu (chữ “gần như” hiểu theo một nghĩa thích hợp), các kết quả của Odell và Schlumprecht, đề cập tới việc tô màu các điểm, có thể được dùng để chỉ ra một cách khá dễ dàng rằng chúng ta không nhất thiết tìm được chúng. Có vẻ như chúng ta đã tới đường cùng, nhưng trên thực tế chưa tới mức như vậy, lý do là tôi nghĩ rằng mình không cần đến toàn bộ sức mạnh của định lý Ramsey. Thay vào đó, tôi có thể giải quyết vấn đề với một “định lý Ramsey yếu” mà tôi sẽ trình bày ngắn gọn sau đây. Để bắt đầu, tôi cần phải giới thiệu một trò chơi có vẻ kỳ lạ. Giả sử ta có một tập hợp P các dãy có dạng .a1; a2; a3; : : :/ trong đó tất cả các ailà các điểm của không gian Banach. (Tại chỗ 77 Tạp chí Epsilon, Số 13, 02/2017 này và nhiều chỗ trước đó, điều quan trọng là cần phải nhớ đối tượng mà tôi nói tới là gì. Điều này hơi khó hiểu: Như tôi vừa mới nói, P là tập hợp các dãy, nhưng các số hạng trong mỗi dãy lại là các điểm trong không gian Banach, và mỗi điểm là một dãy số thực, đó là tại sao tôi viết chúng bằng chữ in đậm. Vậy P là tập hợp các dãy của các dãy số thực. Người ta có thể tiến xa hơn khi nói rằng mỗi số thực được biểu diễn bằng số thập phân vô hạn, do vậy P là tập hợp của những dãy của những dãy của những dãy số từ 0 đến 9: (Nhưng có vẻ như dễ hơn khi xem các số hạng an như là các điểm của không gian vô hạn chiều và quên rằng chúng có toạ độ). Cho tập hợp P; các người chơi A và B, và trò chơi như sau. Người chơi A chọn không gian con S1: Kế đó người chơi B chọn điểm a1 trong S1: Người chơi A giờ đây chọn không gian con S2 (không phải là không gian con của S1) và người chơi B chọn điểm a2 trong S2: Và cứ thế tiếp tục. Kết thúc quá trình vô hạn này, người chơi B chọn được một dãy .a1; a2; a3; : : :/: Nếu như dãy này là một trong các dãy của P thì B thắng, ngược lại A thắng. Rõ ràng là ai thắng trong trò chơi này phụ thuộc rất nhiều vào P: Chẳng hạn như nếu có một không gian con S sao cho không thể tìm các điểm an trong S tạo thành dãy .a1; a2; a3; : : :/ trong P thì A sẽ thắng một cách dễ dàng bằng cách nước đi nào cũng chọn S, nhưng nếu P chứa hầu hết các dãy thì B cần có một chiến lược chơi để thắng. Ở đây định lý Ramsey yếu hoá ra là đủ để chứng minh một phiên bản phù hợp chính xác của phát biểu 1 và do vậy trả lời câu hỏi của Banach (bài toán 6). Tôi đã đơn giản hoá phát biểu một chút. Trước khi tôi đưa ra chính phát biểu, chúng ta hãy tiến hành định nghĩa sau. Nếu S là một không gian con, hạn chế của trò chơi trên S là trò chơi mà tất cả các không gian con S1; S2; : : : chọn bởi A phải là không gian con của S (và do vậy mọi điểm chọn bởi B phải là điểm trong S). Định lý 5. Với mỗi tập hợp P bao gồm các dãy trong không gian Banach, tồn tại một không gian con S sao cho hoặc là B có một chiến lược chiến thắng với hạn chế của trò chơi trên S hay là không có dãy nào trong P được tạo thành từ các điểm của S: Để hiểu tại sao người ta gọi nó là định lý Ramsey yếu, chúng ta hãy tô màu đỏ một dãy nếu như nó thuộc về P và tô màu xanh nếu ngược lại. Khi đó định lý nói rằng chúng ta có thể tìm được một không gian con S thế nào cho hoặc là tất cả các dãy tạo thành từ các điểm của S là xanh, hoặc là có rất nhiều dãy đỏ tạo thành từ các điểm trong S đến mức nếu trò chơi giới hạn trên S thì B có một chiến lược chiến thắng để sinh ra các dãy đỏ. Nói cách khác, chúng ta đã thay “mọi dãy trong S đều màu đỏ” bằng “trong S có nhiều dãy màu đỏ đến mức B có một chiến lược chiến thắng để sinh ra chúng”. Đó là một cách tạo thành phát biểu và chúng ta thấy rằng nó vừa đủ cho mục đích của chúng ta, nhưng chứng minh nó lại là một chuyện khác. Điều này cho tôi thấy một điểm khác nhau giữa các bài toán IMO và các bài toán nghiên cứu, đó là chiến lược giải quyết vấn đề sau đây có vai trò chủ đạo trong các bài toán nghiên cứu hơn là các bài toán IMO. Chiến lược 4. Nếu bạn cố gắng chứng minh một phát biểu toán học, bạn hãy tìm kiếm một phát biểu tương tự đã được chứng minh rồi và cố gắng sửa đổi phép chứng minh một cách thích hợp. Tôi không dám nói rằng điều này luôn luôn áp dụng được trong nghiên cứu hay là không bao giờ dùng được trong một bài toán IMO, nhưng đối với toán IMO thông thường phải bắt đầu từ con số không. 78 Tạp chí Epsilon, Số 13, 02/2017 Quay trở lại với định lý Ramsey yếu, hoá ra là nó giống với định lý Ramsey vô hạn được tìm ra bởi Galvin và Prikry. Chúng giống nhau đến mức tôi có thể sửa đổi lý luận và chứng minh cái tôi cần. Và may mắn thay, tôi có tham dự khoá học tại Cambridge vài năm trước đây trong đó Bela Bollob đã giảng định lý của Galvin và Prikry. 8. Kết luận Tôi không có gì để nói nhiều trong phần kết luận mà tôi chưa đề cập. Mặc dù vậy, có một điểm đáng chú ý. Nếu bạn là một độc giả từng tham dự IMO, có vẻ như tài giải toán của bạn đã phát triển mà không cần bạn phải làm gì: Một vài người chỉ đơn giản là giỏi toán. Nhưng nếu bạn có tham vọng trở thành một nhà nghiên cứu toán học thì sớm hay muộn bạn cũng phải lưu tâm đến hai nguyên tắc sau. Nguyên tắc 1. Nếu bạn có thể giải một bài toán nghiên cứu trong một vài giờ thì bài toán đó có thể là không thú vị lắm. Nguyên tắc 2. Thành công trong nghiên cứu toán học phụ thuộc nhiều vào sự nỗ lực làm việc. Điều này là rõ ràng từ chính những ví dụ mà tôi đã đưa ra. Khi dự định giải một bài toán nghiên cứu thú vị và sáng tạo, người ta thường chỉ có một ý niệm mơ hồ sẽ bắt đầu từ đâu. Từ một ý niệm mơ hồ đến một kế hoạch tấn công rõ ràng cần thời gian, đặc biệt là hầu hết kế hoạch tấn công rõ ràng sẽ bị bỏ qua vì chúng đơn giản không áp dụng được. Nhưng bạn cũng cần sẵn sàng để ý đến những mối liên hệ và các điểm tương đồng với những bài toán khác và phải phát triễn những kỹ thuật và bộ đồ nghề của mình, một chút kiến thức toán học, ... Đằng sau bất cứ nghiên cứu thành công nào, nhà toán học phải bỏ ra hàng ngàn giờ suy tư về toán học, chỉ có vài giờ trong số đó trực tiếp dẫn đến phát minh. Thật lạ là mỗi người đều chuẩn bị cho những giờ như vậy theo một cách nào đó. Có lẽ là vì một nguyên tắc khác như sau. Nguyên tắc 3. Nếu bạn thực sự quan tâm đến toán học thì việc làm toán nặng nhọc không giống như việc nhà: Đó là cái mà bạn muốn làm. Đọc thêm 1. Ron Graham, Bruce Rothschild, and Joel Spencer, Ramsey Theory. Wiley-Interscience Series in Discrete Mathematics and Optimization. Wiley, New York (1990). Quyển sách này chứa nhiều tài liệu về định lý Ramsey, định lý Van der Waerden, định lý Hindman, và nhiều kết quả khác. Đây là điểm khởi đầu nên có cho bất cứ ai quan tâm đến chủ đề này. 2. B’ela Bollob’as, Linear Analysis: An Introductory Course, second edition. Cambridge University Press, Cambridge (1999), xii+240 pp. Không gian Banach thuộc về một nhánh của Toán học gọi là Giải tích tuyến tính. Đây là sách nhập môn cho lãnh vực này, rất hấp dẫn cho những thí sinh IMO (Hãy xem qua những bài tập đánh dấu hai sao, ...) 79 Tạp chí Epsilon, Số 13, 02/2017 3. Edward Odell and Thomas Schlumprecht, The distortion problem. Acta Mathematica 173, 259–281 (1994). Bài báo này có ví dụ của Odell và Schlumprecht được đề cập trong phần 5. 4. W. Timothy Gowers, An infinite Ramsey theorem and some Banach-space dichotomies. Annals of Mathematics (2) 156, 797–833 (2002). Bài báo này có kết quả của tôi về trò chơi vô hạn và những hệ quả của nó. Hai bài báo trên đòi hỏi bạn phải biết về không gian Banach và do vậy sẽ là rất khó cho những độc giải chưa học qua đại học. Một khả năng khác tốt hơn chút đỉnh là bài báo sau của tôi viết về mối liên hệ giữa lý thuyết Ramsey và không gian Banach. 5. W. Timothy Gowers, Ramsey methods in Banach spaces. In: William B. Johnson and Joram Lindenstrauss (editors), Handbook of the Geometry of Banach Spaces, volume 2, pp. 1071–1097. North-Holland, Amsterdam (2003). Nếu bạn đọc cả quyển một thì chương đầu tiên là các khái niệm cơ bản của chủ đề, nó có thể bổ ích, nó là quyển này. 6. William B. Johnson and Joram Lindenstrauss, Basic concepts in the geometry of Banach spaces. In: William B. Johnson and Joram Lindenstrauss (editors), Handbook of the Ge ometry of Banach Spaces, volume 1, pp. 1–84. North-Holland, Amsterdam (2001). Bài viết được dịch từ nguyên bản tiếng Anh, How do IMO Problems Compare with Research Problems? Ramsey Theory as a Case Study của tác giả W.Timothy Gowers. Trích từ cuốn sách An Invitation to Mathematics – From competitions to research do Schleicher và Lackmann làm chủ biên. W. Timothy Gowers Department of Pure Mathematics and Mathematical Statistics, University of Cambridge, Cambridge CB3 0WB, UK. e-mail: [email protected] D. Schleicher, M. Lackmann (eds.), An Invitation to Mathematics, DOI 10.1007/978-3-642- 19533-4 5, c Springer-Verlag Berlin Heidelberg 2011: 80