🔙 Quay lại trang tải sách pdf ebook Tạp Chí Epsilon Số 8
Ebooks
Nhóm Zalo
CƠ SỞ
GRÖBNER LÀ GÌ?
Bernd Sturmfels
LÊ VĂN THIÊM
CON NGƯỜI VÀ SỰ NGHIỆP
Hà Huy Khoái
EUCLID VÀ
CƠ SỞ CỦA HÌNH HỌC
Ngô Bảo Châu, Richard Fitzpatrick
TẬP TRÁNH TỔNG
TRONG NHÓM
Terence Tao
VỀ HẰNG SỐ LIÊN THÔNG
TRÊN LƯỚI TỔ ONG
Huỳnh Công Bằng
VÀ CÁC CHUYÊN MỤC KHÁC
No. 8
“Nếu hai vật thể có đặc số Euler khác nhau, thì chúng không thể cái này biến thành cái kia sau một phép biến đổi thuận nghịch liên tục (kiểu như co dãn cao su). Người ta nói hai vật thể đó không cùng kiểu tôpô.” RỘNG HẸP NHỎ TO VỪA VẶN CẢ
(GIỚI THIỆU TÔPÔ HỌC)
Nguyễn Hữu Việt Hưng
“Cơ sở của hình học được coi là một trong những quyển sách có ảnh hưởng nhất tới sự phát triển của văn minh nhân loại.”
EUCLID VÀ CƠ SỞ CỦA HÌNH HỌC
Ngô Bảo Châu, Richard Fitzpatrick
CHỦ BIÊN:
Trần Nam Dũng
BIÊN TẬP VIÊN:
Võ Quốc Bá Cẩn
Ngô Quang Dương
Trần Quang Hùng
Nguyễn Văn Huyện
Nguyễn Tiến Lâm
Lê Phúc Lữ
Nguyễn Tất Thu
Đặng Nguyễn Đức Tiến
13
04
No. 8
LỜI NGỎ CHO EPSILON SỐ 8
Ban Biên tập Epsilon
Epsilon có gì trong số 8 này? Ban biên tập xin mời bạn đọc hãy lướt qua phần giới thiệu của chúng tôi.
Mảng lịch sử toán học có bài của GS Hà Huy Khoái viết về thân thế và sự nghiệp của GS Lê Văn Thiêm mà chúng ta vừa kỷ niệm 98 năm ngày sinh tháng 3 vừa qua. Cũng mảng lịch sử toán học nhưng có nội dung chính là giới thiệu về tô-pô có bài viết rất hóm hỉnh, dễ hiểu nhưng cũng rất sâu sắc của GS Nguyễn Hữu Việt Hưng với tựa đề "Rộng hẹp nhỏ to vừa vặn cả". Các bạn sẽ thấy bất ngờ khi thấy rằng hóa ra cùng với Leonard Euler vĩ đại, có một nhà thơ Việt Nam cũng đã tìm ra ý tưởng táo bạo của tô-pô (có dẫn trong tựa đề). Cùng chủ đề giới thiệu về toán cao cấp có bài của Matt Baker về định lý hôn nhân, bài về cơ sở Grobner của Bernd Sturmfels. Epsilon số 8 cũng giới thiệu bài viết của Terence Tao trên blog của anh giới thiệu về bài báo của anh và Vũ Hà Văn về tập tránh tổng (Sum-free sets). Mục điểm sách sẽ có bài của GS Ngô Bảo Châu và Richard Fitzpatrick giới thiệu về cuốn Euclid và Cơ sở của hình học. Mục vấn các vấn đề cổ điển và hiện đại sẽ có đề thi Tú tài Pháp do GS Nguyễn Tiến Dũng giới thiệu.
Bên cạnh đó là các chuyên mục quen thuộc về toán sơ cấp, lời giải các số trước, các bài viết của các tác giả "ruột" của Epsilon, bài toán hay, lời giải đẹp, toán giải trí ...
Chúng tôi đặc biệt muốn nhấn mạnh đến sự ủng hộ của các tác giả dành cho Epsilon. Điều này nói lên một tinh thần "Khi chúng ta đóng góp vì cộng động, cộng đồng sẽ vì ta". GS Hà Huy Khoái đã đích thân gửi bài đến cho Ban biên tập. GS Nguyễn Hữu Việt Hưng, khi chúng tôi xin bài cũng đã vui vẻ gửi bản gốc để chúng tôi tiện biên tập chỉ với lời nhắn "với điều kiện các cậu không được sửa, dù chỉ một chữ". Còn Terence Tao thì trả lời ngắn gọn "This is fine with me. Best, Terry". Các tác giả "ruột" như Ngô Quang Hưng, Lý Ngọc Tuệ thì dù bận bịu vẫn luôn gắng dành thời gian viết bài cho chúng tôi. Mà các anh thì viết quá chuẩn, BBT chỉ cần ráp vào là xong. Các bạn trẻ cũng rất hăng hái viết bài (số này sẽ có 3 bài của các bạn học sinh là Hoàng Cao Phong, Nguyễn Trần Hữu Thịnh và Đỗ Xuân Anh), sẵn sàng nhận dịch bài khi được nhờ (số này sẽ có bản dịch của bạn Nguyễn Vũ Anh).
Mà không chỉ có các bạn trẻ sung. Lứa trung niên cũng sung lắm. Số này sẽ có bài của Trịnh Đào Chiến và anh cùng Trần Minh Hiền hứa sẽ viết 1 bài về định lý Cauchy Davenport cho số 6. Lão ngoan đồng Nguyễn Vũ Duy Linh cũng hăng hái dịch bài về cơ sở Grobner của Sturmfels.
Ban biên tập cảm ơn sự ủng hộ của các tác giả và sự đón nhận nồng nhiệt của các độc giả. Hãy tiếp tục chung tay sát cánh cùng chúng tôi trên con đường đầy gian nan phía trước.
Đi nhiều người, ta sẽ đi rất xa.
3
MỤC LỤC
Ban Biên tập Epsilon
Lời ngỏ cho Epsilon số 8 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
Lý Ngọc Tuệ
Xấp xỉ Diophantine trên Rn- Véc tơ xấp xỉ kém và Trò chơi siêu phẳng tuyệt đối . . . . 7
Bernd Sturmfels
Cơ sơ Grobner là gì? ¨ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
Terence Tao
Tập tránh tổng trong nhóm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
Matt Baker
Toán học của hôn nhân . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
Huỳnh Công Bằng
Về hằng số liên thông trên lưới tổ ong . . . . . . . . . . . . . . . . . . . . . . . . . . . 33
Nguyễn Hữu Việt Hưng
Rộng hẹp nhỏ to vừa vặn cả (Giới thiệu Tôpô học) . . . . . . . . . . . . . . . . . . . . . 47
Đặng Nguyễn Đức Tiến
Các bài toán đoán bài . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55
Nguyễn Trần Hữu Thịnh
Xung quanh định lý Brokard . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61
Đỗ Xuân Anh
Tứ giác ngoại tiếp đường tròn . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 75
Trần Quang Hùng, Nguyễn Tiến Dũng
Một số ứng dụng của cực và đối cực . . . . . . . . . . . . . . . . . . . . . . . . . . . . 93 4
Tạp chí Epsilon, Số 08, 04/2016
Nguyễn Tiến Lâm, Ngô Quang Dương
Tính chất hình học của đường cong bậc ba . . . . . . . . . . . . . . . . . . . . . . . . . 119
Hoàng Cao Phong
Biểu diễn số nguyên dương dưới dạng tổng các số chính phương . . . . . . . . . . . . . 125
Trịnh Đào Chiến
Một số dạng toán về bất phương trình hàm . . . . . . . . . . . . . . . . . . . . . . . . . 133
Trần Nam Dũng
Bài toán hay lời giải đẹp . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 151
Ngô Bảo Châu, Richard Fitzpatrick
Euclid và Cơ sở của hình học . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 155
Hà Huy Khoái
Lê Văn Thiêm: Con người và sự nghiệp . . . . . . . . . . . . . . . . . . . . . . . . . . 161
Trần Nam Dũng
Các vấn đề cổ điển và hiện đại . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 173
Ban Biên tập Epsilon
Về kỳ thi Việt Nam TST 2016 và danh sách đội tuyển Việt Nam . . . . . . . . . . . . . . 189 5
Tạp chí Epsilon, Số 08, 04/2016
6
XẤP XỈ DIOPHANTINE TRÊN Rn- VÉC TƠ XẤP XỈ KÉM VÀ TRÒ CHƠI SIÊU PHẲNG TUYỆT ĐỐI
Lý Ngọc Tuệ
(Đại học Brandeis, Massachusetts, Mỹ)
1. Giới thiệu
Trong phần 1 và phần 2 của loạt bài về xấp xỉ Diophantine [16, 17] chúng ta đã chứng minh Định lý Dirichlet trên Rnnhư sau:
Định lý 1 (Dirichlet). Với mọi véc tơ vô tỉ xE 2 Rn X Qn, tồn tại vô số véc tơ hữu tỉ pEqD
p1
q; :::;pn q
2 Qnvới pE 2 Znvà q 2 Z, q ¤ 0 sao cho:
xE pEq<1
jqj1C 1n:
Tổng quát hơn một tí, chúng ta gọi một hàm số liên tục không tăng W R>0 ! R>0 là một hàm xấp xỉ, và gọi một véc tơ xE 2 Rnlà -xấp xỉ được1nếu như tồn tại vô số pE 2 Zn, q 2 Z, q ¤ 0
sao cho:
xE pEq .jqj/
jqj:
Tập các véc tơ -xấp xỉ được trên Rnsẽ được ký hiệu là WAn. /. Nếu như ta sử dụng ký hiệu: ˛ W k 7! k˛, thì Định lý Dirichlet có thể được phát biểu lại thành:
WAn
1
n
D Rn:
Hàm số sẽ được gọi là một hàm Dirichlet (trên Rn) nếu như WAn. / D Rn. Câu hỏi về hàm số Dirichlet tối ưu cho Rnđược trả lời một phần bởi Định luật 0-1 sau của Khintchine:
Định lý 2 (Khintchine 1926). Ký hiệu là độ đo Lebesgue trên Rn:
(i) Nếu như chuỗi X1 kD1
(ii) Nếu như chuỗi X1 kD1
1 -approximable
.k/nhội tụ thì .WAn. // D 0. .k/nphân kỳ thì .Rn X WAn. // D 0.
7
Với > 0 bất kỳ, theo Định lý 2,
WA
1
nC
Tạp chí Epsilon, Số 08, 04/2016
D 0. Vì vậy, 1
nC không phải là hàm
Dirichlet, và số mũ
1 C1n trong Định lý 1 là tối ưu. Tuy nhiên, với những hàm số tiến về 0
nhanh hơn một tí như
k 7! k1n .log k/1n hay k 7! k1n .log log k/1 , Định lý 2 không thể
cho ta biết được rằng đấy có phải là hàm Dirichlet hay không. Thật ra những hàm này không thể là hàm Dirichlet được, hay tổng quát hơn nữa, nếu như hàm số thỏa mãn:
lim
k!1
k1n .k/ D 0;
thì không phải là một hàm Dirichlet trên Rn: WAn. / ¤ Rn.
Điều này có thể được chứng minh bằng cách chỉ ra sự tồn tại của các véc tơ xấp xỉ kém được định nghĩa như sau: xE 2 Rnđược gọi là xấp xỉ kém nếu như tồn tại một hằng số c > 0 (tùy thuộc vào xE) sao cho với mọi pE 2 Zn, q 2 Z, q ¤ 0:
xE pEq>c
jqj1C 1n: (1.1)
Tập các véc tơ xấp xỉ kém trên Rnsẽ được ký hiệu bởi BAn.
Khi n D 1, các số xấp xỉ kém tương ứng với các liên phân số đơn bị chặn, vì thế BA1 không rỗng. Theo như Định lý của Lagrange, rằng một số thực ˛ là một số đại số bậc 2 khi và chỉ khi mở rộng liên phân số của ˛ là tuần hoàn, mọi số thực đại số bậc 2 vô tỉ đều xấp xỉ kém. Tuy không có công cụ liên phân số khi n 2, chúng ta có thể chứng minh được trực tiếp mở rộng của quan sát trên cho Rnnhư sau:
Định lý 3. Nếu như f1; ˛1; :::; ˛ng là một cơ sở của một trường số đại số thực2bậc .n C 1/, thì ˛E D .˛1; :::; ˛n/ 2 BAn.
Bài tập 4. Chứng minh Định lý 3.
Ví dụ trên chỉ ra rằng có ít nhất vô hạn đếm được các véc tơ xấp xỉ kém trên Rn. Mãi đến năm 1954, Davenport [5] chứng minh rằng BA2 là một tập không đếm được, và một năm sau đấy, Cassels [4] chứng minh rằng BAn là không đếm được với n bất kỳ.
Vậy các tập BAn lớn như thế nào? Phân tích BAn ra thành như sau:
BAn D[ c>0
Rn X WA c 1 n
;
và áp dụng Định lý 2, ta có được.
D[1 kD1
Rn X WA k1 1 n
.BAn/ D 0:
Nói một cách khác, theo độ đo Lebesgue thì BAn là một tập nhỏ không đáng kể. Hơn thế nữa, cách phân tích như trên còn chỉ ra rằng BAn thuộc phạm trù thứ nhất theo Baire, một hội đếm được của các tập không đâu trù mật.
Một trong những công cụ phổ biến để đo kích cỡ các tập nhỏ như vậy là chiều Hausdorff, ký hiệu là dim (xem thêm chi tiết ở 2). Sử dụng cách biểu diễn các số xấp xỉ kém dưới dạng liên phân số bị chặn, Jarník [11] chứng minh rằng tập các số xấp xỉ kém BA1 có chiều Hausdorff bằng 1. Đến 1966, Schmidt [21] mở rộng kết quả này ra cho các véc tơ xấp xỉ kém:
2real algebraic number field of degree .n C 1/
8
Tạp chí Epsilon, Số 08, 04/2016
Định lý 5 (Schmidt 1966). dim BAn D n.
Schmidt chứng minh kết quả này dựa vào một phương pháp hoàn toàn mới mà ông nghĩ ra: sử dụng một trò chơi vô hạn với thông tin hoàn hảo mà sau này gọi là trò chơi Schmidt (xem [19, Phần 4]). Áp dụng trò chơi này, Schmidt chứng minh rằng nếu như yE1; yE2; ::: là một dãy các véc tơ trên Rn, thì giao của các tịnh tiến của BAn bởi yE1; yE2; ::: vẫn có chiều Hausdorff bằng n:
dimH
\1
kD1
BAn C Eyk !D n:
Tổng quát hơn, Schmidt đã chứng minh rằng:
Định lý 6 (Schmidt 1966). Gọi U là một tập mở bất kỳ trên Rn, ffiW U ! Vi g1
đếm được các hàm 3từ U vào các tập mở Vi Rn. \1
!
iD1là một họ
dim
iD1
.fi/1.BAn/
D n:
Dựa trên ý tưởng của Schmidt, McMullen [20] giới thiệu một biến thể của trò chơi Schmidt, gọi là trò chơi tuyệt đối4, và chứng minh rằng tập BA1 là một tập thắng cuộc đối với trò chơi này (thắng cuộc tuyệt đối5). Tuy nhiên, khi n 2, BAn không phải là một tập thắng cuộc tuyệt đối. Vì thế Broderick, Fishman, Kleinbock, Reich, và Weiss [1] đã mở rộng ý tưởng của McMullen ra và giới thiệu trò chơi siêu phẳng tuyệt đối, trong đấy tập thắng cuộc được gọi là thắng cuộc siêu phẳng tuyệt đối6, viết tắt là HAW. Áp dụng trò chơi này, BFKRW đã làm mạnh hơn Định lý 6 của Schmidt như sau:
Định lý 7 (BFKRW 2012). Gọi U là một tập mở bất kỳ trên Rn, ffiW U ! Vi g1
đếm được các vi phôi7 C1từ U vào các tập mở Vi Rn.
iD1là một họ
dim
\1 iD1
.fi/1.BAn/
!
D n:
Định lý 5 và Định lý 6 đều là hệ quả của Định lý sau:
Định lý 8 (BFKRW 2012). BAn là một tập thắng cuộc siêu phẳng tuyệt đối.
Trong phần còn lại của bài này, chúng tôi sẽ giới thiệu chi tiết hơn về chiều Hausdorff, về trò chơi siêu phẳng tuyệt đối, và chứng minh Định lý 8.
2. Chiều Hausdorff
Một số tài liệu tham khảo cho chiều và độ đo Hausdorff: Fractal Geometry: Mathematical Foundations and Applications [6] và The Geometry of Fractal Sets [7] của K. J. Falconer.
3uniformly bi-Lipschitz
4absolute game
5absolute winning
6hyperplane absolute winning
7C1diffeomorphism
9
Tạp chí Epsilon, Số 08, 04/2016
Với mỗi tập con không rỗng U Rn, đường kính của U được định nghĩa là khoảng cách lớn nhất giữa 2 điểm bất kỳ trong U:
diam U WD sup˚xE Ey W Ex; yE 2 U :
Nếu như fUi g là một họ đếm được các tập có đường kính không quá ı và E [1
Ui, ta sẽ gọi
fUi g là một ı-phủ8của E.
iD1
Với mỗi tập E Rn, và với mỗi s; ı > 0, độ đo ngoài .ı; s/ Hausdorff của E được định nghĩa
là:
H sı.E/ WD inf
(X1 iD1
)
.diam Ui/sW fUi g là một ı-phủ của E :
Bài tập 9. Chứng minh rằng H sılà một độ đo ngoài, nghĩa là thỏa mãn 3 tính chất sau: (i) H sı.;/ D 0.
(ii) A B H) H sı.A/ H sı.B/.
(iii) H sı
[1 iD1
!
Ai
X1 iD1
H sı.Ai/.
Khi ı giảm dần về 0, lớp các ı-phủ của E nhỏ đi, vậy nên H sı.E/ tăng dần và giới hạn của H sı.E/ khi ı ! 0 tồn tại (có thể là C1). Ta gọi giới hạn này là độ đo ngoài Hausdorff với chiều s9của E:
H s.E/ WD lim ı&0
H sı.E/:
Theo lý thuyết độ đo tổng quát, khi ta giới hạn vào các tập H s-đo được, H strở thành độ đo. Hơn thế nữa, các tập Borel trên Rnđều là H s-đo được với mọi s > 0.
Độ đo Hausdorff có một số tính chất như sau:
Bổ đề 10. Cho E Rn.
(i) Khi s D n, độ đo Hausdorff với chiều n tương đương với độ đo Lebesgue trên Rn: Tồn tại một hằng số c > 0 sao cho với mọi tập Borel E,
H n.E/ D c .E/:
(ii) Với ˛ > 0, ký hiệu ˛E D˚˛xE W Ex 2 E . Độ đo Hausdorff với chiều s của ˛E thỏa mãn: H s.˛E/ D ˛sH s.E/:
(iii) Tổng quát hơn, nếu như f W E ! Rm là một hàm sao cho tồn tại hằng số c; ˛ > 0 để với
mọi x; E yE 2 E: thì với mọi s > 0:
f .x/ E f .y/E cxE Ey˛;
H s=˛.f .E// cs=˛H s.E/:
8ı-cover
9s-dimensional Hausdorff outer measure
10
Tạp chí Epsilon, Số 08, 04/2016
(iv) Nếu như H s.E/ < 1, thì với mọi t > s, H t.E/ D 0.
(v) Nếu như H s.E/ > 0, thì với mọi 0 < t < s, H t.E/ D 1.
Bài tập 11. Chứng minh Bổ đề 10.
Tính chất (iv) và (v) trong Bổ đề 10 cho thấy có 1 thời điểm s D s0 mà H s.E/ nhảy từ 1 xuống 0, gọi là chiều Hausdorff của E:
dimH .E/ WD supfs > 0 W H s.E/ D 1g D inffs > 0 W H s.E/ D 0g:
Một số tính chất cơ bản của chiều Hausdorff như sau:
Bổ đề 12. Cho E Rn.
(i) Nếu 0 < H s.E/ < 1, thì dimH .E/ D s.
(ii) Nếu E là một tập mở của Rnthì dimH .E/ D n.
(iii) Nếu E F thì dimH .E/ dimH .F /.
(iv) Nếu E là một đa tạp m-chiều trong Rnthì dimH .E/ D m.
(v) Với mọi dãy fEi g:
dimH
Bài tập 13. Chứng minh Bổ đề 12.
[1 iD1
Ei
!
D sup
i
dimH .Ei/:
Chúng ta sẽ thấy chiều Hausdorff là một công cụ quan trọng để mô tả các tập có độ đo Lebesgue không đáng kể thông qua một ví dụ nổi tiếng về tập Cantor.
Ví dụ 14. Tập Cantor10 C có thể được định nghĩa theo các bước như sau. Đặt C0 D Œ0; 1. Ở
bước thứ k 1, nếu như tập Ck D[ i
Ik;i là hợp của các đoạn không giao nhau từng cặp, thì
CkC1 sẽ được bằng cách bỏ đi các đoạn mở ở giữa các Ik;i có độ dài dúng bằng 1/3 độ dài của Ik;i. Cụ thể hơn, ta sẽ có được:
C0 D Œ0; 1
C1 D
C2 D :::
0;13 [ 23; 1
0;19 [ 29;13 [ 23;78 [ 89; 1
Tập Cantor C là giao của tất cả các tập Ck. C D\1
kD0
10Cantor middle third set
11
Ck:
Tạp chí Epsilon, Số 08, 04/2016
0 1
C0
0 1=3 2=3 1
C1
0 1=9 2=9 1=3 2=3 7=9 8=9 1
C2
Có thể thấy được rằng Ck bao gồm 2kcác đoạn thẳng có độ dài 3k, và C0 C1 C2 C:
Với mọi k 0:
.C/ .Ck/ D
2 3
k :
Từ đó ta suy ra được rằng C có độ dài (độ đo Lebesgue trên R) bằng 0.
Vì Ck là các tập compact, C cũng là một tập compact và không rỗng. Ta có thể mô tả các phần tử của C như sau. Với mỗi số thực 0 x 1, viết x bằng hệ cơ số 3:
ai3i; a1; a2; ::: 2 f0; 1; 2g:
Khi đấy:
x D .0:a1a2:::/3 DX1 iD1
x 2 C () a1; a2; ::: 2 f0; 2g:
Chúng ta sẽ chứng minh rằng với s Dlog 2
log 2
log 3.
Đặt Ck D
log 3, H s.C/ D 1. Vì vậy tập C có chiều Hausdorff bằng
2[k
Ik;i, trong đấy Ik;i là các đoạn đóng có độ dài 3k, với mỗi ı > 0, chọn k đủ lớn iD1
sao cho 3k ı. Khi đấy fIk;i g là một ı-phủ của C, và ta có được:
H sı.C/
Lấy giới hạn khi ı & 0:
2Xk iD1
.diam.Ik;i//s D
2Xk iD1
3k
log 2
log 3D 1:
H s.C/ D lim ı&0
H sı.C/ 1:
Để chứng minh chiều ngược lại, gọi fU˛g là một phủ bất kỳ của C. Không mất tính tổng quát, chúng ta có thể giả sử rằng U˛ là các đoạn thẳng đóng. Vì C là một tập compact, ta có thể tìm
được một số hữu hạn các đoạn ˚Uj 1 j mphủ C.
Gọi k là số nguyên dương nhỏ nhất sao cho với mọi 1 i 2kvà với mọi 1 j m, nếu như phần trong của Ik;i giao với Uj thì Ik;i Uj . Gọi Ij là tập các đoạn Ik;i nằm trong Uj : Ij WD ˚Ik;i W Ik;i Uj ;
12
Tạp chí Epsilon, Số 08, 04/2016
và U0jlà đoạn đóng nhỏ nhất chứa mọi đoạn Ik;i trong Ij . Ta có thể dễ dàng kiểm tra được rằng ˚U0j 1 j mcũng là một phủ của C, và:
Xm
jD1
diam Uj s Xm
jD1
diam U0j s:
Nếu như U0jchỉ chứa 1 đoạn Ik;i thì hiển nhiên: U0j D Ik;i. Còn khi:
2l < #Ij 2lC1;
ta có thể tìm được một đoạn đóng K U0jsao cho:
(i) Ko \ Ck D ;,
(ii) diam K 13diam U0j,
(iii) U0j X Kobao gồm 2 đoạn đóng J và J0, mỗi đoạn chứa nhiều nhất 2lđoạn con Ik;i trong Ij .
Từ đó ta có được:
diam U0j s Ddiam J C diam K C diam J0 s
3
diam J C diam J0 s
2
2diam J C12diam J0 s s Dlog 2
D 2
1 1
log 3
2
2.diam J /s C12diam J0 s .0 < s < 1/
D .diam J /s Cdiam J0 s
Quy nạp theo l, ta có được:
.diam Ik;i/s:
Vì ˚U0j là một phủ của C:
diam U0j s X Ik;i2Ij
X1 iD1
.diam.Ui//s Xm
jD1
diam Uij s 2Xk iD1
.diam Ik;i/s D 1:
Vậy H s.C/ D 1 và dimH .C/ Dlog 2 log 3.
13
Tạp chí Epsilon, Số 08, 04/2016
3. Trò chơi siêu phẳng tuyệt đối
Trong phần này, chúng ta sẽ ký hiệu B.x; r/ E là ‘quả bóng’11 đóng trong Rnvới tâm xE và bán
kính r:
B.x; r/ E WD ˚yE 2 RnWxE Ey r :
Một siêu phẳng12 L trong Rnlà một tập hợp các nghiệm của một hàm tuyến tính n ẩn khác 0. Khoảng cách từ một điểm xE đến L được định nghĩa là:
distx; E L WD inf˚xE Ey W Ey 2 L :
Tập hợp các điểm có khoảng cách đến L không quá r được gọi là một r-lân cận của L, và ký
hiệu là:
L.r/ WD ˚xE W distx; E L r :
Cho trước một hằng số 0 < ˇ < 13và một tập đối được S Rn, trò chơi ˇ-siêu phẳng tuyệt đối giữa An và Bình diễn ra như sau:
1. An và Bình lần lượt thay phiên nhau đi, và Bình là người đi trước.
2. Đầu tiên Bình chọn một quả bóng bất kỳ B1 D B.xE1; r1/ với bán kính r1 > 0. 3. Ở bước thứ i 1, An chọn si-lân cận của một siêu phẳng Li sao cho 0 < si ˇri. 4. Ở bước thứ i C 1, Bình chọn một quả bóng BiC1 D B.xEiC1; riC1/ sao cho riC1 ˇri và: B.xEiC1; riC1/ B.xEi; ri/ X L.si /
i:
B1
L.s1/
1
An sẽ thắng nếu như:
xE2
r2
S \\1
B2
xE1 r1
B.xEi; ri/ ¤ ;; iD1
11vì chúng ta dùng sup-norm, nên thật ra B.x; r/ E là hình hộp vuông trong Rn 12hyperplane
14
Tạp chí Epsilon, Số 08, 04/2016
còn nếu không thì Bình thắng. Tập S được gọi là một tập ˇ-thắng cuộc siêu phẳng tuyệt đối nếu như An có chiến lược để luôn luôn thắng trong trò chơi ˇ-siêu phẳng tuyệt đối (viết tắt là ˇ-HAW) bất kể Bình có đi như thế nào đi nữa. S được gọi là thắng cuộc siêu phẳng tuyệt đối (viết tắt là HAW) nếu như S ˇ-thắng cuộc siêu phẳng tuyệt đối với mọi 0 < ˇ < 13.
Lưu ý 15. Khi n D 1, các ‘siêu phẳng’ L trên R đơn giản là các điểm. Khi đấy, trò chơi siêu phẳng tuyệt đối còn được gọi là trò chơi tuyệt đối được giới thiệu bởi McMullen trong [20].
Lưu ý 16. Trò chơi siêu phẳng tuyệt đối có thể được chơi ở trên một không gian metric tổng quát .X; dist/ mà trong đấy các siêu phẳng L có thể được thay thế bởi các tập đóng cho trước trong X. Trò chơi tổng quát này gọi là trò chơi H-tuyệt đối13 đã được giới thiệu bởi Fishman, Simmons, và Urbanski [9], phát triển và áp dụng trong [14].
Lưu ý 17. Điều kiện ˇ < 1=3 là để dù cho An có chọn như thế nào đi nữa, Bình cũng luôn có lựa chọn hợp lệ cho bước đi tiếp theo. Ta có thể chơi trò chơi siêu phẳng tuyệt đối trên một tập con X Rnvới mọi lựa chọn của Bình đều có tâm nằm trong X nếu như điều kiện sau được thỏa mãn: Tồn tại ; r0 > 0 đủ nhỏ sao cho với mọi quả bóng B.x; r/ E có tâm xE 2 X và bán kính 0 < r < r0 và với mọi siêu phẳng L,
X \
B.x; r/ E X L.r/
¤ ;:
Điều kiện trên đảm bảo khi ˇ đủ nhỏ, trò chơi ˇ-siêu phẳng tuyệt đối trên X sẽ kéo dài vô hạn. Những tập X thỏa mãn điều kiện này sẽ được gọi là -siêu phẳng phân tán14. X sẽ được gọi là siêu phẳng phân tán nếu như tồn tại > 0 sao cho X là -siêu phẳng phân tán. Ví dụ: tập Rnlà 1
3-siêu phẳng phân tán, nhưng một đường thẳng trong không gian 3 chiều R3không phải là một tập siêu phẳng phân tán.
Lưu ý 18. Nếu như X R là một tập siêu phẳng phân tán, ta sẽ chơi trò chơi siêu phẳng tuyệt đối trên X bằng cách bắt Bình phải chọn các quả bóng có tâm nằm trong X. Khi đấy các tập thắng cuộc sẽ được gọi là HAW trên X.
Một số tính chất quan trọng của các tập thắng cuộc trong trò chơi siêu phẳng tuyệt đối như sau: Định lý 19 ([1]). Giả sử như X R là một tập siêu phẳng phân tán.
(i) Nếu S R là một tập HAW thì dimH .S / D n.
(ii) Nếu S là một tập HAW trên X, và Y X là một tập siêu phẳng phân tán, thì S HAW trên Y .
(iii) Nếu S1; S2; ::: là các tập HAW trên X thì \1 iD1
Si cũng là một tập HAW trên X.
(iv) Giả sử như f W Rn ! Rnlà một vi phôi C1, và S là một tập HAW, thì f .S / cũng là một tập HAW.
13H-absolute game
14-hyperplane diffuse
15
Tạp chí Epsilon, Số 08, 04/2016
Ý tưởng chính của chứng minh phần (i) của Định lý 19 là xây dựng trong S một tập con giống như tập Cantor15 như sau: ở mỗi bước, ta chia nhỏ ‘quả bóng’ B.xEi; ri/ thành các quả bóng con có phần trong đôi một không giao nhau với bán kính ˇri và bỏ đi các quả bóng giao với .ˇri/-lân cận của siêu phẳng Litrong chiến lược thắng cuộc của An. Tập giống Cantor nằm trong tập HAW S này cho chúng ta một chặn dưới của chiều Hausdorff của S, và chặn dưới này sẽ tiến về n khi ˇ tiến về 0. Bạn đọc có thể xem thêm chứng minh đầy đủ ở [3, Định lý 2.2].
Bài tập 20. (a) Chứng minh rằng tập Cantor trên R là19-siêu phẳng phân tán. (b) Có thể thay số 19bằng một số khác lớn hơn hay k0?
4. Véc tơ xấp xỉ kém
Áp dụng Định lý 19, ta dễ dàng có được Định lý 8 suy ra các Định lý 5 và 7. Để chứng minh Định lý 8, chúng ta sẽ dùng Bổ đề Đơn hình16.
Bổ đề Đơn hình là mở rộng của quan sát sau trên R: Cho k > 1, nếu như pqvàp0
q0là 2 số hữu tỉ
khác nhau với mẫu số ki q; q0 < kiC1, thì:
ˇˇˇˇpqp0 q0
ˇˇˇˇ Dˇˇˇˇpq0 p0q qq0
ˇˇˇˇ 1qq0> k2i2:
Như vậy mọi đoạn thẳng trên R có bán kính 0 < r <12k2i2có chứa nhiều nhất một số hữu tỉ p
qvới ki q; q0 < kiC1.
Cho .n C 1/ điểm xE0; xE1; xE2; :::; xEn, sao cho n véc tơ .xE1 Ex0/; .xE2 Ex0/; :::; .xEn Ex0/ độc lập tuyến tính. Đơn hình với các đỉnh ˚xE0; xE1; :::; xEn được định nghĩa là:
.xE0; :::; xEn/ WD ˚xE0 C a1.xE1 Ex0/ C ::: C an.xEn Ex0/ W a1; :::; an 0; a1 C ::: C an 1 :
Khi n D 1, .x0; x1/ là đoạn thẳng nối x0 và x1. Khi n D 2, .xE0; xE1; xE2/ là hình tam giác với các đỉnh xE0; xE1; xE2. Khi n D 3, .xE0; :::; xE3/ là tứ diện với các đỉnh xE0; :::; xE3. Thể tích của đơn hình có thể được tính đơn giản như sau:
.xE0; :::; xEn/ D1nŠˇˇdetxE1 Ex0; xE2 Ex0; :::; xEn Ex0 ˇˇ:
Bổ đề 21 (Bổ đề Đơn hình [15, Bổ đề 4]). Cho 0 < ˇ < 13. Với mỗi k 2 N, gọi Uk là tập các véc tơ hữu tỉ có mẫu nằm giữa ˇn
nC1.k1/ và ˇn
nC1k:
:
15Cantor-like set
16Simplex Lemma
Uk WD
pE
qW Ep 2 Zn; ˇ n
nC1.k1/ q < ˇ n
nC1k
16
Tạp chí Epsilon, Số 08, 04/2016
Đặt Vn là thể tích của quả bóng đơn vị trong Rn. Với mọi: 0 < r < ˇ.nŠVn/1n
và với mọi xE 2 Rn, tồn tại một siêu phẳng Lk sao cho:
Lk:
Bài tập 22. GọipE0
q0;pE1
q1; :::;pEn
Uk \ B
x; ˇ Ek1r
pE1
pE0
qnlà .n C 1/ điểm hữu tỉ trong Uk sao cho n véc tơ
q1
q0
;
pE2
q2
pE0 q0
; ...,
pE2
q2
pE0 q0
độc lập tuyến tính. Tìm một cận dưới của
pE0
q0;pE1
q1; :::;pEn
qn
.
Bài tập 23. Chứng minh Bổ đề Đơn hình 21.
Chứng minh Định lý 8. . Cho 0 < ˇ < 13cố định bất kỳ. Xét trò chơi ˇ-siêu phẳng tuyệt đối trên R với BAn là tập đối tượng của An. Lưu ý rằng BAn trù mật, nên nếu như bán kính của các lựa chọn của Bình không hội tụ về 0, An sẽ thắng. An có thể đi bất kỳ cho đến khi bán kính của quả bóng Bình chọn nhỏ hơn ˇ.nŠVn/1n . Vì thế ta có thể giả sử rằng B1 D B.xE1; r1/ với r1 < ˇ.nŠVn/1n , và lim
i!1ri D 0.
Đặt c D ˇ2r1. Với mỗi k 2 N, gọi ik là lượt đi mà:
ˇk1r1 rik > ˇkr1:
Với mỗi lượt không nằm trong dãy fikg1
kD1, An có thể đi bất kỳ. Ở bước đi thứ ik, theo Bổ đề
Đơn hình 21, tồn tại siêu phẳng Lk sao cho:
Uk \ B.xEk; rik/ Lk:
Bước đi ở lượt thứ ik của An sẽ là
ˇkC1r1
-lân cận của Lk. Vì
BikC1 Bij X L.ˇkC1r1/
k;
với mọi yE 2 BikC1 và với mọipEq2 Uk:
yE pEq ˇkC1r1 D cˇk1 c
q1C 1n:
Vì:[1
kD1
theo định nghĩa của BAn (1.1),
Uk D Qn;
\1 iD1
B.xEi; ri/ D\1 kD1
B.xEik; rik/ 2 BAn :
Vì vậy, An có chiến lược để cho kết quả \1 iD1
B.xEi; ri/ luôn giao với BAn. 17
Tạp chí Epsilon, Số 08, 04/2016
Lưu ý 24. Một hệ quả thú vị của các kết quả trên là 2 tập rất nhỏ là tập Cantor C và tập các số xấp xỉ kém BA1 vẫn giao nhau, và phần giao cũng không nhỏ:
dimH .BA1 \C/ D dimH .C/ Dlog 2
log 3:
Không những thế, với mọi dãy số a1; a2; :::, các dịch chuyển của BA1 bởi ai vẫn giao với tập
Cantor:
dimH
C \\1 iD1
.BA1 Cai/
!
Dlog 2
log 3:
Kết quả này đã được chứng minh bởi Fishman [8] sử dụng trò chơi của Schmidt.
Tài liệu tham khảo
[1] R. Broderick, L. Fishman, D. Kleinbock, A. Reich, và B. Weiss, The set of badly approx imable vectors is strongly C1-incompressible, Math. Proc. Cambridge Philos. Soc. 153, no. 2 (2012), pp. 211–253.
[2] R. Broderick, L. Fishman, và D. Simmons, Badly approximable systems of affine forms and incompressibiblity on fractals, J. Number Theory 133 (2013), pp. 2186–2205.
[3] R. Broderick và D. Kleinbock, Dimension estimates for sets of uniformly badly approx imable systems of linear forms, preprint (2013), arXiv:1311.5474.
[4] J. W. S. Cassels, Simultaneous Diophantine approximation II, Proc. Lon. Math. Soc. 3 (1955), pp.435–448.
[5] H. Davenport, Simultaneous Diophantine approximation, Mathematika 1 (1954), pp. 51–72.
[6] K. J. Falconer, Fractal Geometry: Mathematical Foundations and Applications (1990), John Wiley & Sons.
[7] K. J. Falconer, The geometry of fractal sets, Cambridge Tracts in Math. 85 (1986), Cam bridge Univ. Press.
[8] L. Fishman, Schmidt’s game on fractals, Israel J. Math. 171 (2009), pp. 77–92.
[9] L. Fishman, D. Simmons, và M. Urbanski, Diophantine approximation and the geometry of limit sets in Gromov hyperbolic metric spaces, sắp được đăng tại Mem. Amer. Math. Soc., arXiv:1301.5630.
[10] D. Gale và F. M. Stewart, Infinite games with perfect information, in: Contribution to the theory of games, Vol. II, Annals of Math. Studies 28 (1953), pp. 245–266.
[11] V. Jarník, Diophantische approximationen und hausdorffsches mass, Recueil Math. Moscow 36 (1929), pp. 371–382.
[12] A. Y. Khintchine, Einige Satze ¨ uber Kettenbr ¨ uche, mit Anwendungen auf die Theorie der ¨ Diophantischen Approximationen, Math. Ann. 92 (1924), pp. 115–125.
18
Tạp chí Epsilon, Số 08, 04/2016
[13] A. Y. Khintchine, Zur metrischen Theorie der Diophantischen Approximationen, Math. Zeitschrift 24 (1926), pp. 706–713.
[14] D. Kleinbock và T. Ly, Badly approximable S-numbers and absolute Schmidt games, J. Number Theory 164 (2016), pp. 13–42.
[15] S. Kristensen, R. Thorn, và S. Velani, Diophantine approximation and badly approximable sets, Advances in Math. 203 (2006), pp.132–169.
[16] Lý Ngọc Tuệ, Xấp xỉ Diophantine trên R và Liên phân số, Epsilon 4 (2015).
[17] Lý Ngọc Tuệ, Xấp xỉ Diophantine trên Rn- Quy tắc Dirichlet và Hình học của số, Epsilon 5 (2015).
[18] Lý Ngọc Tuệ, Xấp xỉ Diophantine với độ đo - Định lý Khintchine, Epsilon 6 (2015). [19] Lý Ngọc Tuệ, Trò chơi vô hạn với thông tin hoàn hảo, Epsilon 7 (2016).
[20] C. McMullen, Winning sets, quasiconformal maps and Diophantine approximation, Geom. Funct. Anal. 20, no. 3, (2010), pp. 726–740.
[21] W. M. Schmidt, On badly approximable numbers and certain games, Trans. Amer. Math. Soc. 123 (1966), pp. 178–199.
[22] W. M. Schmidt, Badly approximable systems of linear forms, J. Number Theory 1 (1969), pp. 139–154.
19
Tạp chí Epsilon, Số 08, 04/2016
20
CƠ SỞ GROBNER LÀ GÌ? ¨
Bernd Sturmfels - Đại Học California, Berkeley, Mỹ
Bài viết được Nguyễn Vũ Duy Linh dịch từ bài báo “What is Groebner basis” của giáo sư Bernd Sturmfels đăng trên tạp chí Notice of AMS, volume 52, number 10; 2005:
Một cơ sở Grobner là một tập hợp các đa thức nhiều biến có các tính chất mong muốn về giải ¨ thuật. Mỗi tập hợp các đa thức có thể biến đổi thành một cơ sở Grobner. Quá trình biến đổi này ¨ tổng quát hóa ba kỹ thuật quen thuộc: Phép khử Gauss để giải hệ phương trình tuyến tính, thuật toán Euclide để tính ước chung lớn nhất của hai đa thức một biến và thuật toán đơn hình trong qui hoạch tuyến tính (xem Œ3) Chẳng hạn, đầu vào của phép khử Gauss là tập các dạng tuyến tính sau
D f2x C 3y C 4z 5; 3x C 4y C 5z 2g;
Và thuật toán biến đổi thành cơ sở Grobner ¨
% D fx z C 14; y C 2z 11g:
Gọi K là một trường bất kỳ, chẳng hạn như trường số thực K D R; trường số phức K D C; trường số hữu tỉ K D Q; hay là trường hữu hạn K D Fp: Ta ký hiệu KŒx1; : : : ; xn là vành các đa thức n biến xi với hệ số trong trường K: Nếu F là một tập hợp bất kỳ các đa thức thì ideal sinh bởi là tập hợp h i bao gồm mọi tổ hợp tuyến tính các đa thức của
h i D fp1f1 C C prfr W f1; : : : ; fr 2 và p1; : : : ; pr 2 KŒx1; : : : ; xng:
Trong ví dụ của chúng ta, tập và cơ sở Grobner ¨ % của nó sinh ra cùng một ideal h%i D h i: Theo định lý Hilbert về cơ sở, mỗi một ideal trong KŒx1; x2; : : : ; xn có dạng I D h i; nghĩa là nó được sinh ra bởi một tập hữu hạn các đa thức.
Một thứ tự đơn thức trên KŒx1; x2; : : : ; xn là một thứ tự toàn phần trên tập hợp tất cả các đơn thức xa D xa1
1 xa2
2 xan
nvới hai tính chất sau
.1/ Nó là nhân tính, nghĩa là xa xbkéo theo xaCc xbCcvới mọi a; b; c 2 Nn: .2/ Đơn thức hằng là nhỏ nhất, có nghĩa là 1 xavới mọi a 2 Nnf0g:
Một ví dụ của thứ tự đơn thức (với n D 2/ là thứ tự từ điển phân bậc
1 x1 x2 x21 x1x2 x22 x23 x21x2
Nếu chúng ta cố định thứ tự đơn thức ; khi đó mỗi đa thức có duy nhất một số hạng khởi đầu trong .f / D xa: Đó là đơn thức cực đại xaxuất hiện trong khai triễn của f với hệ số khác không. Chúng ta viết các số hạng của f theo thứ tự giảm dần, và thông thường chúng ta gạch dưới số hạng khởi đầu. Chẳng hạn, một đa thức bậc hai có thể được viết như sau:
f D 3x22 C 5x1x2 C 7x21 C 11x1 C 13x2 C 17:
21
Tạp chí Epsilon, Số 08, 04/2016
Giả sử I là một ideal của KŒx1; : : : ; xn: Khi đó ideal khởi đầu của nó trong .I / là ideal sinh ra bởi số hạng khởi đầu của tất cả đa thức trong I W
in .I / D hin .f / W f 2 I i:
Một tập con hữu hạn % của I là một cơ sở Grobner tương ứng với thứ tự theo số hạng ¨ nếu như các số hạng khởi đầu của các phần tử trong % đủ để sinh ra ideal khởi đầu:
in .I / D hin .g/ W g 2 %i:
Không có yêu cầu về tính tối tiểu để trở thành một cơ sở Grobner. Nếu ¨ % là một cơ sở Grobner ¨ của I thì một tập con hữu hạn bất kỳ của I chứa % cũng là một cơ sở Grobner. Để khắc phục tính ¨ phi tối tiểu đó, chúng ta gọi % là một cơ sở Grobner rút gọn nếu: ¨
.1/ Với mỗi g 2 % hệ số của in .g/ trong g là 1:
.2/ Tập hợp fin .g/ W g 2 %g là tập nhỏ nhất sinh ra in .I /; và
.3/ không có số hạng theo sau với mọi g 2 % nằm trong in .I /:
Với định nghĩa này, ta có định lý sau đây: Nếu như cố định thứ tự đơn thức thì mỗi ideal I trong KŒx1; : : : ; xn có một cơ sở Grobner rút gọn duy nhất. ¨
Cơ sở Grobner rút gọn ¨ % có thể được tính từ mọi tập sinh của I theo phương pháp được giới thiệu trong luận án của Bruno Buchberger năm 1965: Buchberger gọi phương pháp của mình theo tên của người hướng dẫn Wolfgang Grobner. Sau đó người ta nhận ra rằng, ý tưởng về cơ sở ¨ Grobner đã có trước đó chẳng hạn trong một bài viết của Paul Gordan, một nhà nghiên cứu về ¨ bất biến. Tuy nhiên Buchberger là người đầu tiên đề ra một giải thuật để tính cơ sở Grobner. ¨
Cơ sở Grobner rất tiện dụng để giải hệ phương trình đa thức. Giả sử ¨ K C; và là một tập hữu hạn các đa thức trong KŒx1; : : : ; xn: Đa tập của là tập tất cả các không điểm phức chung
. / D f.z1; : : : ; zn/ 2 CnW f .z1; : : : ; zn/ D 0 với mọi f 2 g:
Đa tạp không thay đổi nếu ta thay bởi một tập các đa thức sinh ra cùng một ideal trong KŒx1; : : : ; xn: Nói riêng, cơ sở Grobner giới hạn ¨ % của ideal h i có cùng một đa tạp:
. / D .h i/ D .h%i/ D .%/:
Ưu điểm của % là nó cho biết những đặc tính hình học của đa tạp, những đặc tính này không hiển lộ từ : Câu hỏi đầu tiên được đặt ra là liệu đa tạp . / có thể rỗng hay không. Định lý không điểm Hilbert ngụ ý rằng đa tạp . / rỗng khi và chỉ khi % bằng f1g:
Làm thế nào để đếm số không điểm của một hệ thống các phương trình đã cho? Để trả lời cho câu hỏi này, chúng ta cần thêm một định nghĩa. Cho một ideal cố định I trong KŒx1; : : : ; xn và một thứ tự đơn thức ; một đơn thức xa D xa1
1 xa2
2 xan
nđược gọi là chuẩn nếu như nó trong ở trong
ideal khởi đầu in .I /: Số lượng các đơn thức chuẩn là hữu hạn nếu và chỉ nếu mỗi biến xi xuất hiện trong một lũy thừa nào đó của ideal khởi đầu. Chẳng hạn, nếu in .I / D˝x31; x42; x53˛thì sẽ có sáu mươi đơn thức chuẩn, nhưng trong in .I / D˝x31; x42; x1x43˛tập hợp các đơn thức chuẩn là vô hạn.
Đa tạp .I / là hữu hạn nếu và chỉ nếu tập hợp các đơn thức chuẩn là hữu hạn và số lượng các đơn thức chuẩn bằng với lực lượng của .I / trong đó các không điểm bội cấp k sẽ được đếm k lần.
22
Tạp chí Epsilon, Số 08, 04/2016
Khi n D 1 đây chính là Định lý cơ bản của Đại số, định lý này phát biểu rằng đa tạp .f / của đa thức một biến f 2 KŒx với bậc d bao gồm d số phức. Ở đây tập hợp có phần tử duy nhất ff g là cơ sở Grobner, và các đơn thức chuẩn là ¨ 1; x; x2; : : : ; xd1:
Tiêu chuẩn của chúng ta trong việc quyết định liệu một đa tạp có hữu hạn hay không tổng quát hóa công thức sau cho số chiều của một đa tạp. Xét một tập con S của tập các biến fx1; : : : ; xng thế nào cho không có đơn thức nào trong S xuất hiện trong in .I /; và giả sử rằng S có lực lượng lớn nhất trong số các tập con có cùng tính chất. Khi đó lực lượng tối đại jSj bằng với số chiều của .I /:
Tập hợp các đơn thức chuẩn là một cơ sở trong không gian vector trên trường số K cho vành các thặng dư KŒx1; : : : ; xn=I: Ảnh của một đa thức p modulo I có thể được biểu diễn một cách duy nhất như là một K tổ hợp tuyến tính của các đơn thức chuẩn. Biểu thức này là dạng chuẩn của p: Quá trình tính dạng chuẩn là thuật toán chia. Trong trường hợp quen thuộc với một biến x; khi mà I D hf i và f có bậc d; thuật toán chia biểu diễn một đa thức tùy ý p 2 KŒx dưới dạng một K tổ hợp tuyến tính của 1; x; x2; : : : ; xd1: Tuy nhiên thuật toán chia áp dụng được cho một cơ sở Grobner tùy ý ¨ % với số lượng biến tùy ý.
Làm thế nào chúng ta có thể thử nghiệm liệu một tập các đa thức cho trước là một cơ sở Grobner ¨ hay không? Xét hai đa thức tùy ý g và g0trong %: Thành lập S đa thức m0g mg0: Ở đây m và m0là hai đa thức bậc nhỏ nhất có thể thế nào cho m0 in .g/ D m in .g0/: S đa thức m0g mg0nằm trong ideal h%i: Chúng ta áp dụng thuật toán chia đối với cơ sở Grobner tạm ¨ thời % cho m0g mg0: Dạng chuẩn thu nhận được là một K tổ hợp tuyến tính của các đơn thức trong đó không có đơn thức nào chia hết cho một đơn thức khởi đầu từ %: Điều kiện cần để % là một cơ sở Grobner là ¨
normalform%.m0g mg0/ D 0 với mọi g; g02 %:
Tiêu chuẩn Buchberger phát biểu rằng điều kiện cần đó cũng chính là điều kiên đủ: Một tập hợp % các đa thức là một cơ sở Grobner nếu và chỉ nếu mọi ¨ S đa thức của nó có dạng chuẩn zero. Từ tiêu chuẩn này, người ta đề ra thuật toán Buchberger Œ1 để tính cơ sở Grobner rút gọn ¨ % từ một tập hợp đầu ra bất kỳ.
Tóm lại, các cơ sở Grobner và thuật toán Buchberger để tìm chúng là những khái niệm căn bản ¨ của đại số. Chúng cung cấp những cách tính toán tiên tiến trong hình học đại số, chẳng hạn như lý thuyết khử, tính đối đồng điều, giải quyết tính kỳ dị, ... Cũng như các mô hình đa thức có mặt khắp nơi từ khoa học đến kỹ thuật, các cơ sở Grobner được các nhà nghiên cứu sử dụng trong tối ¨ ưu hóa, lập trình, robotics, lý thuyết điều khiển, thống kê, sinh học phân tử và nhiều ngành khác. Chúng tôi mời bạn đọc thử dùng qua một trong các cài đặt của thuật toán Buchberger (chẳng hạn như CoCoA, Macaulay2, Magma, Maple, Mathematica, hay Singular).
Tài liệu tham khảo
[1] DAVID COX, JOHN LITTLE, and DONAL O’ SHEA, Ideals, Varieties and Algorithms. An Introduction to Computational Algebraic Geometry and Commutative Algebra, second ed. Undergraduate Texts in Mathematics, Springer-Verlag, New York, 1997:
[2] NIELS LAURITZEN, Concrete Abstract Algebra: From Numbers to Grobner Bases ¨ , Cam bridge University Press, 2003:
23
Tạp chí Epsilon, Số 08, 04/2016
[3] BERND STURMFELS, Two Lectures on Grobner Bases ¨ , New Horizons in Undergraduate Mathematics, VMath Lecture Series, Mathematical Sciences Research Institute, Berkeley, California, 2005; http://www.msri.org/communications/vmath/special_ productions/.
24
TẬP TRÁNH TỔNG TRONG NHÓM Terence Tao - UCLA, California, Mỹ
Trong số này, Epsilon trân trọng giới thiệu với độc giả một bài viết của nhà toán học Terence Tao, qua bản dịch của Trần Nam Dũng.
Tôi và Vũ Hà Văn vừa đăng lên arXiv bài báo “tập tránh tổng trong nhóm” [1] (gửi đăng đến tạp chí Discrete Analysis), cùng với bài báo tổng quan đính kèm [2] (gửi đăng đến J. Comb.). Cho tập con A của nhóm cộng tính G D .G; C/, ta định nghĩa .A/ là lực lượng (số phần tử) của tập con B lớn nhất của A tránh tổng trong A theo nghĩa mọi tổng b1 C b2 với b1; b2 là các phần tử phân biệt của B nằm ngoài A. Ví dụ, nếu A là chính nhóm đó thì .A/ D 1, vì không có hai phần tử nào của A lại có thể có tổng là một cái gì đó nằm ngoài A. Một cách tổng quát, nếu A là hợp của k nhóm, thì .A/ tối đa là bằng A theo nguyên lý chuồng và thỏ.
Nếu G là tập hợp các số nguyên, thì ta không có nhóm con thực sự nào, và ta có thể dự đoán rằng .A/ sẽ tăng cùng với A. Ví dụ ta có kết quả đơn giản sau:
Mệnh đề 1. Nếu A là tập hợp gồm 2ksố tự nhiên thì .A/ > k.
Chứng minh: Ta sử dụng lý luận của Ruzsa [3] vốn được dựa trên một lý luận cũ của Choi [4]. Gọi x1 là phần tử lớn nhất của A, và sau đó một cách đệ quy, khi x1; x2; : : : ; xi đã được chọn, gọi xiC1 là phần tử lớn nhất trong A không bằng x1; x2; : : : ; xi sao cho xiC1 C xj … A với mọi j D 1; : : : ; i, và kết thúc quá trình xây dựng này khi không tìm được một xiC1 như vậy. Quá trình này sẽ cho chúng ta dãy x1 > x2 > > xm các phần tử trong A, tránh tổng trong A và có tính chất với mọi y 2 A, hoặc y bằng với một trong các xi, hoặc y C xi 2 A với i nào đó với xi > y. Lặp lại quá trình này, ta thấy mọi y 2 A đều có dạng xi1 xi2 xijvới j 1 nào đó và 1 i1 i2 < ij m. Số các biểu thức xi1 xi2 xijtối đa là 2m–1, do đó 2k 2m–1, từ đó m k C 1. Vì .A/ m nên ta suy ra điều phải chứng minh.
Đặc biệt ta có .A/ >> logjAj đối với các tập con A của tập hợp các số nguyên. Ta có thể cải thiện cận dưới đơn giản này, nhưng sẽ rất tốt công sức. Cận dưới tốt nhất cho đến thời điểm hiện nay là
.A/ logjAj.loglogjAj/1=2o.1/
một kết quả của Shao [5] (xây dựng dựa trên công trình trước đó của Sudakov, Szemeredi và Vu [6] và của Dousse [4]). Trong chiều ngược lại Ruzsa [3] đã xây dựng ví dụ một tập hợp A lớn với
.A/ exp.O.plogjAj/).
Sử dụng công cụ chuẩn của đồng cấu Freiman, các kết quả trên đấy cho số nguyên có thể mở rộng cho các nhóm abel không xoắn G. Trong bài báo của mình chúng tôi nghiên cứu trường hợp ngược lại khi G là nhóm hữu hạn (nhưng vẫn abel). Trong bài báo này của Erdos [7] (mà trong đó đại lượng .A/ lần đầu tiên được giới thiệu), câu hỏi sau đây được đặt ra: nếu A là đủ lớn so với .A/ thì có suy ra tồn tại hai phần tử x; y thuộc A sao cho x C y D 0 hay không? Chúng tôi đã tìm được những phản ví dụ đơn giản cho mệnh đề này. Ví dụ, nếu H là một nhóm hữu hạn
25
Tạp chí Epsilon, Số 08, 04/2016
cộng tính tùy ý, khi đó tập hợp: A WD Œ1 mod 7; 2 mod 7; 4 mod 7 H .Z=7Z/ H có .A/ D 3 nhưng không có hai phần tử x; y 2 A nào có tổng bằng 0; dạng ví dụ này vẫn đúng nếu thay 7 bằng một số nguyên tố Mersenne lớn hơn, và ta có phản ví dụ trong Z=2nZ với n lớn tùy ý. Tuy nhiên, theo hướng khẳng định, ta có thể chứng minh rằng câu trả lời cho câu hỏi của Erdos là khẳng định nếu ¨ jGj không có ước nguyên tố nhỏ. Rõ hơn là
Mệnh đề 2. Với mọi k 1 tồn tại C 1 sao cho nếu G là nhóm abel hữu hạn có bậc không có ước nguyên tố nhỏ hơn hay bằng C và A là một tập con của G có bậc ít lần là C và .A/ k thì tồn tại x; y 2 A sao cho x C y D 0.
Có hai công cụ chính sử dụng để chứng minh kết quả này. Một là “bổ đề loại bỏ số học” được chứng minh mởi Kral, Serra và Vena [8]. Chú ý rằng điều kiện .A/ k có nghĩa là với mọi các phần tử phân biệt x1; : : : ; xkC1 2 A, tồn tại một trong các phần tử xi C xj ; 1 i < j k C 1, cũng nằm trong A. Một cách nôm na, bổ đề loại bỏ số học cho phép ta “gần như” có thể bỏ đi yêu cầu x1; : : : ; xkC1 phân biệt, và điều này có nghĩa là từ x 2 A gần như có thể suy ra 2x 2 A. Phép đối xứng gần-vị tự này khi kết hợp với giả thiết rằng jGj không có ước nguyên tố nhỏ sẽ cho rất nhiều sự “phân tán” trong hệ số Fourier của 1A mà có thể được khai thác để chứng minh định lý.
Công cụ thứ hai là định lý cấu trúc dưới đây, là kết quả chính của bài báo của chúng tôi, và đi đường theo hướng phân loại các tập con A với .A/ nhỏ:
Mệnh đề 3. Cho A là tập con hữu hạn của một nhóm cộng tính G bất kỳ với .A/ k. Khi đó tìm được các nhóm con hữu hạn H1; H2; : : : ; Hm với m k sao cho jA \ Hij >>k jHi và jA n .H1 [ [ Hm/j <>k 1 của tất cả các cặp a; b trong A phải có tổng cũng nằm trong A (ngược lại ta có thể lấy k C 1 phần tử ngẫu nhiên của A và chúng sẽ tránh tổng trong A với xác suất dương). Từ điều này và định lý Balog-Szemeredi và định lý Freiman (trong mọi nhóm abel, được chứng minh bởi Green và Ruzsa [10]), ta thấy rằng A phải “cân xứng” với “đối tập cấp số” (“coset progression”) H C P của rank chặn trên. Sau đó ta có thể khử thành phần không xoắn P của đối tập cấp số này bằng một số phương pháp (ví dụ sử dụng các phương án của lý luận trong mệnh đề 1), với kết quả cuối cùng mà người ta có thể xác định vị trí nhóm H1 hữu hạn có phần giao lớn với A.
Từ điểm này sẽ hấp dẫn nếu loại bỏ H1 khỏi A và lặp lại. Nhưng ta sẽ gặp một khó khăn kỹ thuật là loại bỏ một tập hợp như H1 khỏi A có thể làm thay đổi đại lượng .A/ theo một cách không thể dự đoán được, vì thế ta vẫn cần phải giữ H1 lại khi phân tích tập thặng dư A n H1. Khó khăn thứ hai là tập hợp A n H1 có thể là nhỏ hơn đáng kể so với A và H1 nhưng vẫn còn lớn theo nghĩa tuyệt đối, do đó nói riêng thì mọi số hạng sai số có kích thước chặn trên bởi jAj với nhỏ
26
Tạp chí Epsilon, Số 08, 04/2016
có thể vẫn lớn so với tập thặng dư A n H1, và do đó số hạng sai số đó là không chấp nhận được. Ta có thể vượt qua được những khó khăn này nếu trước tiên ta thực hiện bước tiền “chuẩn hóa” của nhóm H1, để cho tập thặng dư không giao với mọi đối tập của H1 quá nhiều. Các lý luận còn trở nên phức tạp hơn khi ta bắt đầu loại bỏ nhiều hơn một trong các nhóm H1; : : : ; Hitừ A và phân tích tập thặng dư A n .H1 [ [ Hm/; thật vậy quá trình “quản lý epsilon” liên quan sẽ trở nên phức tạp đến nỗi mà chúng ta buộc phải sử dụng cách phát biểu phân tích không tiêu chuẩn của bài toán để giữ độ phức tạp của các lý luận ở mức chấp nhận được (xem bài viết blog trước của tôi về chủ đề này [11]). Một nhược điểm của cách làm như vậy là chúng ta không có giới hạn hiệu quả cho các hằng số trong định lý chính của chúng tôi; sẽ thú vị để có được một nó sẽ được một chứng minh trực tiếp hơn cho định lý của chúng tôi mà có thể sẽ dẫn đến giới hạn hiệu quả.
Tài liệu tham khảo
[1] http://arxiv.org/abs/1603.03068
[2] http://arxiv.org/abs/1603.03071
[3] Imre Z. Ruzsa, Sum-Avoiding Subsets, The Ramanujan Journal, March 2005, Volume 9, Issue 1, pp 77-82.
[4] Choi, S. L. G. On a combinatorial problem in number theory. Proc. London Math. Soc. (3) 23 (1971), 629–642.
[5] Shao, Xuancheng Finding linear patterns of complexity one. Int. Math. Res. Not. IMRN 2015, no. 9, 2311–2327.
[6] Sudakov, B.; Szemerédi, E.; Vu, V. H. On a question of Erdos and Moser. Duke Math. J. 129 ˝ (2005), no. 1, 129–155.
[7] Erdos, P. Extremal problems in number theory. 1965 Proc. Sympos. Pure Math., Vol. VIII ˝ pp. 181–189 Amer. Math. Soc., Providence, R.I.
[8] Kráˇl, Daniel; Serra, Oriol; Vena, Lluís On the removal lemma for linear systems over abelian groups. European J. Combin. 34 (2013), no. 2, 248–259.
[9] Freiman theorem
[10] Green, Ben; Ruzsa, Imre Z. Freiman’s theorem in an arbitrary abelian group. J. Lond. Math. Soc. (2) 75 (2007), no. 1, 163–175.
[11] https://terrytao.wordpress.com/2007/06/25/ultrafilters-nonstandard-analysis-and-epsilon management/
27
Tạp chí Epsilon, Số 08, 04/2016
28
TOÁN HỌC CỦA HÔN NHÂN
Matt Baker – Viện công nghệ Georgia, Mỹ
Nguyễn Vũ Anh dịch từ blog của Matt Baker – Trần Nam Dũng hiệu đính.
Thân tặng Võ Quốc Bá Cẩn, biên tập viên đầu tiên của Epsilon nhân ngày cưới của anh và chị Nguyễn Thị Kim Anh vào ngày 27 / 3 / 2016.
Ngày 25 tháng 6 năm 2014
Cũng khá lâu kể từ bài blog gần nhất của tôi – một trong những lý do đó là gần đây tôi đã kết hôn. Để kỷ niệm cho sự kiện này, cũng như đánh dấu sự trở lại của tôi trên blog toán học tôi sẽ đăng bài về định lý Hall về hôn nhân.
Hãy xét trò chơi solitaire (game xếp bài của Windows): Bạn có một bộ bài được chia làm 13 cọc, mỗi cọc 4 lá, và bạn phải chọn 1 lá từ mỗi cọc sao cho không có giá trị nào (từ A đến K) lặp lại. Đây là một sự kiện toán học vô cùng đẹp đẽ là trò chơi luôn có thể hoàn thành, bất chấp các quân bài được chia ra sao.
Chúng ta sẽ suy luận điều này từ một kết quả tổng quát hơn của Philip Hall, thường được gọi là định lý Hall về hôn nhân. Cho hữu hạn tập hợp A1; A2; : : : ; An và bạn phải tìm các phần tử riêng biệt x1 2 A1; x2 2 A2; : : : ; xn 2 An: (Trong ví dụ trò solitaire, cho Aj chứa các giá trị của các lá bài nằm trong cọc thứ j:) Sự lựa chọn này được gọi là SDR (system of distict representatives-hệ đại diện riêng biệt). Dưới điều kiện nào thì điều này khả thi? Để hệ đại diện riêng biệt này tồn tại thì điều kiện cần thiết là với mọi tập con J 2 .1; 2; : : : ; n/; tập hợp AJ D Uj2J Aj chứa ít nhất jJ j phần tử. Định lý của Hall khẳng định rằng những điều kiện trên cũng chính là điều kiện đủ.
Trong ví dụ về trò bói bài, ta chọn k cọc bất kì, chứa 4k lá bài. Bởi vì chỉ có 4 lá bài mỗi cọc với mọi giá trị, khi chúng ta kết hợp những cọc bài chúng ta chọn, sẽ có ít nhất k giá trị khác nhau. Do đó, những điều kiện của định lý Hall đều thỏa và định lý hôn nhân sẽ khẳng định rằng chúng ta có một cách đi thắng.
Một ví dụ khác, xét bài toán sau có lời giải đơn giản hơn định lý Hall về hôn hân:
[Kì thi Putnam, bài toán B-3] Một giải đấu vòng tròn 2n đội kéo dài 2n 1 ngày. Mỗi ngày, tất cả các đội đấu với một đội khác, trong đó có 1 đội thắng và 1 đội thua trong mỗi n trận. Xuyên suốt giải đấu, 2 đội bất kì gặp nhau đúng 1 lần. Liệu có luôn chọn được mỗi ngày một đội thắng mà không có đội nào được chọn nhiều hơn 1 lần?
Kết quả của Hall được biết tới là định lý hôn nhân vì nó có thể phát biểu lại theo cách sau. Giả sử mỗi một tập hợp hữu hạn chàng trai quen với một tập hợp hữu hạn các cô gái. Điều kiện là gì để mỗi chàng trai đều kết hôn với một trong những người họ quen biết? Điều kiện cần và đủ là mỗi tập hợp k chàng trai, được chọn một cách ngẫu nhiên, quen với ít nhất k cô gái. Rất dễ dàng nhận thấy sự tương đương của hai cách phát biểu (cho Aj là tập hợp các cô gái mà chàng trai thứ j quen).
29
Tạp chí Epsilon, Số 08, 04/2016
Cách chứng minh đơn giản nhất cho định lý của Hall mà tôi biết xuất hiện đầu tiên trong bài báo 2 trang của Halmos và Vaughan, được thực hiện phép quy nạp theo số chàng trai n: Ta trích dẫn trực tiếp chứng minh của Halmos và Vaughan:
“Với n D 1; kết quả là hiển nhiên. Với n > 1; nếu với mọi tập hợp k bạn nam 1 6 k 6 n; có ít nhất k C 1 người quen, 1 bạn nam sẽ cưới một trong những người quen bất kì của anh ta và đưa những người còn lại vào giả thuyết quy nạp. Nếu ngược lại, một số nhóm k chàng trai, 1 6 k 6 n; có chính xác k người quen, thì tập hợp này sẽ có thể kết hôn theo giả thiết quy nạp, n k chàng trai còn lại cũng thỏa mãn điều kiện cần với những cô gái chưa kết hôn. Thật vậy, nếu 1 6 h 6 n k; và nếu một số tập hợp h chàng trai chưa có vợ ít hơn h cô gái chưa có chồng, thì tập hợp h chàng trai chưa có vợ cùng với k chàng trai đã kết hôn sẽ quen ít hơn k C h cô gái. Áp dụng giả thiết quy nạp vào n k chàng trai chưa có vợ, ta thu được kết luận định lý đúng với n C 1 chàng trai.”
Có một chứng minh đẹp cho định lý của Hall, được đề ra bởi Jack Edmonds, dựa trên đại số tuyến tính. Đây là một ví dụ sử dụng kỹ thuật đại số để giải quyết các vấn đề tổ hợp. Trước khi xem xét chứng minh của Edmonds, chúng ta cần 2 định nghĩa:
Định nghĩa 1. Cho B là một ma trận m n với các số hạng trong trường F đặc số 0: Chúng ta gọi B là generic nếu các số hạng khác 0 của nó độc lập đại số (chúng không thỏa mãn một đa thức không đồng nhất 0; với hệ số trong Q/:
Định nghĩa 2. Cho B là một ma trận m n có hạng r < n: Ta nói B là dạng Edmonds bình thường (Edmonds Normal Form, hay ENF) nếu B có thể viết dưới dạng một ma trận có ma trận B1 là ma trận r .r C 1/ ở phía trên bên trái mà:
.a/ r C 1 cột đầu tiên của B tạo thành một tập hợp phụ thuộc tuyến tính nhỏ nhất. .b/ Mỗi dòng của ma trận B2 phía dưới bên trái là một tổ hợp tuyến tính các dòng của B1:
Dễ nhận thấy, mọi ma trận B bậc m n có hạng r < n có thể chuyển về dạng ENF bằng cách hoán vị các cột và dòng. Thật vậy, nhờ vào việc hoán vị các cột, chúng ta có thể giả sử r C 1 cột đầu tiên tạo thành một tập hợp phụ thuộc tuyến tính nhỏ nhất. Ma trận hoán vị B0xác định bởi r C 1 cột đầu tiên có hạng r; nên nhờ vào hoán vị các dòng chúng ta có thể giả sử r dòng đầu tiên tạo thành một cơ sở cho không gian dòng của B0: Ma trận kết quả là một ENF.
Bây giờ chúng ta cùng xem phép chứng minh của Edmonds cho định lý của Hall:
Chứng minh. Cho n là số lượng chàng trai và m là số lượng cô gái. Cho ma trận generic m n với Bij ¤ 0; nếu cô gái thứ j quen chàng trai thứ j: Sử dụng công thức chuẩn cho định thức của ma trận bằng tổng các hoán vị, cùng với generic của B; ta thấy rằng sẽ tồn tại một cách tổ chức cưới hạnh phúc khi và chỉ khi định thức của một ma trận nhỏ n n nào đó của B khác 0; và điều này xảy ra khi và chỉ khi B có hạng > n: Không mất tính tổng quát, chúng ta có thể giả sử (bằng cách hoán vị các cột và dòng nếu cần) rằng B là một ENF: Vì các cột của B1 phụ thuộc tuyến tính, tồn tại một véc-tơ v khác 0 trong nhân của B: Bằng phép khử Gauss, chúng ta có thể giả sử tọa độ của v là những đa thức có số hạng khác 0 của B1: Nhờ vào tính chất .a/ của ENF, không
30
Tạp chí Epsilon, Số 08, 04/2016
một số hạng nào của v bằng 0: Và dựa vào tính chất .b/; mỗi dòng của B2 đều trực giao với v: Vì B2 là geniric, nên B2 D 0: Nhưng như vậy thì tập hợp các chàng trai tương ứng với r C 1 cột
đầu tiên chỉ quen với các cô gái tương ứng với r dòng đầu tiên, mâu thuẫn.
Các chứng minh bằng đại số tuyến tính xem ra là quá mức cần thiết so với phương pháp tổ hợp đơn giản. Nhưng nó lại có vài tính năng khá hấp dẫn: Ví dụ, việc làm sáng tỏ một cách rõ ràng dẫn tới một thuật toán xác suất hiệu quả để kiểm tra liệu có một hệ đại diện riêng biệt (SDR). (Sẽ thuận tiện nếu xem các số hạng của B là các ẩn số). Chứng minh trên đưa bài toán về việc xét xem một đa thức có khác 0 hay không. Về mặt tính toán là không khả thi để tính các định thức con của B như các đa thức, nhưng nếu chúng ta thay thế các giá trị cụ thể vào các ẩn số, chúng ta có thể xác định một cách hiệu quả các giá trị tương ứng có khác 0 theo một mô-đun nguyên tố đủ lớn hay không. Nếu dùng thuật toán nhân nhanh ma trận để tính định thức thì ta sẽ có thuật toán tiệm cận nhanh nhất để xác định bài toán hôn nhân có nghiệm hay không (trong thực tế, có những thuật toán tất định chạy nhanh hơn, và còn tìm ra các cặp ghép).
Cuối cùng, chúng tôi muốn đề cập đến định lý Hall có thể mở rộng cho các trường hợp có vô số chàng trai (nhưng số cô gái quen từng chàng trai vẫn là hữu hạn). Sự tổng quát này do Everett và Whaples đề xuất. Một lần nữa ta có cách nào tốt hơn là trích dẫn “Chứng minh từ Sách” (Proof from the Book) của Halmos và Vaughn, sử dụng cấu trúc điểm - tập hợp topo để giảm bớt trường hợp hữu hạn: Nếu tập hợp B các chàng trai là vô hạn, xét mỗi b 2 B và tập G.b/ là những người b quen, topo hóa các tập topo rời rạc, G.b/ là không gian compact Hausdorff. Viết G theo dạng tích Đề-các topo cho mọi G; theo định lý Tikhonov, G là compact. Nếu fb1; b2; : : : ; bng là một tập hữu hạn chàng trai bất kì, xét tập hợp H chứa các phần chứa tất cả các phần tử g D g.b/ của g sao cho gi ¤ gj với bi ¤ bj ; j D 1; ; 2; : : : ; n: H là tập con đóng của G; và dựa vào kết quả trong trường hợp hữu hạn, H khác rỗng. Vì hợp hữu hạn các tập hợp hữu hạn nên lớp của tất cả tập hợp như H có tính chất giao hữu hạn, và do đó có giao khác rỗng. Vì phần tử g D g.b/ trong phần giao này thỏa mãn tính chất g.b/ ¤ g.b0/ với mọi b ¤ b0; phép chứng minh hoàn tất.
Ghi chú
1: Bài báo công bố năm 1950 của Halmos và Vaughan, có tên là “The Marriage Problem”, được đăng lại trong cuốn sách “Classic Papers in Combinatorics” (biên soạn bởi by Gessel and Rota), cùng với bài báo ban đầu của Hall. Bài báo của Edmonds năm 1967 có tên là “Systems of Distinct Representatives and Linear Algebra”. Đoạn chứng minh của Edmonds mà tôi nói đến ở trên được lấy từ bài báo này Œ1: Các bình luận trên đây về định thức và khía cạnh thuật toán của bài toán hôn nhân được trích từ buốn sách “Thirty - three miniatures” của Jiri Matousek. Cuốn sách này chứa một số ví dụ thú vị về chứng minh các kết quả tổ hợp bằng đại số tuyến tính.
2: Lời giải của bài toán Putnam có thể xem ở Œ2: Nếu bạn thích bài toán này, ở đây có một bài toán vui khác dựa trên định lý Hall: Nếu G là một nhóm hữu hạn và H là một nhóm con chỉ số n: Chứng minh rằng tồn tại các phần tử g1; g2; : : : ; gn thuộc G sao cho tồn tại đúng một gitrong mỗi lớp kề trái của H và đúng một gitrông mỗi lớp kề phải.
3: Richard Rado chứng minh mở rộng quan trọng sau đây của định lý Hall cho matroid: Giả sử Ailà họ các tập con của tập hữu hạn S được đánh số bởi tập I và M là matroid trên S: Khi đó tồn tại một hệ đại diện riêng biệt gồm các phần tử độc lập nếu và chỉ nếu AJ có hạng ít nhất là jJ j với mọi J I: Như một hệ quả ví dụ, nếu A1; A2; : : : ; An là các tập
31
Tạp chí Epsilon, Số 08, 04/2016
con của một không gian véc-tơ V có n chiều sao cho dim span AJ > jJ j với mọi tập con J 2 f1; 2; : : : ; ng; thì V có cơ sở fa1; a2; : : : ; ang với ai 2 Ai với mọi i:
4: Có một phiên bản của định lý Hall về hôn nhân cho siêu đồ thị được phát biểu bởi Aharoni và Haxell trong đó có đưa ra một chứng minh mới của định lý Hall dựa trên bổ đề Sperner (bổ đề này lại tương đương với định lý điểm bất động Brouwer trong tô-pô). Xem bài blog Œ3 của Gil Kalai để biết rõ hơn.
5: Có một số kết quả nổi tiếng trong tổ hợp mà đều “tương đương” nhau, theo nghĩa là chúng có thể suy ra được từ nhau một cách khá đơn giản. Đó là định lý Hall về hôn nhân, định lý Dilworth, định lý luồng cực đạt lát cắt cực tiểu và định lý Menger. Một đặc điểm chung của tất cả các định lý này là một vài điều kiện cần hiển nhiên thấy lại chính là điều kiện đủ. Có thể xem ở đây Œ4:
6: Một số bài toán yêu thích của tôi liên quan đến bài toán hôn nhân là bài toán hôn nhân ổn định và bài toán thư ký.
7: Định lý Hall đóng vai trò chủ đạo trong bài báo sau Œ5 của Zur Izhakian và Louis Rowen về supertropical matrix algebra.
8: Định lý Hall về hôn nhân có thể được hiểu như điều kiện cần và đủ để tồn tại cặp ghép đầy đủ cho một đồ thị hai phe. Tutte đã chứng minh mở rộng sau đây cho một đồ thị bất kỳ, không nhất thiết phải là hai phe: Một đồ thị G có cặp ghép đầy đủ khi và chỉ khi với mọi tập con U các đỉnh, đồ thị cảm sinh trên phần bù của U có tốt đa jUj thành phần liên thông với số đỉnh lẻ. Từ định lý Tutte ta có thể nghĩ đến một định nghĩa thoáng hơn về “hôn nhân”.
Tài liệu tham khảo
[1] https://www.ima.umn.edu/preprints/Feb92Series/918.pdf [2] http://kskedlaya.org/putnam-archive/2012s.pdf
[3] https://gilkalai.wordpress.com/2012/11/25/
happy-birthday-ron-aharoni/
[4] http://robertborgersen.info/Presentations/GS-05R-1.pdf [5] http://arxiv.org/abs/0806.1178
32
VỀ HẰNG SỐ LIÊN THÔNG TRÊN
LƯỚI TỔ ONG
Huỳnh Công Bằng - Ecole Normale Supérieure de Lyon
Hằng số liên thông trên một mạng lưới là đại lượng liên quan đến số lượng đường đi không tự cắt trên lưới đó (lưới có thể là ô vuông, hay lục giác (lưới tổ ông), ...) Vào năm 1982, một lập luận dựa trên gas coulomb của Nienhuis dự đoán rằng trên mạng lưới lục giác, hằng số liên thông
q
bằng
2 Cp2. Điều này đã được chứng minh chi tiết bởi Duminil-Copin và Smirnov bằng cách
sử dụng phương pháp "parafermionic".
1. Giới thiệu
Ký hiệu cn là số đường đi không tự cắt (SAW) trên mạng lưới lục giác H với độ dài n và bắt đầu
từ O. Ta có:
cn .p2/n
Điều này có được bằng cách đếm số đường đi lên phía trên và đi xuống phía dưới ở bước thứ 2k C 1 và số đường đi ngang ở bước thứ 2k C 2 với k 2 N.
Ta có thể cắt một đường đi SAW có độ dài m C n thành hai phần SAW có độ dài n và m. Do đó cmCn cm cn:
Theo bổ đề subadditivity, ta có
lim c1nn D 2 p2; 2 and cn n;8n
vì D limnc1nn D infn.c1nn /.
q
Định lý 1. Đối với mạng lưới lục giác, ta có D 33
2 Cp2.
Tạp chí Epsilon, Số 08, 04/2016
Một vài ký hiệu: Ta sẽ làm việc trên những trung điểm của các cạnh của H. Tập hợp tất cả những điểm đó là H˘.
Ta viết a 2 H˘; W a ! E nghĩa là bắt đầu tại a và kết thúc tại một điểm trong E H˘. l. / D #fa 2 H W a 2 g là độ dài của (Vì là số các đỉnh thuộc ).
Ta định nghĩa hàm số sau đây:
z.x/ DX
xl./ for x > 0:
Wa!H˘
Ta co
z.x/ DX
xl./ DX
cn xl./ DX
cn xn X
. x/n:
Do đó,
Wa!H˘
n
n
n
If x <1 then z.x/ < C1:
If x >1 then z.x/ D C1.
Khi đó, ta chỉ cần chứng minh
z.x/ < C1 if x <1
p
2 Cp2
va
z.x/ D C1 if x D1
2 Cp2:
p
ta dat xc D1
2 Cp2voi j D e2i
3 .
2. Cầu
p
Trong mục này, ta định nghĩa một lớp của SAW là cầu và ta sẽ chứng minh rằng số cầu sẽ tăng tỉ lệ với số SAW ( n) và từ đó ta có thể chứng minh rằng
q
b.H / D
2 Cp2:
Định nghĩa 1. Một cầu n-bước là một SAW có n-bước sao cho
1.0/ < 1.i / 1.n/8i D 1; 2; 3; : : : ; n:
trong đó 1.i / là tọa độ đầu tiên .i /. 34
Tạp chí Epsilon, Số 08, 04/2016
Ký hiệu bn à một cầu n-bước với .0/ D 0. Ta đặt b0 D 1:
Ta có bmCn bm bn, do đó
n!C1bn1n D supnb1nn :
b D lim
Hơn nữa, bnn nb n.
Định nghĩa 2. Một nửa mặt phẳng n-bước là một SAW có n bước với 1.0/ < 1.i /;8i: Ta đặt hn là số lượng nửa mặt phẳng n bước với .0/ D 0:
Định nghĩa 3. Độ dày của nửa mặt phẳng n bước là
0 i n1.i / min
max
với bn;A là số n-bước cầu với độ dài A:
0 i n1.i /
Ta có bn DXn AD1
bn;A.
Định lý 2. (Hardy-Ramanujan): Cho n 2 N , gọi PD.n/ là số cách để viết n D n1Cn2C Cnk trong đó n1 > n2 > > nk 1 cho bất kỳ k, khi đó, ta có
lnPD.n/
n 3
12as n ! C1:
Mệnh đề 1. hn PD.n/ bn với mọi n 1.
Đặt b0 D 0, ta định nghĩa
j >ni.1/i.1.j / 1.ni//
AiC1 D max
va
n
niC1 D max
j > ni.1/i.1.j / 1.ni// D AiC1o:
Nghĩa là: n1 là giá trị cực đại của 1.j / W j > n0 và n2 là giá trị cực tiểu của 1.j /; j > n1. Ta đặt hn.a1; a2; : : : ; ak/ là số nửa mặt phẳng n bước với
K D k; Ai D ai:
Ta cóhn.a1; a2; : : : ; ak/ hn.a1 C a2; a3; : : : ; ak/
: : :
hn.a1 C a2 C C ak/ D bn;a1Ca2C Cak:
Do đó,
hn DX k 1
X
k 1
X
1 a1
2 3
12, khi đó, tồn tại một hằng số n0.B/ sau cho
8n > n0.B/ W cn bnC3 eBpnC3:
Chứng minh. Ta sẽ chứng minh rằng
hnm hmC4:
Đặt x1 D max
cn Xn mD0
0 i n1.i /; m D maxfi W .i / D x1g. Ta xóa đi .m/ và thêm vào 5 điểm giữa a1; a2; a3; a4; a5 của lục giác chứa .m/:
Đường đi này ..0/; .1/; : : : ; .m 1/; a1; a2; a3; a4/ là một nửa mặt phẳng có .m C 3/ bước và .a5; .m C 1/; : : : ; .n// là một nửa mặt phẳng có .n m/ bước. Do đó,
hnm hmC3
Sử dụng mệnh đề:
cn Xn mD0
cn Xn mD0
hnm hmC3 Xn mD0
PD.n m/ PD.m C 3/ bnm bmC3
Xn mD0
PD.n m/ PD.m C 3/ bnC3
Theo định lý Hardy thì: PD.n/
n
12khi n ! C1, do đó 9˛ W PD.n/ ˛eB0 .A2 /12với
B > B0 >
2 3
12.
3
chúng ta có được:
PD.n m/ PD.m C 3/ ˛2eB0
hpnm 2 C
p mC3 2
i
˛2eB0pnC3;
Do đó: và
cn .n C 1/˛2eB0pnC3 bnC3
9B0.B/;8n B0.B/ W cn eBpnC3bnC3:
Hệ quả 1. .H / D b.H /.
36
Tạp chí Epsilon, Số 08, 04/2016 Ta có:
nC3 nC3
n b1
n
nC3 ) b
nên D b.
cn eBpnC3bnC3 ) c1nn eBpnC3
Ghi chú. Chúng ta có cùng kết quả cho mạng hình vuông Z2bằng cách thay thế n C 3 bởi n C 1:
Cố định B > n n0.
2
12khi đó có một giá trị n0 D n0.B/ sao cho cn bnC1eBpnvới mọi 3
Chúng ta định nghĩa B.x/ DXbnxn, như vậy
Nếu x >1 : B.x/ D C1
Nếu x <1 : B.x/ < C1.
3. Parafermionic
Một miền là hợp của tất cả các trung điểm từ việc đưa ra một tập hợp của các đỉnh V ./. Một trung điểm z sẽ thuộc về miền nếu ít nhất một đầu mút của cạnh liên kết của trung điểm này thuộc về V ./. Trung điểm này thuộc về @ nếu chỉ có duy nhất một đầu mút là nằm trong V ./
Định nghĩa 4. Số gốc quay W .a; b/ của một SAW giữa a và b là số lần rẽ sang trái của trừ đi số lần rẽ sang phải của , lấy kết quả nhân với 3. khi đi từ a đến b. Định nghĩa 5. Cho a 2 @; z 2 ; chúng ta đặt
F .z/ D F .a; z; x; / DX
ei W .a;z/xl./:
Wa!z
Bổ đề 1. Nếu x D xc; D58, khi đó F thỏa mãn:
8v 2 V ./ W .p v/F .p/ C .q v/F .q/ C .r v/F .r/ D 0 trong đó p; q; r là 3 cạnh liên kết đến v:
Chứng minh. Ta viết
.p v/F .p/ C .q v/F .q/ C .r v/F .r/
D.p v/ X
ei W .a;p/xl./ C .q v/ X
ei W .a;q/xl./C
Wa!p
Wa!q
.r v/ X
ei W .a;r/xl./
Wa!r
trong đó p; q; r là 3 trung điểm theo thứ tự ngược chiều kim đồng hồ xung quanh v: 37
Tạp chí Epsilon, Số 08, 04/2016
Ta kí hiệu:
Cp D f W W a ! pg
Cq D f W W a ! qg
Cr D f W W a ! rg
vàC3p D˚ 2 Cp W đi qua q và r
C2p D˚ 2 Cp W chỉ đi qua q và r
C1p D˚ 2 Cp W không đi qua q cũng không đi qua r
Ta có 3 trường hợp:
1. If 2 C3n, ta liên kết đến e, được định nghĩa bởi: e đi qua cùng những trung điểm mà đi qua và thêm vào đường p ! r vào e. Đặc biệt, e 2 C3p.
2. nếu 2 C1p, ta liên kết đến Q và QQ đi qua 2 trung điểm (p; q or p; r ) bằng cách mở rộng đường đi thêm một bước.
3. nếu 2 C2p, nó là trong trường hợp 2 C1por C1r,
Ta định nghĩa: Nếu một đường kết thúc tại trung điểm z, C. / D .z v/ei w .a;z/xl./. Trong những lập luận tiếp theo, chúng ta sẽ xem xét một vài trường hợp: 1. Trường hợp đầu tiên, chúng ta sẽ chứng minh rằng
xl./
c .p v/ei w .a;p/ C .q v/ei w .a;q/xl./Q
c D 0
We have l. / D l. /; .q Q v/ D e2i
3 .p v/ và
w .a; p/ D w .a; r/ C w .r; p/ D w .a; r/ C
4 3
Do đó
wQ .a; p/ D wQ .a; r/ C wQ .r; p/ D wQ .a; r/ C4 3D w .a; r/ C4 3 xl./
c .p v/ei w .a;p/ C .q v/ei w .a;q/xl./Q
c
D .p v/ei Œw .a;r/4 3 C e2i
h
6 C e2i
3 .p v/ei Œw .a;r/C4 3 i
D
.p v/e 5i
3 .p v/e5i
6
0
e5i8 w .q;r/ 1
D .p v/e5i8 w .a;r/
@e5i
6 C ei 6
„ ƒ‚ … 0
A D 0
2. Trường hợp thứ 2, chúng ta sẽ chứng minh rằng
c. / C c. /Q C c.Q /Q D 0
Nói cách khác,
c C .r v/ei w QQ.a;r/xl. Q/Q
c.p v/ei w .a;p/ C .q v/ei wQ .a;q/xl./Q
xl./
c D 0
38
Tạp chí Epsilon, Số 08, 04/2016 Ta có
và
l. /Q D l.Q /Q D l. / C 1
wQ .a; q/ D wQ .a; p/ C wQ .p; q/ D w .a; p/ C
;
3
wQQ.a; r/ D wQQ.a; p/ C wQ .p; r/ D w .a; p/ C 3 3 ; r v D .p v/e2i
q v D .p v/e 2i
Ta viết lại như sau:
xl./
3
c C .r v/ei w QQ.a;r/xl. Q/Q
c.p v/ei w .a;p/ C .q v/ei wQ .a;q/xl./Q , 1 C xce2i
3 ei 3 58 C xce2i
3 ei5
c D 0
24 D 0
, xc
e7i
8 C e7i
C 1 D 0
8
, 2 cos 8xC C 1 D 0
p
, cos 8D12xCD
2 Cp2 2
q
Điều này là đúng bởi vì
2 Cp2 D 2 cos 8. Bổ đề đã được chứng minh
Ghi chú 1) Chúng ta có thể thấy .1/ giống như là tích phân rời rạc theo đường tam giác trên một mạng lưới theo nghĩa sau đây. Gọi H là mạng lưới "dual" của H. Một đường:
W f0; 1; 2; : : : ; ng ! H
(v 2 H nếu và chỉ nếu v là tâm của các mặt của H).
I
F W H˘ ! C là một hàm trên H: Chúng ta định nghĩa:
F .z/dz WD Xn1 iD0
F
i C iC1 2
.iC1 i/.
If .0/ D a; .1/ D b; .2/ D c; .3/ D a và F giống như trong định nghĩa 5, khi đó ta có
I
F .z/dz D .b a/F
a C b 2
C .c b/F
b C c 2
C .a c/F
a C c 2
D 2e 2 .p v/F .p/ C 2ei 2 .q v/F .q/ C 2ei 2 .r v/F .r/
D 0
Tổng quát hơn, nếu W f0; 1; 2; : : : ; ng ! H sao cho .0/ D .n/. Chúng ta phân tích thành những đường tam giác. Ta có:I
F .z/dz D 0:
2) Những mối quan hệt này thì không thể xác định được duy nhất hàm F như trong định nghĩa, bởi vì số biến là lớn hơn số phương trình. Chúng ta có thể đưa ra hai hàm mà thỏa mãn mối quan hệt này:
F .z/ D 0;8z 2 H
F .z/ D 1;8z 2 H
39
Tạp chí Epsilon, Số 08, 04/2016
4. Chứng minh định lý
Chúng ta cố định a 2 H˘giống như là gốc tọa độ của mặt phẳng phức.Chúng ta xem xét một miền dọc D ST được tạo thành từ T dãy lục giác, và phiên bản hữ hạn ST;L cắt tại độ cao ˙L và góc ˙ 3. Chúng ta sẽ xác định V .ST / và V .ST;L/.
Định nghĩa ˛; ˇ tương ứng là những biên bên trái, bên phải ST and ; là những biên phía trên và phía dưới của ST;L
Chúng ta có
8z 2 ˇ;Re z D3T C 1 2:
Biên phía trên thuộc về đường thẳng có phương trình p3y x D 3L C12. Biên phía dưới thuộc về đường thẳng có phương trình p3y x D 3L 12.
Do đó
V .ST / D
z 2 V .H / W 0 Re z 3T C 1 2
V .ST;L/ D
n
z 2 V .H / W
ˇˇˇp3 Im.z/ Re.z/ˇˇˇ 3Lo
Chúng ta định nghĩa
AT;L.x/ DX
xl./
ST;LWa!˛nfag
BT;L.x/ DX
xl./
ST;LWa!ˇ
ET;L.x/ DX
xl./
Bổ đề 2. For x D xC ; D58, Ta có
ST;LWa! [
c˛AT;L.xc/ C BT;L.xc/ C c ET;L.xc/ D 1
trong đó c˛ D cos3 8; c D cos 4.
Chứng minh. Chúng ta đã chứng minh rằng: Nếu x D xc; D58khi đó 8v 2 V ./ W .pv v/F .pv/ C .qv v/F .qv/ C .rv v/F .rv/ D 0
trong đó pv; qv; rv là những trung điểm của 3 cạnh liên kết đến v:. Chúng ta cộng những mối quan hệ này trên tất cả cách đỉnh v 2 V .ST;L/ khi đó
X z2ˇ
F .z/ CX z2
3 F .z/ CX
e2i
z2˛
ei F .z/ CX z2
e2i
3 F .z/ D 0
e2i
3 F .z/ D 0
đặc biệt,
)X z2ˇ
F .z/ CX z2
3 F .z/ C .1/X
e2i
z2˛
F .z/ CX z2
40
Tạp chí Epsilon, Số 08, 04/2016
.1/X z2˛
F .z/ D 1 ei C ei
2AT;L.xc/ D 1 cos5 8AT;L.xc/ D 1 C
cos3 8AT;L.xc/
X z2ˇ
F .z/ D ei 0BT;L D BT;L .
e2i
X
X
F .z/ D e2i
3 X
3 X
3
z2
F .z/ C e2i
3
z2
3 e2i
3 e2i
c C e2i
xl./
Wa!
xl./
c
Wa!
D e i4X
c C e i4X xl./
c D12 e i4 C e i4 ET;L.xc/ D cos 4ET;L.xc/ xl./
Do đó, ta có
Wa!
Wa!
cos3 8AT;L.xc/ C BT;L.xc/ C cos 4ET;L.xc/ D 1:
Chú ý. Chúng ta nhận thấy rằng .AT;L.xc//Land .BT;L.xc//Llà những dãy tăng, khi đó L!C1AT;L.xc/ D AT .xc/ and lim
lim
L!C1BT;L.xc/ D BT .xc/:
ta có
cos3 8AT;L.xc/ C BT;L.xc/ C cos 4ET;L.xc/ D 1
và .AT;L.xc//L;.BT;L.xc//Llà những dãy tăng, do đó ET;L.xc/ là một dãy giảm, điều này suy ra rằng
L!C1ET;L.xc/ D ET .xc/:
lim
Ta có cos3 8AT .xc/ C BT .xc/ C cos 4ET .xc/ D 1.
Bây giờ, chúng ta sẽ trình bày phần chứng minh định lý.
Trong phần 2, chúng ta đã chỉ ra rằng b.H / D .H /. Do đó, chỉ cần chứng minh rằng z.xc/ D C1 và B.x/ < C1;8x < xc.
1. Chứng minh rằng z.xc/ D C1:
Chúng ta xem xét 2 trường hợp:
C1
If 9T0 W ET0.xc/ > 0 do đó z.xc/ X
C1
ET;L.xc/ X
ET0.xc/ D C1. Bởi vì
.ET0;L.xc//Llà một dãy giảm. 41
LD1
LD1
Tạp chí Epsilon, Số 08, 04/2016
If 8T W ET .xc/ D 0, then we have cos3 8AT .xc/ C BT .xc/ D 1 với mọi T: Dễ dàng chứng minh rằng
AT C1.xc/ AT .xc/ zcBT C1.xc/2
do đó
cos3 8AT C1.xc/ C BT C1.xc/ cos3 8AT .xc/ BT .xc/ D 0
, 0 D cos3 8ŒAT C1.xc/ AT .xc/ C BT C1.xc/ BT .xc/
cos3 8xcBT C1.xc/2 C BT C1.xc/ BT .xc/
Kí hiệu cos3 8D c˛, ta có
c˛xcBT C1.xc/2 C BT C1.xc/ BT .xc/:
Chúng ta sẽ chứng minh rằng
BT .xc/ mi n
B1.xc/; 1 c˛xc
1
T:
Giả sử rằng tồn tại T0 sau cho BT0.xc/ < min
B1.xc/; 1 c˛xc
1
T0, khi đó chúng ta có
c˛xcBT0.xc/2 C BT0.xc/ BT01.xc/ ) BT01.xc/ c˛xcBT0.xc/2 C BT0.xc/
< min
B1.xc/; 1 c˛xc
1
T0C c˛xc min
B1.xc/; 1 c˛xc
21 T20
min
B1.xc/; 1 c˛xc
1
T0C min0
B1.xc/; 1 c˛xc
1
1 T20
min
B1.xc/; 1 c˛xc
BBBBB@1T0C1T20 „ ƒ‚ … < 1
T01
CCCCCA
Bằng cách tương tự, ta có
BT02.xc/ < min
B1.xc/; 1 c˛xc
1
T0 2
: : :
B1.xc/ < min
B1.xc/; 1 c˛xc
B1.xc/
42
Tạp chí Epsilon, Số 08, 04/2016
bất đảng thức cuối cùng là một sự mâu thuẫn, do đó
then
BT .xc/ minC1
B1.xc/; 1 c˛xc
1
Tfor all T; X
z.xc/ X T D1
BT .xc/ min
B1.xc/; 1 c˛xc
C1 T D1
1
TD C1
2. Chứng minh của B.x/ < C1;8x < xc.
Giả sử rằng x < xc. Vì BT .x/ là một cầu có độ dài ít nhất T nên
BT .x/ DXxl./ X.xxc/l. /xl./ X.xxc/Txl./ xxc TBT .xc/ xxC T bởi vì BT .xc/ 1. Như vậy,
T
< C1
bởi vì x < xc.
C1
B.x/ DX T D1
C1
BT .x/ X T D1
x xc
5. Mô hình vòng O.n/ trên mạng lưới lục giác:
Cho là một đồ thị con của mạng lưới lục giác, chúng ta xem xét cấu hình của những vòng đơn giản không tự cắt . Cho n 0; x > 0: Chúng ta định nghĩa độ đo trên tập hợp X của cấu hình những vòng đơn không tự cắt:
P.!/ n#loop.!/x#edges.!/:
Kể từ đó, một phần giao giữa 2 vùng sẽ được thêm vào. Trong trường hợp này, cấu hình sẽ được hợp giữa các vòng không tự cắt và giao diện tránh các vòng từ a vào b. Chúng ta sẽ mở rộng định nghĩa của "paraforminoic observable" trong phần 3.
Định nghĩa 6. Cho u; v 2 @; z 2 ; n 2 Œ0I 2; x > 0, ta định nghĩa
F .z/ D F .z; u; v; x; n; / D
P
!2 .u;z/ P
!2 .u;v/
ei w .u;z/xj!jn#loop.!/ ei w .u;v/xj!jn#loop.!/
trong đó .u; v/ là một tập hợp của những cấu hình với giao diện (SAW ) từ u đến v: Ghi chú. Cho u; v cố định, chúng ta đặt
ei w .u;v/xj!jn#loop.!/;
khi đó chúng ta có
c DX !2 .u;v/
F .z/ D F .z; u; v; x; n; / D1cX
!2 .u;z/
với quy ước 00 D 1 và cho n D 0, ta có:
43
ei ! .u;z/xj!jn#loop.!/
Tạp chí Epsilon, Số 08, 04/2016
Nếu #loops.!/ > 0 then P.!/ D 0.
Nếu #loops.!/ D 0 then P.!/ x#edges.!/.
Nghĩa là X D fSAW g.
Mệnh đề 2. Gọi là một miền hữu hạn của H và a; b 2 @. Đặt x.n/ D1
2 Cp2 nvà
p
.n/ D 1 34 arccos n12 và F là "paraformionic observable" khi đó .p v/F .p/ C .q v/F .q/ C .r v/F .r/ D 0
trong đó p; q; r là 3 trung điểm của những cạnh liên kết đến v:
Ghi chú: Nếu n D 0 then x D1
2 Cp2; D58. Điều này đã được chứng minh trong bổ đề 1. p
Chứng minh. Chúng ta có thể liên kết cấu hình 1; 2 và 3 (4; 5; 6) Cố định một trường hợp (trường hợp 1; 2; 3) Chúng ta sẽ chứng minh rằng: C.1/ C C.2/ C C.3/ D 0:
Nói cách khác,
n.p x/e w.u; p/n#loops.!1/ C xj!2j
xj!1j
C xj!3j
n.q x/e w2.u;q/n#loops.!2/
n.r x/e w3.u;r/n#loops.!3/ D 0
trong đó j!2j D j!3j D j!1j C 1 và
#loops.!1/ D #loops.!2/ D #loops.!3/;
w2.a; q/ D w2.a; p/ C w2.p; q/ D w1.a; p/ C
;
3
w3.a; r/ D w .a; p/ C 3
q v D .p v/e 2i
3 ; r v D .p v/e2i
3
44
Tạp chí Epsilon, Số 08, 04/2016
Chúng ta viết lại
xj!1j
n.p v/ei w1.u;p/n#loops.!1/
C xj!2j
n.q v/ei w2.u;q/n#loops.!2/
C xj!3j
n.r v/ei w3.u;r/n#loops.!3/
D xj!1j
n.p v/ei w1.u;p/n#loops.!1/
n.p v/e 2i
C xj!1jC1
3 ei Œw1.u;q/ 3n#loops.!2/
h
n.p v/e2i
w1.u;p/C 3in#loops.!3/
C xj!1jC1
Nó thì dễ để chứng minh rằng 1 C e2i
3 ei
3 xnei
3 C xne2i
3 ei
1 34 arccos n2 and xn bởi 1
3 D 0. Chúng ta thay thế by
p
3 xnei
3 C xne2i
2 Cp2 n, khi đó ta có
1 C e2i
3 ei
3
3 ei 3 i4arccos.n2 /1
3 ei4arccos.n2 /1
D 1 C e2i
p
2 Cp2 nC e2i 3 ei
p
2 Cp2 n
D 1 ei4arccos.n2 /1
p
2 Cp2 n ei4arccos.n2 /1
p
2 Cp2 n
1
n
1
1
n
1
D 1 cos
4arccos
2
p
2 Cp2 n cos
4arccos
2
p
2 Cp2 n
D 1 2 cos14arccosn2
p
điều này là đúng.
2 Cp2 nD 0
6. Giả thuyết cho mô hình O(n)
Định nghĩa của sự biến đổi pha thì tương ứng đến sự tồn tại của xc 2 .0I C1/ sao cho
1. Cho x < xc: Xác suất để mà đỉnh a và b là trên cùng một vòng giảm nhanh như lũy thừa theo khoảng cách giữa a và b:
2. Cho x > xc: Xác suất để mà những đỉnh a và b là nghịch đảo của lũy thừa theo khoảng cách giữa a và b:
Giả thuyết: Cho n 2 Œ2I 2, khi đó xc.n/ D1
p2 Cpx n.
Tài liệu tham khảo
[1] Hugo Duminil-Copin, Parafermionic observables and their applications to planar statistical physics models.
45
Tạp chí Epsilon, Số 08, 04/2016
[2] Hugo Duminil-Copin, Smirnov: The connective constance of the honeycomb lattice equals
q
2 Cp2.
[3] Hugo Duminil-Copin, R. Bauerschmidt, J. Goodman, G. Slade, Leture on the self-avoiding walks.
[4] Hugo Duminil-Copin, N. R. Beaton, Mireille Bousquet-Mélou, Jan de Gier, Anthony J. Guttmann, The critical fugacity for surface adsorption of self avoiding walks on the money
comb lattice is 1 Cp2.
46
RỘNG HẸP NHỎ TO VỪA VẶN CẢ (GIỚI THIỆU TÔPÔ HỌC)
Nguyễn Hữu Việt Hưng
(Trường ĐH Khoa học Tự nhiên, ĐHQG - Hà Nội)
Có những vấn đề của hình học, nhưng lại không phụ thuộc vào kích cỡ to nhỏ, rộng hẹp, dài ngắn của các đối tượng liên quan. Những vấn đề như thế thuộc về một lĩnh vực được gọi là Tôpô học (Topology1). Trong những vấn đề thuộc loại này, chuyện một mảnh đất rộng hay hẹp, vuông hay méo chẳng quan trọng gì. (Thế có lạ không!) Vì thế, những người buôn đất, buôn bất động sản chớ nên học Tôpô. Nếu như vì tò mò mà họ cứ học, họ thể nào cũng cả quyết rằng các nhà Tôpô học là những kẻ điên, hâm hấp.
Cao đàm khoát luận như thế không khéo dễ dẫn đến tư biện, mù mờ, rồi dễ sinh ra nói nhảm. Để tránh chuyện đó, ta hãy bắt đầu bằng một vài ví dụ. Đôi khi, vài ví dụ thực chất có thể đẻ ra một lý thuyết, có khi còn đẻ ra cả một ngành học.
Leonhard Euler (1707 - 1783), nhà toán học vĩ đại người Thuỵ Sĩ, được xem là cha đẻ của ngành Tôpô học, vì ông là người đầu tiên nghiên cứu hai bài toán sau đây.
1. Bài toán về bảy chiếc cầu
Konigsberg là một thành phố cổ thuộc ¨ Vương quốc Phổ và nước Đức cho đến 1945. Sau Đại chiến Thế giới II, nó thuộc Liên Xô (cũ) rồi Nga, và được gọi là Kaliningrad. Chỉ có rất ít dấu tích của Konigsberg còn sót lại ngày nay ở Kaliningrad. ¨
Ở thành phố Konigsberg, có ¨ 7 chiếc cầu. Chúng nối hoặc là hai bờ sông, hoặc một bờ sông và một trong hai cù lao, hoặc nối hai cù lao đó. Xem bản đồ sau đây:
1Tất cả các liên kết trong bài đều của Ban Biên tập.
47
Tạp chí Epsilon, Số 08, 04/2016
Từ xưa, cư dân ở Konigsberg đã đặt câu hỏi: Liệu có thể đi một lần qua tất cả ¨ 7 chiếc cầu mà không có cầu nào phải lặp lại hay không?
Không cần để tâm nhiều lắm đến vị trí cụ thể của 7 chiếc cầu. Điều quan trọng nhất mà người ta quan sát được từ bài toán này là như sau: Đây là một vấn đề của hình học, nhưng không phụ thuộc vào độ lớn của các yếu tố tham dự (dòng sông rộng hay hẹp; những chiếc cầu dài hay ngắn, to hay bé; các cù lao lớn nhỏ thế nào). Vấn đề chỉ phụ thuộc hình dáng và vị trí tương đối của các yếu tố.
Không có bằng chứng nào còn lại chứng tỏ rằng Euler đã tới Konigsberg. Tuy nhiên, năm 1735 ¨ ông đã chứng minh rằng mong muốn tìm một cách đi qua cả 7 chiếc cầu “một lần, không lặp lại” là không thể thực hiện được.
Chúng ta thử tìm hiểu lời giải của Euler cho bài toán 7 cây cầu. Trên bản đồ Konigsberg hãy thay ¨ mỗi bờ sông, mỗi cù lao bằng một điểm, gọi là đỉnh, thay mối chiếc cầu bằng một đường nối các đỉnh, gọi là cạnh. Hình thu được gọi là một đồ thị. Bài toán về 7 cái cầu ở Konigsberg thực chất ¨ là chuyện cố gắng “vẽ bằng một nét” đồ thị sau đây:
Bài toán này rất quen thuộc với trẻ em qua trò chơi “vẽ hình bằng một nét”. Có ai thuở thiếu thời lại chẳng đã từng đau đầu với câu đố vẽ cái phong bì chỉ bằng một nét?
48
Tạp chí Epsilon, Số 08, 04/2016
Hãy bắt đầu với nhận xét đơn giản sau đây: Mỗi khi ta đi qua một đỉnh, thì có 2 cạnh (2 cây cầu) xuất phát từ đỉnh đó đã được đi qua: Cạnh đi tới, và cạnh đi ra khỏi đỉnh đó. Như thế, mỗi lần đi qua một đỉnh, số cạnh nối với đỉnh đó mà ta chưa đi qua giảm đi 2. Cho nên, nếu một đỉnh có số cạnh nối tới là một số chẵn (gọi tắt là đỉnh chẵn) thì mỗi lần đi tới đó ta luôn còn đường để thoát ra ngoài. Còn tại mỗi đỉnh lẻ, chẳng hạn có (2k C 1) đường nối với đỉnh đó, thì sau k lần đi qua, tới lần (k C 1) ta sẽ hết đường để đi khỏi đỉnh đó.
Như vậy, các đỉnh lẻ chính là các cản trở cho việc “đi qua” mà không phải dừng lại. Chiến thuật của ta là không xuất phát từ các đỉnh chẵn (nếu vẫn còn đỉnh lẻ), vì nếu xuất phát từ một đỉnh chẵn, khi đi khỏi đỉnh đó, chúng ta sẽ biến đỉnh chẵn này thành một đỉnh lẻ trong phần tiếp theo của trò chơi.
Ta chỉ cần xét các đồ thị liên thông, nghĩa là đồ thị mà giữa 2 đỉnh bất kỳ của nó đều có ít nhất một đường nối. (Việc vẽ một đồ thị không liên thông hiển nhên qui về vẽ từng thành phần liên thông của nó.) Dựa trên những nhận xét về đỉnh chẵn và đỉnh lẻ nói trên, ta có thể chứng minh:
(1) Trong mỗi đồ thị, số các đỉnh lẻ luôn là một số chẵn,
(2) Một đồ thị liên thông không có đỉnh lẻ nào, cần tối thiểu 1 nét vẽ.
(3) Một đồ thị liên thông có 2n đỉnh lẻ (n > 0), cần tối thiểu n nét vẽ.
Cách vẽ như sau: Xuất phát từ một đỉnh lẻ bất kỳ (nếu có), vẽ tuỳ ý cho đến khi không vẽ được nữa. Khi đó ta gặp một đỉnh lẻ khác. Nét vẽ vừa rồi khử bớt 2 đỉnh lẻ (là điểm đầu và điểm cuối của nét vẽ). Lặp lại quá trình trên cho đến khi không còn đỉnh lẻ nào. Trường hợp không có đỉnh lẻ nào, hãy xuất phát từ một đỉnh chẵn bất kỳ, vẽ tuỳ ý cho đến khi không vẽ dược nữa. Khi đó ta gặp lại đỉnh xuất phát.
Chúng tôi không đi sâu vào chi tiết chứng minh những khẳng định trên.
Cái phong bì có 5 đỉnh, trong đó 4 góc là 4 đỉnh lẻ. Vì thế, không thể vẽ phong bì bằng 1 nét. Cần ít nhất 4=2 D 2 nét để vẽ được phong bì.
Trong bài toán 7 cây cầu ở Konigsberg, có bốn đỉnh, đều là các đỉnh lẻ. Do đó, không thể vẽ ¨ đồ thị đó bằng 1 nét. Tối thiếu cần 4=2 D 2 nét. Đó là lý do trong suốt chiều dài lịch sử, không người dân nào ở Konigsberg có thể đi một lần qua tất cả các cây cầu mà không chiếc cầu nào bị ¨ lặp lại.
49
Tạp chí Epsilon, Số 08, 04/2016
2. Bài toán về số mặt, số cạnh, và số đỉnh của một đa diện
L. Euler đã chứng minh định lý sau đây, thoạt nhìn tưởng như trò chơi trẻ con: Trong bất cứ đa diện lồi nào, số mặt trừ đi số cạnh cộng với số đỉnh đều bằng 2.
Hãy lấy vài ví dụ.
Trong một tứ diện, số mặt m D 4, số cạnh c D 6, số đỉnh d D 4;
Ta có m c C d D 4 6 C 4 D 2.
Trong một hình hộp chữ nhật, số mặt m D 6, số cạnh c D 12, số đỉnh d D 8; Ta cũng có m c C d D 6 12 C 8 D 2.
Vì sao lại có chuyện lúc thì lấy dấu “cộng”, lúc lại lấy dấu “trừ” trong định lý trên? Xin thưa: Mặt là một yếu tố 2 chiều, đỉnh thì 0 chiều, những yếu tố chẵn chiều thì được mang dẫu cộng; còn cạnh là một yếu tố 1 chiều, tức số chiều lẻ, nên nó mang dấu trừ.
Giống như bài toán về 7 chiếc cầu, bài toán này cũng là một vấn đề hình học, nhưng không phụ thuộc vào độ lớn các yếu tố. Thật vậy, một đa diện dù bé như hạt đậu hay to như trái đất thì số mặt, số cạnh, và số đỉnh của nó cũng không thay đổi. Nhận xét trên gợi ý cho suy luận sau đây: Hãy tưởng tượng đa diện lồi được làm bằng cao su. Ta hãy thổi phồng đa diện lồi đó thành một quả bóng hình cầu.
50
Tạp chí Epsilon, Số 08, 04/2016
Các mặt, cạnh, và đỉnh của đa diện biến thành các mặt (cong), cạnh (cong), và đỉnh trên mặt cầu. Như thế, định lý trên của Euler về bản chất là một định lý về mặt cầu: Trong mọi cách phân mặt cầu thành các hình đa giác cong, số mặt trừ số cạnh cộng số đỉnh đều bằng 2. Hơn nữa, mọi hình thu được từ mặt cầu bằng một phép biến đổi liên tục (tương tự như co dãn màng cao su) đều nghiệm đúng định lý này.
Chúng ta vừa đạt được một bước tiến quan trọng trong cách nghĩ: Bài toán của Euler ban đầu xét rất nhiều đối tượng, là bất cứ đa diện lồi nào. Rút cuộc, nó là một bài toán về chỉ một đối tượng duy nhất, đó là mặt cầu.
Đạt được bước tiến đó là do chúng ta sử dụng lập luận về các biển đổi kiểu “co dãn cao su”. Người ta gọi đó là các phép biến đổi tôpô.
Bây giờ, thay cho mặt cầu đã nói ở trên, hãy lấy mặt xuyến (cái săm ôtô) làm thí nghiệm. Có thể phân chia cái săm bằng 2 đường (c D 2), một đường cắt theo vết măng-xông, đường kia cắt dọc toàn bộ chiều dài xăm. Hai đường này cắt nhau tại một điểm duy nhất (d D 1). Bị cắt hai đường đó, săm trở thành một mặt hình chữ nhật (m D 1). Vậy, số mà Euler quan tâm của mặt xuyến (săm) là m c C d D 1 2 C 1 D 0.
51
Tạp chí Epsilon, Số 08, 04/2016
Tiếp theo, hãy lấy một mặt “xuyến kép”, có được bằng cách dính 2 chiếc săm ôtô vào nhau. Bạn hãy tự chọn một cách chia mặt “xuyến kép” thành các mặt giống như hình vuông (cong), các cạnh (cong), và các đỉnh. Chẳng hạn, ta chọn cách chia mô tả bằng hình vẽ trên. Các đường đỏ và vàng cắt nhau ở 2 điểm (1 điểm nhìn thấy, 1 điểm là hình chiếu thẳng đứng của điểm nhìn thấy), vậy d D 2. Các đường đỏ và vàng được 2 đỉnh ấy chia làm 4 cạnh (4 nửa đường tròn), cộng thêm 2 đường mầu xanh, vậy c D 6. Sau khi cắt theo các đường ấy mặt xuyến kép bị chia thành ra 2 hình chữ nhật, vậy m D 2. Ta có m c C d D 2 6 C 2 D 2. Như thế, số Euler của xuyến kép là 2.
Ta có thể dính nhiều săm ôtô với nhau để tạo thành một mặt xuyến có g lỗ. Số mà Euler quan tâm đối với mặt đó bằng m c C d D 2.g 1/.
Trong tôpô hiện đại, định lý Euler được tổng quát hoá như sau: Nếu chia bất cứ một vật thể n chiều nào thành các phần “giống như đa diện”, thì tổng số các phần với chiều chẵn trừ đi tổng số các phần với chiều lẻ luôn là một hằng số, được gọi là đặc số Euler, của vật thể đó.
Như thế, mỗi vật thể đều là sự tổng hoà nhịp nhàng của hai phần âm và dương, chẵn và lẻ nội tại của nó, không thể thay đổi. Đặc số Euler, cũng còn được gọi là đặc số Euler – Poincaré (bởi vì Poincaré (1854-1912) chính là người đầu tiên ý thức được chuyện này ở trường hợp số chiều tuỳ ý), của một vật thể chính là một loại “bản thể”, một loại “chứng minh thư”, một “ID Card” của vật thể ấy.
Hệ quả là, nếu hai vật thể có đặc số Euler khác nhau, thì chúng không thể cái này biến thành cái kia sau một phép biến đổi thuận nghịch liên tục (kiểu như co dãn cao su). Người ta nói hai vật thể đó không cùng kiểu tôpô.
Như thế, mặt cầu, mặt xuyến, và mặt xuyến kép không cùng kiểu tôpô, vì chúng có đặc số Euler khác nhau (tương ứng bằng 2, 0, và 2). Về mặt trực giác, vì sao chúng không cùng kiểu tôpô? Lý do thật đơn giản: Mặt cầu không có lỗ nào; mặt xuyến có 1 lỗ (là cái chỗ người ta vẫn chui vào để biến săm thành phao bơi); còn mặt xuyến kép có 2 lỗ. Các nhà tôpô bảo mặt xuyến có 1 lỗ, nên có giống (genus) bằng 1; mặt xuyến kép có 2 lỗ, nên có giống bằng 2; mặt cầu không có lỗ nào, nên có giống bằng 0. À ra thế, phải có lỗ thì giống mới không bị triệt tiêu. Các nhà tôpô thật giỏi ỡm ờ.
Riemann còn chứng minh một định lý thật thâm thuý: Mọi mặt 2 chiều trơn (tức mịn màng), bị chặn (có thể giữ trong một căn phòng), và có hướng (tức là phân biệt được phía nào là ngoài da, phía nào là trong thịt) đều xác định được về mặt tôpô chỉ bằng cách đếm số lỗ trên nó. Chà chà, phải mời Picasso đến đây mới được.
Những chuyện kể trên có thể dẫn chúng ta đến những gì? Sau đây là một kết luận thật khó tin.
Khẳng định: Dù có nhào nặn một cục bột, hình cái bánh mì, kỹ đến mức nào, miễn là hình của cục bột lúc đầu và khi thôi nặn vẫn là cái bánh mì, nặn xong lại để cái bánh vào đúng chỗ cũ, khi đó luôn luôn có một hạt bột mì không thay đổi vị trí.
Thật vậy, sau một phép biến đổi liên tục 2 chiều, cục bột hình cái bánh mì được biến thành một hình cầu B. Gọi S là mặt cầu bao quanh B. Khẳng định trên được chứng minh bằng các bước suy luận sau đây:
52
Tạp chí Epsilon, Số 08, 04/2016
1) Không có phép biến đổi nào biến B thành S và vẫn giữ nguyên mọi điểm trên S. (Ý chứng minh: Giả sử tồn tại một phép biến đổi như thế. Trước phép biến đổi, S là biên của B, sau phép biến đổi S phải là biên của chính S. Điều này vô lý.)
2) Giả sử phản chứng, sau nhào nặn không có hạt bột mì nào giữ nguyên vị trí. Giả sử hạt bột mì x được biến thành f .x/ sau nhào nặn. Nửa đường thẳng nối f .x/ với x (kéo dài) cắt mặt cầu S tại một điểm duy nhất, ký hiệu g.x/. Phép biến đổi x thành g.x/ chính là một phép biến hình liên tục, biến B thành S và giữ nguyên mọi điểm trên S. (Nếu x nằm trên S, thì nửa đường thẳng nối f .x/ với x cắt S tại chính x.) Điều này mâu thuẫn với điểm 1). Mâu thuẫn này bác bỏ giả thiết phản chứng.
Hai bài toán được Euler nghiên cứu nói trên là những ví dụ đơn giản của các vấn đề hình học trong đó kích cỡ không quan trọng, chỉ có hình dáng và vị trí tương đối đóng vai trò quyết định. Ngành toán học nghiên cứu những vấn đề như vậy ngày nay được gọi là Tôpô học (Topology).
Ngẫm cho kỹ thì chuyện kích cỡ không quan trọng đã được tạo hoá duy trì như một trong những nguyên lý hàng đầu, đóng vai trò “đảm bảo an ninh” không chỉ cho xã hội loài người, mà cho toàn bộ các giống loài trong tự nhiên. Nếu một người mua nhầm đôi giầy, chật quá hay rộng quá, tức là người ấy gặp một vấn đề về kích cỡ, thì anh ta đem đổi. Thế nhưng, nếu người ấy lấy vợ, và nếu như anh ta cũng gặp một vấn đề về kích cỡ, rồi đòi đổi, thì nguy hiểm vô cùng. Và nếu rất nhiều người sau khi lấy vợ cùng gặp vấn đề về kích cỡ như thế, đều cần phải đổi, thì xã hội chắc chắn sinh loạn.
Bà chúa thơ nôm Hồ Xuân Hương (1772–1822) chính là nhà Tôpô học đầu tiên của Việt Nam, người bằng trực cảm tuyệt vời đã phát biểu tường minh những ý tưởng táo bạo của tôpô từ hơn 200 năm trước. Không nghiên cứu bài toán về 7 cái cầu hay bài toán về số mặt số cạnh số đỉnh trong đa diện, nhưng bằng một tiếp cận đầy mẫn cảm, bà đã nhận ra chuyện này từ xưa. Bà viết thật nhân văn:
“Rộng hẹp nhỏ to vừa vặn cả
Ngắn dài khuôn khổ cũng như nhau”.
Hai câu thơ đó trích trong bài “Dệt cửi” của bà:
“Thắp ngọn đèn lên thấy trắng phau
Con cò* mấp máy suốt canh thâu
Hai chân đạp xuống năng năng nhắc,
Một suốt đâm ngang thích thích mau,
53
Tạp chí Epsilon, Số 08, 04/2016
Rộng hẹp nhỏ to vừa vặn cả
Ngắn dài khuôn khổ cũng như nhau
Cô nào muốn tốt ngâm cho kỹ
Chờ đến ba thu mới dãi màu.”
Như thế, Hồ Xuân Hương (1772–1822) độc lập và gần như đồng thời với L. Euler (1707-1783), đã phát biểu tường minh quan điểm cơ bản của tôpô học. Nữ sĩ họ Hồ quả là đã khởi đầu đầy sinh khí cho đám hậu sinh làm tôpô của Việt Nam, trong đó có kẻ học trò viết bài này:
“Mát mặt anh hùng khi tắt gió
Che đầu quân tử lúc sa mưa”.
Theo được Hồ nữ sĩ quả là khó. May sao,
"Mỏi gối chồn chân vẫn muốn trèo".
Vậy mà lại bảo các nhà Tôpô là hâm thì nghe thế quái nào được, hở giời. Vĩ thanh:
Lão Cò-nhà-đất đọc xong bài này cười phá lên, mà rằng: “Có mảnh đất cũng không biết nó to hay bé, vuông hay méo, lại bảo rằng như nhau tuốt. Thế thì nghèo suốt đời là phải. Bọn tôpô này xem ra chỉ lo chuyện giống thôi.
54
CÁC BÀI TOÁN ĐOÁN BÀI
Đặng Nguyễn Đức Tiến
(Đại học Trento, Italy)
Sân khấu bừng sáng trong tiếng hò reo vang dội.
Và nhà ảo thuật hiện ra, sang sảng nói.
“Các bạn, các bạn của tôi ơi, trò ảo thuật bài hay nhất đêm nay đang chờ đợi. Đây, hãy chọn 5 lá bài ngẫu nhiên. Chọn nào, bạn tôi ơi, ngẫu nhiên cũng được hay suy tư cẩn trọng đều cũng chẳng sao.
Chọn đi nào, thật kín đáo khỏi mọi con mắt thế gian.
Lựa chọn xong hãy giao cho người trợ lý của tôi những lá bài của bạn. Rồi anh ta sẽ đưa lại bốn lá trong số đó cho tôi.
Xem nào, từng lá một:
Bảy bích, đầm cơ, tám chuồng, cuối cùng là ba rô.
Giờ trên tay người trợ lý chỉ còn lại một, duy nhất một lá mà thôi. Một lá bài mà chỉ anh ta và người lựa chọn biết là gì.
Nhưng con mắt của nhà ảo thuật, đọc được thấu tâm can.
Bạn tôi ơi, đó chính là già bích!”
1. Năm lá bài của Fitch Cheney
Tiếp nối những số trước, chuyên mục giải trí kỳ này trân trọng giới thiệu với độc giả một loạt các bài toán đố, và kỳ này là các bài toán đoán bài. Như thường lệ, chúng tôi bắt đầu chuyên mục bằng bài toán kinh điển nhất và bài toán khởi đầu của lần này là bài toán năm lá bài của Fitch Cheney. Bài toán lần đầu tiên được in trong quyển Math Miracle của tác giả Wallace Lee vào năm 1950. Trong quyển này, tác giả đã ghi nhận tác giả bài toán là William Fitch Cheney (1894 - 1974), vẫn được gọi một cách thân mật là Fitch - nhà ảo thuật. Theo tác giả, trò ảo thuật này được Fitch sáng tạo vào khoảng những năm 1920 và chúng tôi đã mượn chi tiết này để viết lại thành lời tựa cho chuyên mục kỳ này. Để đơn giản hơn cho việc tiếp cận bài toán, chúng tôi phát biểu lại bài toán ở dạng toán đố như sau:
Hai người A và B tham gia một trò chơi như sau: A được nhận ngẫu nhiên 5 lá bài từ bộ bài chuẩn 52 lá và B không biết A nhận những lá bài nào. Sau khi xem xong, A được phép giữ lại 1 lá tùy ý và đưa lần lượt 4 lá còn lại cho người quản lý trò chơi. Người quản lý sẽ lần lượt đặt các lá bài vào các vị trí được đánh số cho trước từ 1 đến 4. B nhìn vào 4 lá bài đó của A và được yêu cầu đoán lá bài còn lại, nếu đoán đúng, họ thắng trò chơi, nếu đoán sai, họ thất bại. Tìm chiến thuật cho 2 người để họ luôn luôn chiến thắng.
55
Tạp chí Epsilon, Số 08, 04/2016
Thoạt nhìn, điều này là không thể vì với 4 lá bài, chúng ta chỉ có thể tổ hợp thành 4Š D 24 trường hợp khác nhau, trong khi bộ bài chuẩn có 52 lá. Tuy nhiên, với một chút mày mò và kiên nhẫn, hẵn bạn đọc sẽ nhanh chóng tìm ra cách thức để khám phá ra bí mật đoán bài của nhà ảo thuật.
Ở đây, chúng tôi giới thiệu một cách giải đơn giản như sau:
- Vì có 5 lá bài, nên chắc chắn tồn tại ít nhất 2 lá bài đồng chất (cùng là cơ, cùng rô, cùng chuồn hoặc cùng bích). Gọi 2 lá này là M và N.
- Vì mỗi chất bài có 13 lá khác nhau, nên ta luôn tìm được cách ‘đếm tới’ để khoảng cách của 2 lá tối đa là 6 (và tối thiểu là 1 do M và N cùng chất, không thể bằng nhau). Ví dụ nếu M D 7 và N DBồi thì khoảng cách là 4 vì sau 7 là 8; 9; 10 và bồi, 4 lá. Nếu M D bồi và N bằng 3 thì khoảng cách là 5 vì sau bồi là đầm, già, át, hai, ba, 5 lá. Không mất tính tổng quát, ta gán M cho lá đầu tiên và N là lá được ‘đếm tới’.
- Chiến thuật là giữ lại lá N và đặt lá M ở vị trí số 1. 3 lá còn lại, luôn có thứ tự lớn nhỏ ngầm định trước (ví dụ thứ tự chơi tiến lên như cơ lớn hơn rô, rô lớn hơn chuồn..) nên có thể tạo thành 6 hoán vị khác nhau, mỗi hoán vị ứng với 1 số cho biết khoảng cách của M và N.
- Như vậy, với cách hoán vị 3 lá còn lại ở vị trí 2; 3; 4 và lá đầu tiên là lá M, ta biết được chất của N và khoảng cách từ M đến N, nên xác định được N.
Liệu rằng ta có thể làm tốt hơn, nghĩa là có thể tìm ra lá bài bằng 4 lá còn lại trong một bộ bài lớn hơn, ví dụ 100 lá thay vì chỉ 52 lá chẳng hạn?
Hãy quay lại trò ảo thuật với cái nhìn toán học hơn một chút: chúng ta hãy xem một bộ 4 lá nhận được từ trợ lý là một thông điệp, do vậy có 52 51 50 49 thông điệp khác nhau. Nhà ảo thuật thấy 4 lá bài và phải đoán lá còn lại, điều này nghĩa là nhà ảo thuật chỉ cần phải đoán trong tổ
hợp chập 5 của 52 trường hợp. Vì
52
5
!
D 52 51 50 49 48=5Š nên số lượng thông điệp
mà nhà ảo thuật nhận được là quá dư so với số trường hợp, gấp 5Š=48 D 2:5 lần. Và thật sự là ta có thể giải quyết bài toán với 124 lá bài chứ không phải chỉ với 52 lá.
Chiến thuật cụ thể để với 4 lá bài có thể tìm ra lá còn lại trong số 124 lá bài chúng tôi xem như một bài tập dành cho độc giả. Gợi ý: dựa trên số dư khi chia cho 5.
Tổng quát hóa bài toán, cho m lá bài lấy từ n, có thể chọn giữ lại m 1 lá để từ đó xác định đượcn lá còn lại khi và chỉ khi n mŠ C m 1.
Tiếp tục mở rộng, với bộ ba .m; n; k/, n > m > k, với m lá bài lấy ra từ bộ bài n lá, có thể chọn giữ lại k lá sao cho từ đó xác định được m k lá còn lại khi và chỉ khi:
n
m
!
n.n 1/.n 2/ : : : .n k C 1/:
Với bài toán 5 lá bài của Fitch Cheney tương đương bộ 3 .52; 5; 4/:
Việc chứng minh chi tiết kết quả này nằm ngoài khuôn khổ của một bài toán giải trí, chúng tôi chỉ giới thiệu ý vắn tắt thông qua lý thuyết đồ thị như sau: Xét một đồ thị hai phía G với hai tập phân biệt S và T trong đó S là tập tất cả các bộ m lá bài lấy từ n lá và T là tập tất cả các cách sắp xếp k lá. Một cặp ghép trên đồ thị G chính là chiến thuật cần tìm. Theo định lý Konig-Egerváry, ¨
56
Tạp chí Epsilon, Số 08, 04/2016
độ lớn cực đại của một cặp ghép trên đồ thị hai phía bằng đúng kích thước của tập đỉnh phủ nhỏ nhất (có thể dẫn về bài toán luồng cực đại - lát cắt cực tiểu), và điều kiện tối ưu sẽ đạt được khi jSj D jT j.
2. Bài toán 55 lá bài
Trong loạt 3 bài toán tiếp theo, chúng tôi sẽ trích chọn giới thiệu từ tác giả quen thuộc của chuyên mục toán học giải trí, Stan Wagon qua các bài toán số 922, 1219, và 1223.
Và đây, bài toán 922, bài toán 55 lá bài:
Có 55 lá bài, được gán các số khác nhau từ 1 đến 55 và đặt ngẫu nhiên, úp mặt, thành vòng tròn. Cứ mỗi lần ta sẽ được lật một lá bài và xem số trên đó. Tìm chiến thuật lật bài ít nhất sao cho tìm được 1 lá bài chắc chắn có giá trị lớn hơn lá bài bên trái và bên phải của nó.
Bài toán này được Stan Wagon giới thiệu năm 2000, và theo ông nó bắt nguồn từ bài toán Sharygin đăng trên trang cut the knot.
Đáp án của bài toán là cần tối đa 10 lần mở bài, ta sẽ luôn tìm được một lá có giá trị lớn hơn hai lá hai bên.
Chúng tôi giới thiệu ở đây một lời giải như sau:
- Gọi f .x/ là giá trị của lá bài tại vị trí x. Khi đó, xét một bộ 3 vị trí .m; n; k/ bất kỳ, ta luôn tìm được một lá bài lớn hơn 2 lá còn lại. Không mất tính tổng quát, giả sử lá bài đó là n, lá bên trái là m và bên phải là k (do các lá bài xếp thành vòng tròn nên ta luôn tìm được bộ 3 thỏa mãn điều kiện này). Khi đó f .m/ < f .n/ và f .n/ > f .k/. Ta gọi một bộ 3 có tính chất như vậy là tính chất S, nghĩa là lá ở giữa có giá trị lớn hơn 2 lá bên trái và phải.
- Giả sử jn mj > 1, nghĩa là 2 lá m và n không nằm kế nhau. Chọn một lá t bất kỳ ở giữa m và n. Có hai trường hợp: Nếu f .t / > f .n/, ta có bộ 3 .m; t; n/ có tính chất S. Nếu f .t / < f .n/, ta có bộ 3 .t; n; k/ có tính chất S. Như vậy, dù ở trường hợp nào thì bộ 3 mới tạo với t đều có các chỉ số gần hơn so với bộ 3 .m; n; k/. Và cứ làm như vậy, cuối cùng ta sẽ thu được một bộ 3 mà khoảng cách các lá bằng 0, hay nói cách khác, là 3 lá liên tục thỏa mãn tính chất S, cũng chính là yêu cầu của đề bài.
- Tiếp tục đơn giản hóa, với mỗi bộ .m; n; k/ ta có khoảng cách giữa các lá là fnm1; kn1g, tức là số lá bài ở giữa các lá của bộ 3 này. Như vậy mục tiêu của bài toán là tìm ra bộ 3 có khoảng cách f0; 0g.
- Để rút về được f0; 0g trong tình huống xấu nhất thì trước đó sẽ là f0; 1g (chúng ta đang xét trong tình huống xấu nhất, không quan tâm đến may rủi). Lần ngược tiếp tục, ta có bộ lớn nhất trong tình huống xấu nhất có thể đưa về f0; 1g là f1; 2g. Lưu ý, ở đây, không mất tính tổng quát, ta thấy khoảng cách trái hay phải là như nhau, nghĩa là f1; 2g tương ứng với f2; 1g.
- Tiếp tục lần ngược ta có: f0; 0g f0; 1g f1; 2g f2; 4g f4; 7g f7; 12g f12; 20g.
- Như vậy, khởi điểm ta có thể chọn lá bài a bất kỳ, sau đó chọn lá bài b cách a 12 lá bài ở giữa, và sau đó chọn tiếp lá bài c cách b 20 lá. Khi đó, ta có nếu f .a/ hoặc f .b/ là lá lớn nhất trong 3
57
Tạp chí Epsilon, Số 08, 04/2016
lá thì ta chỉ mở thêm tối đa 6 lá nữa là sẽ chắc chắn đưa về được 0; 0. Nếu f .c/ lớn nhất, ta tốn thêm một lần mở để đưa 20; 20 về 12; 20. Trường hợp này ta cần tối đa 7 lần mở bài.
- Vậy trong tình huống xấu nhất, ta tốn tối đa 10 lần mở bài.
Và, với cách làm như trên, nếu để ý ta sẽ thấy số lá bài tối đa với n lần lật bài ta sẽ chắc chắn tìm được một lá bài có giá trị lớn hơn hai lá bên cạnh chính là số Fibonacci thứ n.
3. Bài toán 1219
Bài toán này được Stan Wagon phát biểu như là một bài toán về cai ngục, ở đây chúng tôi phát biểu lại với dạng trò chơi đoán bài, như sau:
A và B tham gia một trò chơi với luật như sau:
A và B được mời vào một phòng riêng để chờ gọi ra tham gia trò chơi.
Đầu tiên, người dẫn trò sẽ mời A ra và cho A xem một bộ bài chuẩn 52 lá được xếp ngửa mặt thành một hàng. Sau khi xem xong, A có quyền chọn 2 lá bài bất kỳ, nếu muốn và đổi chỗ 2 lá này. Sau đó, người dẫn trò lật úp lại toàn bộ các lá bài (giữ nguyên thứ tự) lại và mời B ra. Người dẫn trò sẽ nói tên một lá bài T tùy ý, và cho phép B lật các lá bài lên để tìm ra lá bài T này. Nếu sau tối đa 26 lần lật bài B tìm được lá bài T , họ chiến thắng trò chơi. Ngược lại, nếu sau 26 lần lật bài mà B không tìm ra lá T , họ thất bại.
A và B trong quá trình chơi không được có bất cứ trao đổi gì với nhau, và họ chỉ được trao đổi chiến thuật với nhau trước khi chơi. Hãy chỉ ra chiến thuật cho A và B để họ luôn có thể thắng trò chơi.
Số 26 trong đề bài là một trong những gợi ý quan trọng trong việc tìm ra chiến thuật. Trong phần này, chúng tôi giới thiệu một chiến thuật dựa trên chu trình như sau:
- Đầu tiên A và B ngầm định đánh số các lá bài từ 1 đến 52. Khi B được người dẫn trò cho biết lá cần tìm là lá bài T , B sẽ mở lá ở vị trí T . Nếu lá đó đúng là lá T , B đã tìm ra và dừng. Ngược lại, nếu lá đó có giá trị f .T / ¤ T , B sẽ mở tiếp lá bài ở vị trí f .T / tương ứng và tiếp tục như vậy cho đến khi gặp T .
- Một chuỗi các lá bài như vậy (bắt đầu từ một vị trí x, sau đó mở tiếp vị trí f .x/ trên lá bài tại x và tiếp tục cho đến khi gặp lá x), được gọi là một chu trình. Và vì toàn bộ bộ bài chỉ có 52 lá, nên chỉ có thể tồn tại nhiều nhất một chu trình có độ dài hơn 52=2 D 26. Do vậy, chiến thuật của A là tìm ra chu trình dài hơn 26, nếu có, và đổi chỗ 2 lá bài để cắt ngắn chu trình này thành 2 chu trình không vượt quá 26.
- Việc "cắt" chu trình của A thực hiện khá đơn giản như sau: không mất tính tổng quát, giả sử chu trình dài hơn 26 là 1 2 3 N (nghĩa là f .1/ D 2; f .2/ D 3; : : : ; f .N / D 1), lúc này ta chỉ đơn giản hoán đổi vị trí lá thứ 26 và lá thứ N thì ta sẽ có 2 chu trình ngắn hơn là 1 2 3 N và 27 28 26.
Một câu hỏi khó hơn được chúng tôi xem như một bài tập dành cho độc giả là với cách làm như chiến thuật ở trên, kỳ vọng để B tìm ra lá bài T ngẫu nhiên bất kỳ trong số 52 lá bài E.52/ là bao nhiêu? Và tổng quát với n lá bài thì kỳ vọng E.n/ là bao nhiêu? Ví dụ ta có E.2/ D 1, E.3/ D 11=9.
58
Tạp chí Epsilon, Số 08, 04/2016
4. Bài toán 1223
Bài toán cuối cùng mà chúng tôi giới thiệu ở chuyên mục lần này là một phát triển của bài toán trước, phát biểu như sau:
A và B tham gia một trò chơi với luật như sau:
A và B được mời vào một phòng riêng để chờ gọi ra tham gia trò chơi.
Đầu tiên, người dẫn trò sẽ mời A ra và cho A xem 5 lá bài, đánh số từ 1 đến 5 và được xếp ngửa mặt thành một hàng. Sau khi xem xong, A có quyền chọn 2 lá bài bất kỳ, nếu muốn và đổi chỗ 2 lá này. Sau đó, người dẫn trò lật úp lại toàn bộ các lá bài (giữ nguyên thứ tự) lại và mời B ra. Người dẫn trò sẽ nói ngẫu nhiên một số nguyên T tùy ý trong khoảng từ 1 đến 5 và yêu cầu B tìm lá bài có số tương ứng trong số các lá bài đang lật úp. Nếu sau đúng 1 lần lật bài B tìm được lá bài T , họ chiến thắng trò chơi. Ngược lại, họ thất bại.
A và B trong quá trình chơi không được có bất cứ trao đổi gì với nhau, và họ chỉ được trao đổi chiến thuật với nhau trước khi chơi. Hãy chỉ ra chiến thuật cho A và B để khả năng chiến thắng trò chơi là cao nhất.
Ta có thể thấy nếu B chọn ngẫu nhiên 1 lá, không quan tâm đến A, khả năng họ thắng trò chơi là 1=5. Nếu A luôn luôn đổi chỗ lá bài sao cho lá 1 sẽ nằm ở vị trí 1 và chiến thuật của B là nếu T D 1 thì sẽ mở lá ở vị trí 1, ngược lại mở ngẫu nhiên các lá ở vị trí từ 2 đến 5. Lúc này, xác suất chiến thắng là 2=5 D 40%.
Nếu A và B sử dụng chiến thuật cắt chu trình như ở bài toán trước, xác suất chiến thắng của họ là bao nhiêu? Ta thấy, với chiến thuật ngày thì B sẽ mở lá bài ở vị trí T khi người dẫn trò cho biết là cần tìm là T . Stan Wagon, do vậy, ký hiệu cho chiến thuật này là (12345) ứng với các vị trí sẽ mở bài tương ứng. Chiến thuật của A như sau: nếu A gặp 1 cặp bị hoán đổi vị trí, A sẽ hoán đổi vị trí cặp này lại cho đúng. Ngược lại (nghĩa là không có cặp bị hoán đổi vị trí), A sẽ tìm chu trình có độ dài k 3 và cắt thành chu trình này, nếu có, thành chu trình ngắn hơn có độ dài k 1 và một lá rời. Dễ thấy, nếu không có chu trình k, các lá bài đã nằm đúng vị trí từ 1 đến 5. Với cách làm này có tất cả 284 trường hợp B sẽ tìm đúng lá T trong số 5:5Š khả năng, do vậy xác suất để họ thắng trò chơi là 284
5:5ŠƯD 4713%, lớn hơn 713% so với cách làm ở trên.
Stan Wagon đưa ra cách tìm công thức tổng quát để tính số trường hợp thành công f .n/ với n lá bài với chiến thuật này là:
f .n/ D 2:nŠ 1 C T .n/
với T .n/ là số lượng các hoán vị của n số nguyên đầu tiên trong đó có tồn tại ít nhất một cặp bị hoán đổi vị trí. Một vài giá trị T .n/ đầu tiên là 0, 1, 3, 9, 45, 285, 1995. Trong trường hợp đầu bài n D 5, ta có f .5/ D 2:5Š 1 C T .5/ D 2:120 1 C 45 D 284. Chứng minh chi tiết của T(n) và f(n) có thể xem thêm tại trang nhà của Stan Wagon.
Tuy nhiên, công thức tổng quát ở trên không phải là điểm thú vị của bài toán mà là kết quả bất ngờ sau đây: chiến thuật (11345) sẽ có khả năng thành công cao hơn chiến thuật (12345)! Và đây cũng chính là chiến thuật tối ưu. Chiến thuật này tóm tắt đơn giản là sau khi nghe người dẫn trò nói lá bài T , B sẽ lật lá bài ở vị trí T tương ứng, trừ trường hợp T D 2 thì B sẽ lật lá bài ở vị trí 1.
59
Tạp chí Epsilon, Số 08, 04/2016
Tổng số khả năng thành công theo chiến thuật này là 286 và do vậy xác suất thắng lợi là 4723%, cao hơn13% so với chiến thuật (12345). Chiến thuật này được Stan gọi là double-door (cửa đôi).
Một câu hỏi mở vẫn chưa được giải đáp là với bộ bài chuẩn 52 lá, chiến thuật nào là tốt nhất? Và với n tổng quát? Hiện tại, kết hợp khảo sát bằng máy tính, Stan Wagon, tác giả của bài toán cũng chỉ mới chứng minh và đề xuất được cách làm tối ưu cho n trong phạm vi từ 1 đến 10.
Tham khảo và trích dẫn
Độc giả có thể tham khảo chi tiết hơn cho các bài toán giới thiệu ở chuyên mục lần này ở các địa chỉ và tài liệu sau:
1. Các bài toán của Stan Wagon tại http://mathforum.org/wagon/
2. Kleber, M., The Best Card Trick. Mathematical Intelligencer, 24 (2002).
3. Simonson, S. and Holm, T., Using a Card Trick to Teach Discrete Mathematics. Primus: Problems, Resources and Issues in Mathematics Undergraduate Studies, 13 (2003):248-269.
60
XUNG QUANH ĐỊNH LÝ BROKARD
Nguyễn Trần Hữu Thịnh
(Trường THPT Chuyên Lý Tự Trọng, Cần Thơ)
Bài viết này sẽ nói về các vấn đề xoay quanh định lý Brokard quen thuộc và được trình bày bằng các công cụ hình học phẳng thuần túy.
1. Mở đầu
Định lý Brokard [1] nói về tam giác được có các định là giao điểm của các cặp đường thẳng tạo bởi một tứ giác nội tiếp và nhận tâm ngoại tiếp của tứ giác ấy là trực tâm. Bản thân Brokard cũng là một trong những viên ngọc quý và có nhiều ứng dụng trong các cuộc thi học sinh giỏi các nước. Sau đây tôi xin trình bày lại một cách chứng minh định lý này thông qua một bổ đề có khá nhiều ứng dụng như sau:
Định lý Brokard. Cho tứ giác lồi ABCD không là hình thang nội tiếp đường tròn tâm O. Gọi E; F; G lần lượt là giao điểm của AB và CD, AD và BC, AC và BD. Khi đó O là trực tâm của tam giác EF G. Lời giải sau được rút ra từ ý tưởng của thầy Đỗ Thanh Sơn về vấn đề giao điểm của các tiếp tuyến trong một đường tròn.
Ta có bổ đề sau:
Bổ đề 1. Gọi H; I; J; K; L; M theo thứ tự là giao điểm của các cặp đường thẳng .dAI dB /; .dAI dC /; .dAI dD/; .dB I dC /; .dB I dD/; .dC I dD/1. Khi đó các bộ điểm .I I EI LI F /, .F I MI GI H /, .EI KI GI J / thẳng hàng.
Chứng minh. Do vai trò của E và F là bình đẳng trên đường thẳng IL nên ta có thể giả sử E nằm trên đoạn thẳng IL. Gọi E là giao điểm của AB và IL. Áp dụng định lý Menelaus cho tam giác IHL với cát tuyến ABE được:
EL:BL
EI
BH:AH
AID 1 hayEI
ELD AI
BL
Gọi E0là giao điểm của CD và IL. Tương tự ta cũng được: E0LD CI
E0I
DLD AI BL
Điều này chứng tỏ E và E0chia trong đoạn IL theo cùng tỉ số. Do đó E trùng E0. Nên với E là giao điểm AB và CD thì I; E; L thẳng hàng.
Tương tự I; L; F thẳng hàng. Vậy bộ điểm .I I EI LI F / thẳng hàng.
1Để tiện cho việc chứng minh, ta quy ước dK là tiếp tuyến tại K của đường tròn đi qua K. 61
Tạp chí Epsilon, Số 08, 04/2016
Với cách chứng minh như vậy ta cũng suy ra được các bộ điểm .F I MI GI H /, .EI KI GI J / thẳng hàng.
Một cách khác, ta có thể áp dụng định lý Pascal cho lục giác suy biến thành tứ giác ABCD để
suy ra các bộ điểm nêu trên thằng hàng.
Quay lại bài toán,
Chứng minh. Ta có BOCK và AODJ là những tứ giác nội tiếp. Mặt khác do tứ giác ABCD nội tiếp nên:
F C :FB D FD:FA
Nên F nằm trên trục đẳng phương của .BOCK/ và .AODJ / nên OF ? KJ . Áp dụng bổ dề được EG ? OF .
Tương tự F G ? OE. Do đó O là trực tâm của tam giác EF G.
Vậy ta có điều phải chứng minh.
Nhận xét. Việc chứng minh các bộ điểm thẳng hàng như thế giúp hướng giải quyết được sáng sủa hơn và đưa bài toán trở về với một tính chất quen thuộc về sự vuông góc giữa đường nối tâm và trục đẳng phương của hai đường tròn. Với bài toán thú vị như vậy ta sẽ xét đến những mở rộng và ứng dụng quan trọng của nó trong các bài toán quen thuộc và đề thi học sinh giỏi của một số nước.
2. Khai thác định lý
Trong bổ đề trên ta thu được ba bộ điểm thẳng hàng và có những tính chất khá đẹp. Một tính chất được suy ra trực tiếp của bổ dề này đã được đưa vào bài hình trong kì thi China MO 1997. Ta xét bài toán
62
Tạp chí Epsilon, Số 08, 04/2016
Bài toán 1 (China MO 1997). Cho tứ giác ABCD với các cạnh đôi một không song song nội tiếp. Gọi P; Q lần lượt là giao điểm của AB và CD, AD và BC. Gọi QE; QF lần lượt là tiếp tuyến tại E; F của đường tròn ngoại tiếp tứ giác ABCD. Chứng minh rằng P; E; F thẳng hàng.
Ta thấy nếu O là tâm đường tròn ngoại tiếp của tứ giác ABCD thì OQ ? EF . Mặt khác theo định lý Brokard thì P G ? OQ với G là giao điểm của AC và BD. Do đó nếu E; G; F thẳng hàng thì P; E; F thẳng hàng, ta xét bổ đề sau
Bổ đề 2. Cho tứ giác ABCD không là hình thang nội tiếp .O/. M; T lần lượt là giao điểm của AB và CD, AC và BD. Vẽ ME; MF là các tiếp tuyến của đường tròn .O/ với E; F là tiếp điểm. Chứng minh rằng E; F; T thẳng hàng.
Chứng minh. Gọi H là giao điểm của OM và EF . Ta có:
MA:MB D ME2 D MH:MO
Do đó tứ giác ABHO nội tiếp. Tương tự tứ giác CDOH nội tiếp. Suy ra: BHC \D BHM \ C MHC \ D BAO [ C ODC \) BHC \D BT C \
Nên tứ giác BH T C nội tiếp. Tương tự tứ giác AH TD nội tiếp. Ta có:
MHC \ D ODC \D ODH \và THC \D TBC [ D TAD[ D THD \
Do đó:
MH T \ D12 MHC \ C THC \C THD \C OHD \ D 90ı
Nên TH ? OM. Do đó TH; EF trùng nhau, tức là ba điểm E; F; T thẳng hàng. Ta có điều phải chứng minh.
Quay lại bài toán,
63
Tạp chí Epsilon, Số 08, 04/2016
Chứng minh. Từ bổ đề trên, ETF ? OQ và theo định lý Brokard thì ta cũng có P T ? OQ, vì vậy ta có ngay được E; F; P thẳng hàng.
Bài toán đã được giải xong.
Nhận xét. Lời giải trên sử dụng định lý Brokard như một ”chiếc cầu” để liên kết các điểm với nhau. Hơn thế sau khi thông qua lời giải, rõ ràng bài toán đã được vận dụng khéo léo tính chất của tiếp tuyến và được trình bày ngắn gọn thông qua hình học phẳng thuần túy.
Nói về tứ giác thì hẳn vấn đề được quan tâm không kém hiện nay là tứ giác toàn phần cùng với điểm Miquel của tứ giác này, và chúng có liên hệ với định lý Brokard thế nào, ta cùng xét hai bài toán sau:
Bài toán 2 (IMO 1985). Cho tam giác ABC. Một đường tròn tâm O đi qua A; C và cắt các đoạn AB; BC theo thứ tự tại hai điểm K; N phân biệt. Giả sử M là giao điểm thứ hai của .ABC / và .KBN /. Chứng minh OMB \ D 90ı.
Ta để ý thấy M là điểm Miquel của tứ giác toàn phần ACPNFB. Chứng minh OMB \ D 90ı tức là chứng minh M là chân đường cao kẻ từ O xuống BP. Mặt khác theo định lý Brokard thì OG là đường cao của tam giác GBP với G là giao điểm của AN và KC. Vậy ta chỉ cần chứng minh O; G; M thẳng hàng là xong.
Chứng minh. Gọi M0là chân đường cao kẻ từ O xuống BP.
Gọi D; E lần lượt là giao điểm của .dC I dK/; .dAI dN /. Theo bổ đề của định lý Brokard thì E; B; M0; D; P thẳng hàng.
Từ đó ta dễ dàng suy ra các ngũ giác AEM0NO và KM0DCO nội tiếp. Nên: AM\0C D AM\0O C OM\0C D ANO \C OKC \D 180ı KAC \ NCA [ D ABC \
Do đó tứ giác ABM0C nội tiếp. Tương tự KBM0N nội tiếp. Nên M0là giao điểm thứ hai của .ABC / và .KBN /. Suy ra M0trùng M.
Vậy ta có điều phải chứng minh.
64
Tạp chí Epsilon, Số 08, 04/2016
Nhận xét. Một bài toán không quá khó nhưng vẫn tiếp tục áp dụng bổ đề quen thuộc này. Song đó ta tiếp tục phát hiện một tính chất khá hay ở đây, .AKNC /; .AONM /; .KOCM / đều nhận G là giao điểm của hai đường chéo. Điều này dễ dàng thu được thông qua khái niệm tâm đẳng phương của ba đường tròn. Vậy ta có thể chứng minh định lý Brokard bằng kết quả này hay không? Ta cùng quay lại với định lý thú vị này:
Chứng minh. Gọi N; P lần lượt là chân đường cao kẻ từ O; E xuống EF; FO. Khi đó các ngũ giác OBNKD và AOCNH nội tiếp. Mặt khác ta cũng có tứ giác ABCD nội tiếp. Áp dụng kết quả ta được AC; BD; ON đồng quy tại G hay O; G; N thẳng hàng. Tương tự vậy ta cũng cần chứng minh bộ ba tứ giác ABCD; AP CE; BPDE nội tiếp. Thật vậy,
65
Tạp chí Epsilon, Số 08, 04/2016
ngũ giác AMDPO nội tiếp. Do đó:
ACE [ D ACB [ C BCE [ D ACB [ C BAD [ D 90ı C ADO \D 90ı C APO [ D APE [
Suy ra tứ giác AP CE nội tiếp. Theo đó ta cũng được EBPD nội tiếp. Áp dụng kết quả ta được AC; BD; EP đồng quy tại G hay E; G; P thẳng hàng.
Vậy ta có điều phải chứng minh.
Nhận xét. Lại thêm một phát kiến thú vị về định lý này thông qua tâm đẳng phương G của sáu đường tròn. Thậm chí, qua Bài toán 2, ta còn thấy điểm Miquel của tứ giác toàn phần là chân đường cao kẻ từ tâm O xuống cạnh EF . Không những vậy, ta có thể thu được tính chất với nhiều ứng dụng như sau:
Tính chất 1. Chân ba đường cao của tam giác EF G chính là ba điểm Miquel của tứ giác toàn phần ABECDF .
Tính chất 2. Tâm O của đường tròn ngoại tiếp tứ giác ABCD nằm trên đường tròn Miquel của tứ giác toàn phần ABECDF .
Ta lại nghĩ đến tính chất đường thẳng Steiner của tứ giác này đi qua các trực tâm, vậy điểm G có quan hệ gì với đường này không? Ta có bài toán sau:
Bài toán 3. Cho tam giác nhọn ABC. Đường tròn tâm O đi qua B và C cắt AB; AC lần lượt tại M; N. Gọi P là giao điểm của BN và CM. Gọi H; K lần lượt là trực tâm của tam giác ABC và tam giác AMN. Chứng minh rằng P; K; H thẳng hàng.
Ta nhận thấy K; H cùng nằm trên đường thẳng Steiner nên P cũng phải nằm trên đường này. Nhìn vào giả thiết đề bài thì ta khó định hướng được lối đi, nhưng ta để ý đến tính chất của đường thẳng Steiner của tứ giác toàn phần thông qua một bổ đề sau:
Bổ đề 3. Cho tứ giác toàn phần ABF CDE. Chứng minh rằng đường thẳng Steiner của tứ giác là trục đẳng phương chung của .AC /; .BD/ và .EF /.
Chứng minh. Gọi H1; H2 là trực tâm của CDE; ABE.
Gọi H; I lần lượt là hình chiếu của H1 lên ED; CD. Ta thấy H 2 .AC /; I 2 .EF /. Ta có tứ giác HH1ID và CHIE nội tiếp nên:
H1H:H1C D ID:IC D HD:HE D H1I:H1E
Như vậy H1 nằm trên trục đẳng phương của .AC / và .EF /. Tương tự H2 cũng nằm trên trục đẳng phương của .AC / và .EF /. Hoàn toàn theo cách ấy ta cũng suy ra H1H2 là trục đẳng phương của .BD/ và .EF /.
Ta kết luận đường thẳng Steiner của tứ giác toàn phần ABF CDE là trục đẳng phương chung của .AC /; .BD/ và .EF /.
Vậy ta có điều phải chứng minh.
66
Tạp chí Epsilon, Số 08, 04/2016
Với bổ đề quan trọng này, bài toán sẽ trở nên nhẹ nhàng hơn, ta cùng trở lại: Chứng minh. Vì P là giao của BN và CM nên:
PM :P C D PN :PB
Suy ra P nằm trên trục đẳng phương của .BN / và .CM /. Áp dụng bổ đề ta thu được P nằm trên đường thẳng Steiner của tứ giác toàn phần AMBPNC. Như vậy P; K; H thẳng hàng.
Vậy ta có điều phải chứng minh.
Nhận xét. Bài toán trên đã khéo léo vận dụng một ”viên ngọc quý” trong tứ giác toàn phần, tứ đó đưa ta đến một tính chất khác nữa của định lý Brokard:
Tính chất 3. Trực tâm G của tam giác OEF nằm trên đường thẳng Steiner của tứ giác toàn phần 67
Tạp chí Epsilon, Số 08, 04/2016
ABECDF .
Do định lý Brokard cho ta một hệ thống tam giác trực tâm nên thông qua bài toán sau ta lại có thêm một tính chất đẹp như sau
Bài toán 4 (Romanian Master of Mathematics 2013). Cho tứ giác ABCD không là hình thang nội tiếp đường tròn !. Gọi P; Q; R lần lượt là giao điểm của AB và CD, AD và BC, AC và BD. Gọi M là trung điểm của PQ. MR cắt ! tại K. Chứng minh rằng đường tròn ngoại tiếp tam giác KPQ và ! tiếp xúc nhau.
Đây là một bài toán hay và khó, ta sẽ sử dụng hai bổ đề, trước hết đường thẳng vuông góc với OR tại R cắt ! tại P1; Q1 như hình vẽ
Bổ đề 4. AP1 cắt CQ1 tại một điểm thuộc PQ.
Chứng minh. Gọi X; Y lần lượt là giao điểm của AP1 với CQ1, AQ1 với CP1.
Áp dụng định lý Pascal cho lục giác suy biến thành tứ giác AP1CQ1 ta dễ dàng suy ra được đường thẳng XY chứa P và Q nên AP1 và CQ1 cắt nhau tại một điểm thuộc PQ.
Ta có điều phải chứng minh.
Bổ đề 5. PP1; QQ1 cắt nhau tại K.
Chứng minh. PP1 cắt ! tại P2. Ta sẽ chứng minh P2Q1 đi qua Q.
Áp dụng định lý Pascal cho lục giác P2Q1CDAP1 kết hợp với bổ đề 1 ta có giao điểm của P2Q1 68
Tạp chí Epsilon, Số 08, 04/2016
và AD, Q1C và AP1 cùng với giao điểm của AD và P1P2 là P thẳng hàng. Mặt khác theo bổ đề 1 ta có Q1C cắt AP1 tại một điểm thuộc PQ, do đó giao điểm của P2Q1 và AD cũng nằm trên PQ, tức là điểm Q. Vậy P2Q1 đi qua Q.
Ta có điều phải chứng minh. Quay trở lại bài toán,
Chứng minh. Áp dụng bổ đề 4 và bổ đề 5, ta có tứ giác PQP1Q1 là hình thang, M; R lần lượt là trung điểm của PQ; P1Q1 và K là giao điểm của PP1; QQ1 nên ta dễ dàng suy ra đường tròn ! ngoại tiếp tam giác KP1Q1 và KPQ tiếp xúc nhau.
Vậy bài toán đã được giải xong.
Nhận xét. Việc sử dụng khéo léo định lý Pascal đã giúp ta giải quyết gọn gàng bài toán trên. Như ta đã biết, một tư giác nội tiếp không là hình thang bất kỳ chỉ tạo ra một tam giác trực tâm, ta tạm gọi theo ánh xạ tam giác trực tâm ấy là ảnh của tứ giác nội tiếp thông qua một ánh xạ Brokard. Nhưng điều ngược lại thì chưa đúng, tức là một tam giác trực tâm có thể có nhiều tạo ảnh. Cụ thể, ta xét tam giác nhọn OEF , trực tâm G, đường cao EK. Bằng công cụ phương tích,
ta dựng đường tròn tâm O bán kính pOE2 GE:KE, đây chính là đường tròn ngoại tiếp các tạo ảnh mà ta đề cập đến, với một cát tuyến từ P cắt .O/ tại hai điểm sẽ cho ta một tạo ảnh của tam giác trực tâm OEF .
Từ nhận xét này, ta có cách phát biểu rộng hơn cho bài toán 4 như sau
Bài toán 5. Cho tam giác ABC trực tâm H. Đường tròn đường kính AB; AC cắt nhau tại X. Gọi ! là đường tròn tâm A bán kính AX. Gọi M là trung điểm của BC. Đường thằng MH cắt ! tại E; F . Chứng minh rằng đường tròn ngoại tiếp các tam giác BCE và BCF tiếp xúc !.
Bài toán trên còn có thêm một tính chất như sau
Bài toán 6. Cho tam giác ABC trực tâm H. Đường tròn đường kính AB; AC cắt nhau tại X. Gọi !A là đường tròn tâm A bán kính AX. Gọi M là trung điểm của BC. Đường thằng MH cắt !A tại A1 sao cho A1 nằm giữa M và H. Định nghĩa tương tự cho B1; C1. Chứng minh rằng AA1; BB1; CC1 đồng quy.
69
Tạp chí Epsilon, Số 08, 04/2016
Các bài toán trên, đặc biệt là bổ đề được nêu ra có thể sử dụng định lý Pascal để giải quyết vấn đề. Như thế, việc phát triển từ tứ giác nội tiếp đường tròn sang tứ giác có bốn điểm nằm trên một conic là hoàn toàn có thể. Phần tiếp theo tác giả xin giới thiệu việc vận dụng định lý Pascal cho bốn điểm nằm trên một conic, từ đó cho thấy bản chất của định lý Brokard về tứ giác nội tiếp trong một đường tròn. Ta có bổ đề sau là phát triển rộng hơn của bổ đề đã nêu ở đầu tài liệu
Bổ đề 6. Cho bốn điểm A; B; C; D nằm trên một conic C tạo thành một tứ giác lồi không là hình thang. M; N lần lượt là giao điểm của AD và BC, AB và CD. P; Q là giao điểm tiếp tuyến của C tại A và C, B và D. Khi đó bốn điểm M; N; P; Q thẳng hàng.
Chứng minh. Áp dụng định lý Pascal cho lục giác suy biến thành tứ giác AABCCD ta có M; N; P thẳng hàng. Áp dụng định lý Pascal cho lục giác suy biến thành tứ giác ABBCDD ta có M; N; Q thẳng hàng. Tóm lại ta có M; N; P; Q thẳng hàng.
Ta có điều phải chứng minh.
Từ bổ đề trên ta có tiếp hệ quả như sau
Hệ quả. Cho conic C tiếp xúc các cạnh AB; BC; CD; DA của tứ giác ABCD theo thứ tự tại M; N; P; Q. Khi đó AC; BD; MP; NQ đồng quy.
Rõ ràng bổ đề trên là một mở rộng đẹp của bổ đề đã nêu ở đầu bài đối với ellipse, parabol hay hyperbol. Trong trường hợp là ellipse, chỉ cần thực hiện một phép co thành hình tròn thì ta lại có ngay những ứng dụng mới mẻ nữa. Bổ đề tiếp theo chính là mở rộng của Bổ đề 2:
Gọi A1A2A3A4 là tứ giác không là hình thang nội tiếp trong một conic C và M1; M2; M3 lần lượt là giao điểm của A1A2 và A3A4, A2A3 và A4A1, A3A1 và A2A4. Gọi N1; N2; N3; P1; P2; P3 là giao điểm của tiếp tuyến của conic tại A1 và A2, A1 và A4, A1 và A3, A3 và A4, A2 và A3, A2 và A4. Gọi U1; U2 là tiếp điểm của hai tiếp tuyến của conic đi qua M1. Định nghĩa tương tự V1; V2 đối với M2 và W1; W2 đối với M3. Bổ đề 1 cho ta ba bộ điểm thẳng hàng là .M2I M3I N1IP1/; .M3I M1I N2IP2/, .M1I M2I N3IP3/. Lần lượt gọi ba đường thẳng ấy là m1; m2; m3.
70
Tạp chí Epsilon, Số 08, 04/2016
Bổ đề 7. U1; U2 nằm trên m1, V1; V2 nằm trên m2 và W1; W2 nằm trên m3.
Chứng minh. Trong mặt phẳng xạ ảnh tồn tại phép chiếu ' biến conic C thành đường tròn C0. Như ta đã biết, phép chiếu ' bảo toàn sự thẳng hàng của các bộ điểm nên thông qua phép biến hình này ta có ngay Bổ đề 2 và theo đó các bộ điểm điểm .M2I M3IU1IU2/; .M1I M3I V1I V2/; .M1I M2I W1I W2/ thẳng hàng.
Ta có điều phải chứng minh.
Một kết quả đẹp lại được chứng minh. Gọi O là tâm của conic C, từ kết quả này ta xét tam giác OM1M2 sau:
71
Tạp chí Epsilon, Số 08, 04/2016
Khi conic C là đường tròn thì lần lượt theo tính chất của tiếp tuyến ta có m1 ? OM1 và m2 ? OM2 và như thế ta đã hiểu được tại sao định lý Brokard lại có phát biểu như vậy. Cuối cùng, tác giả xin đề xuất một số bài tập để bạn đọc có thể rèn luyện thêm những tư duy khác về định lý Brokard này.
3. Ứng dụng
Bài toán 7 (Trường hè Bắc Trung Bộ 2015 - Ngày 2). Cho tam giác nhọn ABC có đường cao AH, trực tâm K. Đường thẳng BK cắt đường tròn đường kính AC tại D; E (BD < BE). Đường thẳng CK cắt đường tròn đường kính AB tại F; G (CF < CG). Đường tròn ngoại tiếp tam giác DHF cắt BC tại điểm thứ hai là P.
a) Chứng minh rằng các điểm G; H; P; E cùng thuộc một đường tròn.
b) Chứng minh rằng các đường thẳng BF; CD; PK đồng quy.
Bài toán 8. Cho tứ giác lồi ABCD không là hình thang nội tiếp đường tròn tâm O. Gọi E; F; G lần lượt là giao điểm của AB và CD, AD và BC, AC và BD. Gọi X; Y theo thứ tự là trung điểm của AC; BD. Kéo dài XY cắt EF tại Z. Kéo dài GZ cắt đường tròn ngoại tiếp tam giác OFE tại Q. Đường tròn đường kính GQ cắt đường tròn ngoại tiếp tam giác OFE tại K khác Q. Gọi H là điểm Miquel của tứ giác toàn phần ABCDEF . Chứng minh rằng đường tròn ngoại tiếp các tam giác KQG và KZH tiếp xúc nhau.
Bài toán 9 (Lê Bá Khánh Trình). Cho tam giác ABC nội tiếp .O/ có B; C cố định, A chạy
trên cung nhỏ \
BC. M; N là trung điểm AB; AC. Lấy P trên đường thẳng MN thỏa mãn
BP C C ABC \C ACB [ D BAC [. Đường tròn .ABP / cắt AC tại E, .ACP / cắt AB tại F . Chứng minh rằng .AFE/ đi qua một điểm cố định.
Bài toán 10 (Lê Bá Khánh Trình). Cho tam giác ABC nội tiếp .O/, trung tuyến AI cắt .O/ tại D. AB cắt CD tại E. AC cắt BD tại F . .ABF / cắt .ACE/ tại K. .O1/; .O2/ là các đường tròn đi qua B tiếp xúc với AC tại A và đi qua C tiếp xuc với AB tại A. Chứng minh ba đường tròn .O1/; .O2/ và .OK/ có một điểm chung.
Bài toán 11. Cho tam giác ABC nội tiếp .O/, điểm P nằm trong tam giác sao cho AP vuông góc BC. Đường tròn đường kính AP cắt đường thẳng AC; AB lần lượt tại E; F và cắt .O/ tại điểm G khác A. Chứng minh rằng BE; CF; GP đồng quy.
Bài toán 11 có thể xem ở [6].
Bài toán 12 (USA TST 2012). Cho tam giác ABC nhọn, đường cao AA1; BB1, CC1. Gọi A2 là giao điểm của BC và B1C1. Định nghĩa B2; C2 tương tự. Gọi D; E; F theo thứ tự là trung điểm của BC; CA; AB. Chứng minh rằng đường thẳng vuông góc kẻ từ D tới AA2, E tới BB2 và F tới CC2 đồng quy.
Bài toán 13. Cho tứ giác ABCD nội tiếp .O/. Gọi E; F lần lượt là giao điểm của AB và CD, AD và BC. Gọi M; N theo thứ tự là trung điểm của AC; BD. Gọi H; K lần lượt là trực tâm của tam giác MEF và tam giác NEF . Chứng minh rằng HNKM là hình bình hành.
72
Tạp chí Epsilon, Số 08, 04/2016
Bài toán 14 (Trần Quang Hùng). Cho tam giác ABC. Đường tròn tâm K đi qua B; C cắt CA; AB lần lượt tại E; F . BE; CF cắt nhau tại H. D là hình chiếu của K xuống AH. M; N theo thứ tự di chuyển trên DE; DF sao cho BM ? BE; CN ? CF . Chứng minh rằng đường đối trung xuất phát từ đỉnh A của tam giác ABC chia đôi cạnh MN.
Bài toán trên có tham khảo trong [7]. Hơn nữa ta còn có thêm hai mở rộng sau
Bài toán 15 (Trần Quang Hùng). Cho tam giác ABC và điểm P. AP; BP; CP lần lượt cắt BC; CA; AB tại D; E; F . Trên DE; DF lần lượt lấy M; N sao cho BM k AC; CN k AB. Gọi S; T theo thứ tự là trung điểm của EF; MN. Chứng minh rằng A; S; T thẳng hàng.
Bài toán 16 (Trần Quang Hùng). Cho tam giác ABC và điểm D nằm trên cạnh BC. .DAB/; .DAC / cắt CA; AB lần lượt tại E; F . M; N nằm trên DE; DF sao cho BM k AC; CN k AB. Gọi S; T lần lượt là trung điểm của EF; MN. Chứng minh rằng ST song song với đường đối trung xuất phát từ đỉnh A của tam giác ABC.
Bài toán 17 (Chọn đội tuyển quốc gia Khoa học tự nhiên 2014). Cho tứ giác ABCD nội tiếp. P CDBD2
M; N lần lượt là trung điểm của CD; AB. P nằm trên CD sao choPD
AC2. AC cắt BD
tại E. Gọi H là hình chiếu của E lên PN. Chứng minh rằng đường tròn ngoại tiếp các tam giác HMP và EDC tiếp xúc nhau.
Trên đây là tổng hợp của tác giả về định lý Brokard, xin cảm ơn anh Ngô Quang Dương - lớp 12A2 trường THPT chuyên KHTN đã có những trao đổi quý báu giúp bài viết được hoàn thiện hơn.
Tài liệu tham khảo
[1] Định lý Brokard.
http://www.imomath.com/index.php?options=334&lmm=0.
[2] Đỗ Thanh Sơn, Một số chuyên đề Hình học phẳng bồi dưỡng học sinh giỏi Trung học phổ thông, NXB Giáo dục, 2013.
[3] Nguyễn Văn Nho, Những định lí chọn lọc trong hình học phẳng qua các kì thi Olympic, NXB Giáo dục, 2007.
[4] Romanian Master of Mathematics 2013 - Problem 3.
http://www.artofproblemsolving.com/community/c6h523072p3558896
[5] IMO 2015 - Problem 3.
http://www.artofproblemsolving.com/community/c6h1112748p5079655
[6] Concurrent problem.
http://www.artofproblemsolving.com/community/c6h1161051p5527875
[7] Symmedian bisects segment.
http://www.artofproblemsolving.com/community/c6h1192618p5839116 73
Tạp chí Epsilon, Số 08, 04/2016
74
TỨ GIÁC NGOẠI TIẾP ĐƯỜNG TRÒN
Đỗ Xuân Anh
(Trường THPT Chuyên KHTN, Hà Nội)
Tứ giác ngoại tiếp là một chủ đề không quá mới đối với bất kỳ ai đam mê với môn toán và đặc biệt là môn hình học nhưng có không nhiều những tài liệu viết về chủ đề này. Vậy nên trong bài viết này tôi xin đề cập đến vấn đề này với kiến thức và những ứng dụng cơ bản nhất của tứ giác ngoại tiếp.
1. Một số tính chất cơ bản của tứ giác ngoại tiếp đường tròn
Khi nhắc tới tứ giác ngoại tiếp đường tròn, chúng ta nên để ý đến những tính chất hay sử dụng như sau:
Cho tứ giác ABCD ngoại tiếp đường tròn .I /. .I / tiếp xúc AB, BC, CD, DA lần lượt tại M, N, P, Q.
Đặt AM D AQ D a, BM D BN D b, CN D CP D c, DQ D DP D d. Định lý 1.(Định lý Pithot) AB C CD D BC C DA.
Định lý 2.
1. (Định lý Newton) AC, BD, MP, NQ đồng quy tại T
2.AT
DTDbd:
C TDac,BT
T
D
Q
A
M
I
P
B
C
N
Chứng minh. Gọi T1 là giao điểm của AC với MP và T2 là giao điểm của AC với NQ. 75
Tạp chí Epsilon, Số 08, 04/2016
Ta sẽ chứng minh T1 T2 T . Thật vậy, áp dụng định lí sin, ta có:
T1A
T1CDAM
sin ∠AT1M sin ∠C T1M
CP sin ∠AMP
sin ∠CPM
DAM
CP
Tương tự,T2A
T2CDacnên T1, T2, T trùng nhau. Tính chất được chứng minh.
Định lý 3. AC, MN, PQ đồng quy tại V vàAV
C VDac,BV
1.
V
A
T
Q
D
M
I
P
DVDbd. Từ đó suy ra .AC; T V / D
B
N
C
Chứng minh. Lấy V trên AC sao choAV
C VDac. Áp dụng định lí Menelaus cho 4ABC ta có
M, N, V thẳng hàng. Tương tự suy ra P, Q, V thẳng hàng. Vậy tính chất trên cũng được chứng
minh.
với AD cắt DI tại Y thì XY vuông góc với AC.
Định lý 4. Đường thẳng qua A vuông góc với AB cắt BI tại X, đường thẳng qua A vuông góc
A
I
Y
B
F
D
X
E
C
76
Tạp chí Epsilon, Số 08, 04/2016
Chứng minh. Gọi F là hình chiếu của X lên BC; E là hình chiếu của Y lên CD. Ta có AX2 XC2 D AX2 XF 2 F C2 D F C2.
AY 2 Y C2 D AY 2 YE2 EC2 D EC2:
Mà F C D BC AB D DC AD D EC nên AX2 XC2 D AY 2 Y C2.
XA2 C C Y 2 AY 2 CX2 D XA2 C AC2 CX2 .AY 2 C AC2 C Y 2/ D 2!
AX !
AC 2!
AY !
AC
D 2!
AC !
YX
Do đó AC ? XY . Vậy ta đã chứng minh xong định lí 4.
Ngoài ra, chúng ta cũng nên biết một số công thức tính các yếu tố trong tứ giác ngoại tiếp đường tròn. Việc chứng minh xin dành cho các bạn đọc.
Trong các tính chất dưới đây, ta đặt r là bán kính đường tròn nội tiếp tứ giác ABCD và ∠DAB D ˛; ∠ABC D ˇ; ∠BCD D ; ∠CDA D ı:
r2:
Định lý 5. AB DNQ2:IA:IB
A'
D
A
Q
M
I
P
B'
B
C
N
Chứng minh. Gọi IA, IB lần lượt cắt QM, MN tại A0, B0 Ta có IA:IA0 D IB:IB0 D r2nên 4IA0B0 4IBA suy raA0B0
ABDIA0
IB. Từ đó, AB DIB:A0B0
IA0DIB:IA
được chứng minh.
Định lý 6. IB2
AB:BCDID2
CD:DA.
77
r2:NQ2. Vậy định lí 5
Q
D
B
A
I
P
M
N
Tạp chí Epsilon, Số 08, 04/2016 C
r2:NQ2suy raAB
Chứng minh. Từ định lí 5, ta có CD DIC:ID ADDIB2
ID2hayIB2
CDDIA:IB
IC:ID. Tương tự
ADDIB:IC
AB:BCDID2
BC
IA:IDsuy raAB
CD BC
CD:DA.
Định lý 7. IA:IC C IB:ID DpAB BC CD DA
Q
A
M
P' I
B
N
M' D
P
C
Chứng minh. Gọi M0, P0lần lượt đối xứng M, P qua I . Ta có 4MIB 4NM0M suy
MIDMM0
IBD2r2
IB. Tương tự M0Q D2r2
raM0N
P0N D2r2
IBhay M0N DMM0:MI
IA, P0Q D2r2 ID,
IC. Áp dụng định lí Ptoleme cho tứ giác P0NM0Q và định lí 5, suy ra IA:IC C
IB:ID DpAB BC CD DA. Vậy định lý được chứng minh.
Định lý 8. IA:IC D.a C c/:r sin ˛C
2
:
78
Tạp chí Epsilon, Số 08, 04/2016
A
Q
D
M
I
P
B
C
U
N
Chứng minh. Lấy U trên tia MB sao cho M U D NC suy ra IU D IC nên SAI U D12.a C c/:r D12IA:IU:sin ∠AIU D12IA:IC:sin˛ C 2
hay IA:IC D.a C c/ r sin ˛C
2
. Vậy định lí được chứng minh.
2:
Định lý 9.SABCD DpAB BC CD DA:sin˛ C
A
Q
D
M
I
P
B
C
N
Chứng minh. Theo định lí 7 và 8, ta có IA:IC CIB:ID D.a C b C c C d / r sin ˛C
2
suy ra SABCD D .a C b C c C d / r DpAB BC CD DA:sin˛ C
DpAB:BC:CD:DA
chứng minh.
2. Một số bài tập áp dụng
2. Ta có điều phải
Bài toán 1. 4ABC cân ngoại tiếp đường tròn .I /. Lấy E thuộc AB, F thuộc AC sao cho EF là tiếp tuyến của đường tròn .I / và EF k BC. ED vuông góc với BC tại D. Gọi H là giao điểm của BI với đường thẳng qua F vuông góc với BC. Chứng minh rằng DH vuông góc với EC.
79
E
A
I
Tạp chí Epsilon, Số 08, 04/2016
F
H
B C
D
G
Chứng minh. Gọi FH cắt BC tại G. Dễ thấy E; I; G thẳng hàng và F; I; D thẳng hàng.Ta có ∠BEG D ∠BEI D ∠IEF D ∠GEF D ∠EGB nên tam giác BEG cân tại B, suy ra BE D BG. Do đó BEH D BGH (c.g.c) vì vậy ∠BEH D ∠BGH D 90ıhay EH vuông góc EB tại E. Áp dụng định lý 4, suy ra DH vuông góc với EC. Vậy bài toán được chứng
minh.
Nhận xét. Chúng ta có thể sử dụng tính chất 4 để chứng minh một bài toán trong Mathley [5] bởi thầy Trần Quang Hùng như sau
Bài toán. 4ABC, đường tròn nội tiếp .I / tiếp xúc CA, AB tại E, F . Lấy P di chuyển trên EF . BP cắt CA tại M, MI cắt đường thẳng qua C vuông góc AC tại N. Chứng minh rằng đường thẳng qua N vuông góc với P C luôn đi qua điểm cố định khiP di chuyển. tại F . Chứng minh rằng đường tròn nội tiếp 4AEF , 4CEF tiếp xúc tại một điểm trên EF .
Bài toán 2. Cho tứ giác ABCD ngoại tiếp đường tròn .I /. AB giao CD tại E, AD giao BC F
X=Y
P
B
E
S
D
A Q I
C
R
80