Chia lưới tam giác đều và nguyên lí Dirichlet: bài toán 244 điểm
Chia tam giác đều thành lưới ô bằng nhau, dùng nguyên lí Dirichlet mở rộng và bổ đề bốn điểm để chứng minh có tứ giác diện tích nhỏ trong 244 điểm.
Toán 9 · Học sinh giỏi · Tổ hợp hình học
Chia lưới tam giác đều và nguyên lí Dirichlet: bài toán 244 điểm
Trong một tam giác đều diện tích 6 rải 244 điểm. Em sẽ học cách "đọc ngược" hai con số 2/27 và 244 để tự tìm ra lời giải, rồi viết lại thật chặt chẽ.
120 phút Mức: giỏi – chuyên Chỉ dùng kiến thức lớp 9, kèm một vài công cụ nâng cao được giải thích ngay trong bài
Em sẽ học: nguyên lí Dirichlet dạng mở rộng · chia tam giác đều thành các ô bằng nhau · từ bốn điểm dựng tứ giác đơn · xử lí điểm nằm trên biên ô · viết lời giải không hở
1 Bài toán và bản đồ bài học
Đọc đề, biết mình sẽ đi đâu và kiểm tra vốn liếng trước khi bắt đầu.
Trước hết hãy đọc thật kĩ đề bài. Trong bài toán tổ hợp hình học, mỗi con số của đề đều mang một thông điệp, và việc của em là giải mã chúng.
Đề bài
Cho một tam giác đều có diện tích bằng 6. Trong tam giác đó có 244 điểm phân biệt, không có ba điểm nào thẳng hàng. Chứng minh rằng tồn tại một tứ giác có bốn đỉnh là bốn điểm trong số 244 điểm đã cho và có diện tích nhỏ hơn \frac{2}{27}.
GV
Cô Lukato
Nhìn vào đề, em thấy ngay ba điều lạ: số 244 rất "lẻ", phân số \frac{2}{27} rất "nhỏ", và câu hỏi là tồn tại một tứ giác. Chưa cần tính gì cả, ta hãy hỏi: ba con số này có liên hệ với nhau không?
Em sẽ làm được
- Phát biểu và chứng minh nguyên lí Dirichlet dạng mở rộng.
- Chia một tam giác đều thành n^{2} tam giác đều nhỏ bằng nhau và đếm chính xác các ô.
- Đọc ngược từ một con số diện tích để đoán cách chia.
- Chứng minh bốn điểm trong một tam giác luôn tạo được tứ giác đơn có diện tích nhỏ hơn tam giác.
Bản đồ bài học
- Nguyên lí Dirichlet từ đầu.
- Lưới tam giác đều n\times n.
- Đọc ngược \frac{2}{27} và 244.
- Từ bốn điểm đến một tứ giác nhỏ.
- Viết lời giải hoàn chỉnh.
- Vì sao lại là 244, mở rộng, thử nghiệm bằng máy tính.
- Luyện tập, thách thức, tự kiểm tra.
Để bắt đầu, hãy tự kiểm tra nhanh ba câu dưới đây. Không sao nếu em chưa làm được: các mục sau sẽ giải thích từng chỗ.
Trong một lớp có 13 học sinh. Khẳng định nào sau đây luôn đúng ?
Đúng: có 12 tháng và 13 bạn, nhốt 13 "thỏ" vào 12 "chuồng" thì có chuồng chứa ít nhất hai thỏ.
Sai: "ít nhất hai" không có nghĩa là "đúng hai". Có thể cả lớp đều sinh vào tháng năm, khi đó có 13 bạn cùng tháng.
Sai: có thể nhiều tháng không có bạn nào sinh (ví dụ cả lớp sinh cùng mùa hè).
Sai: có thể xếp 12 bạn vào 12 tháng khác nhau và bạn thứ 13 vào một tháng bất kì, khi đó không tháng nào có ba bạn.
Có 50 quả táo xếp vào 7 rổ. Vì 50=7\times 7+1 nên có một rổ chứa ít nhất quả. Số nhỏ nhất k mà chắc chắn có rổ chứa ít nhất k quả là \left\lceil \frac{50}{7}\right\rceil= .
Trong hình học, ta chia một hình thành nhiều "ô" rồi rải các điểm vào các ô. Hãy xét các khẳng định sau.
a) Nếu chia một tam giác thành 10 ô và có 11 điểm thì chắc chắn có ô chứa ít nhất hai điểm.
Đúng: đây là Dirichlet cơ bản, 11\gt 10.
b) Nếu chia một tam giác thành 10 ô và có 20 điểm thì chắc chắn có ô chứa ít nhất ba điểm.
Sai: có thể xếp đúng hai điểm vào mỗi ô. Muốn chắc chắn có ô chứa ba điểm cần ít nhất 2\times 10+1=21 điểm.
c) Nếu có 30 điểm và 10 ô thì chắc chắn có ô chứa ít nhất ba điểm.
Đúng: \left\lceil \frac{30}{10}\right\rceil=3. Nếu mọi ô chứa nhiều nhất hai điểm thì tổng nhiều nhất là 20\lt 30.
d) Dirichlet cho biết ô nào chứa nhiều điểm.
Sai: nguyên lí chỉ khẳng định có tồn tại một ô như vậy, không chỉ ra là ô nào.
2 Nguyên lí Dirichlet từ đầu
Công cụ chính của bài: phát biểu, chứng minh và các bẫy khi dùng.
Nguyên lí Dirichlet (còn gọi là nguyên lí chuồng thỏ) là công cụ tồn tại mạnh nhất ở bậc THCS. Nó không cho ta tìm ra đối tượng cụ thể, nhưng đảm bảo rằng đối tượng đó chắc chắn có.
Trực giác: nhốt thỏ vào chuồng
Có 5 con thỏ và 4 cái chuồng. Em nhốt thế nào thì cũng không thể để mỗi chuồng chỉ có nhiều nhất một con thỏ, vì như vậy tối đa chỉ nhốt được 4 con. Vậy phải có một chuồng chứa ít nhất hai con thỏ.
Điều làm nguyên lí này mạnh là nó đúng bất kể em nhốt như thế nào . Ta không cần biết cách nhốt, chỉ cần biết số thỏ và số chuồng.
Nguyên lí Dirichlet (dạng cơ bản)
Nếu nhốt N đối tượng ("thỏ") vào k nhóm ("chuồng") mà N\gt k thì có ít nhất một nhóm chứa từ hai đối tượng trở lên.
Nguyên lí Dirichlet (dạng mở rộng)
Nếu nhốt N đối tượng vào k nhóm và N\gt m\cdot k (với m là số tự nhiên) thì có ít nhất một nhóm chứa từ m+1 đối tượng trở lên. Nói gọn: có nhóm chứa ít nhất \left\lceil \frac{N}{k}\right\rceil đối tượng.
Kí hiệu \lceil x\rceil đọc là "trần của x", là số nguyên nhỏ nhất không nhỏ hơn x. Ví dụ \lceil 8{,}33\rceil=9 còn \lceil 8\rceil=8.
Vì sao đúng: phản chứng
Chứng minh dạng mở rộng
Giả sử điều cần chứng minh sai: mọi nhóm đều chứa nhiều nhất m đối tượng.
Phủ định của "có nhóm chứa ít nhất m+1" là "mọi nhóm chứa nhiều nhất m". Chứng minh phản chứng luôn bắt đầu bằng việc viết đúng phủ định.
Khi đó tổng số đối tượng ở k nhóm nhiều nhất là m\cdot k, nghĩa là N\le m\cdot k.
Cộng k số, mỗi số không vượt quá m, thì tổng không vượt quá m\cdot k.
Điều này mâu thuẫn với giả thiết N\gt m\cdot k. Vậy có ít nhất một nhóm chứa từ m+1 đối tượng trở lên.
Mâu thuẫn xuất hiện nên giả sử ban đầu sai, tức khẳng định đúng.
GV
Cô Lukato
Nhớ cụm "nếu ai cũng ít thì tổng phải ít". Gần như mọi bài Dirichlet đều được chứng minh bằng đúng một dòng như vậy. Khó khăn thật sự nằm ở việc tự tạo ra các chuồng .
Ba câu hỏi trước khi dùng Dirichlet
Câu hỏi · Ở bài 244 điểm
Ai là "thỏ"? · 244 điểm đã cho.
Ai là "chuồng"? · Các tam giác đều nhỏ do ta tự chia (chưa biết chia thành bao nhiêu ô).
Muốn có bao nhiêu thỏ cùng chuồng? · Bốn điểm, vì bốn điểm mới là bốn đỉnh của một tứ giác.
Ví dụ 1 · Bao nhiêu bạn cùng tháng sinh?
Đề: trong trường có 100 học sinh khối 9 đến dự tuyển. Chứng minh có ít nhất 9 bạn sinh cùng một tháng (không tính năm).
Thấy "ít nhất" và "cùng" là tín hiệu của Dirichlet.
Thỏ là 100 học sinh, chuồng là 12 tháng trong năm. Tính \frac{100}{12}=8{,}33\ldots
Số chuồng là 12 chứ không phải 365 hay 30; em phải chọn đúng tiêu chí phân loại.
Giả sử mọi tháng có nhiều nhất 8 bạn, khi đó tổng nhiều nhất là 8\times 12=96\lt 100, mâu thuẫn.
Ta chọn m=8 vì 8\times 12=96 là bội của 12 ngay dưới 100.
Vậy có tháng chứa ít nhất 9 bạn. Đây cũng chính là \left\lceil \frac{100}{12}\right\rceil=9.
Kết quả 9 là số nguyên, còn 8{,}33 chỉ là "số trung bình", không thể có 8{,}33 bạn.
Bẫy thường gặp
Nhiều em thấy \frac{100}{12}\approx 8{,}33 rồi kết luận "có ít nhất 8 bạn cùng tháng". Kết luận này đúng nhưng yếu , không phải điều tốt nhất. Vì số bạn phải là số nguyên, trung bình 8{,}33 buộc có tháng từ 9 bạn trở lên. Nguyên tắc: làm tròn lên , không làm tròn xuống. Sai lầm ngược lại là dùng N\gt m\cdot k với m quá nhỏ, khiến kết luận yếu hơn mức có thể.
Bẫy thường gặp
Chọn chuồng mà không kiểm tra mọi thỏ đều có chuồng . Ví dụ chia học sinh theo "mùa" nhưng một bạn sinh đúng ngày chuyển mùa thì bạn ấy thuộc mùa nào? Với hình học, điểm nằm đúng trên đường kẻ giữa hai ô là chỗ dễ sơ hở nhất; ta sẽ xử lí kĩ ở Mục 5.
Bài 1 Mức 1 · Nhận biết
Có 100 học sinh, mỗi bạn sinh vào một trong 12 tháng. Số k lớn nhất mà chắc chắn có ít nhất k bạn sinh cùng một tháng bằng bao nhiêu?
Gợi ý 1. Thỏ là học sinh, chuồng là tháng. Hãy tính \frac{100}{12}.
Gợi ý 2. Số bạn trong một tháng là số nguyên; hãy làm tròn lên.
Chính xác! \left\lceil \frac{100}{12}\right\rceil=9: nếu mọi tháng chỉ có nhiều nhất 8 bạn thì tổng chỉ tối đa 96.
Em đã làm tròn xuống: 100:12=8{,}33\ldots nên phải làm tròn lên 9.
Có thể xếp để mọi tháng chỉ có nhiều nhất 9 bạn (ví dụ 8 bạn mỗi tháng và 4 tháng có 9 bạn), nên không thể chắc chắn có 10 bạn cùng tháng.
Lời giải mở sau khi em làm đúng, thử 2 lần, hoặc xem hết gợi ý.
Lời giải
Nếu mọi tháng có nhiều nhất 8 bạn thì tổng số bạn nhiều nhất là 8\times 12=96\lt 100, mâu thuẫn. Vậy có tháng chứa ít nhất 9 bạn. Có thể xảy ra đúng 9? Có: xếp 8 bạn vào mỗi tháng, thêm 4 bạn còn lại vào bốn tháng khác nhau. Do đó 9 là giá trị tốt nhất.
Bài 2 Mức 1 · Nhận biết
Cần ít nhất bao nhiêu điểm rải vào 25 ô để chắc chắn có một ô chứa ít nhất 4 điểm?
Gợi ý 1. Muốn ép có ô chứa 4 điểm, hãy nghĩ đến trường hợp xấu nhất: mọi ô đều chứa 3 điểm.
Gợi ý 2. Trường hợp xấu nhất chứa bao nhiêu điểm? Thêm một điểm nữa thì sao?
Chính xác! Trường hợp xấu nhất chứa 3\times 25=75 điểm mà chưa có ô nào chứa 4; điểm thứ 76 ép được.
Với 75 điểm ta vẫn có thể xếp mỗi ô đúng 3 điểm, chưa ép được 4.
Đây là 4\times 25: chỉ đủ khi muốn mỗi ô đều chứa 4 điểm, còn ở đây chỉ cần một ô.
Lời giải mở sau khi em làm đúng, thử 2 lần, hoặc xem hết gợi ý.
Lời giải
Nếu mọi ô chứa nhiều nhất 3 điểm thì tổng số điểm nhiều nhất là 3\times 25=75. Vậy chỉ cần 76 điểm là chắc chắn có ô chứa ít nhất 4 điểm. Với 75 điểm, xếp đúng 3 điểm mỗi ô thì không ô nào có 4 điểm. Vậy số nhỏ nhất cần tìm là 76.
Mở rộng: tổng quát hóa công thức
Với k chuồng, để chắc chắn có chuồng chứa ít nhất r thỏ, số thỏ nhỏ nhất cần dùng là (r-1)k+1. Ở Bài 2: r=4, k=25 cho (4-1)\times 25+1=76. Ở bài 244 điểm: r=4 và k=81 cho 3\times 81+1=244. Con số kì lạ 244 chỉ là (r-1)k+1 với r=4, k=81.
3 Lưới tam giác đều: chuồng của bài toán
Xây dựng n^{2} ô bằng nhau, đếm ô, tính diện tích và quy ước gán điểm.
Chuồng của ta sẽ là các tam giác nhỏ. Muốn Dirichlet dùng được, các chuồng phải bằng nhau về diện tích để so sánh với con số \frac{2}{27} và phải phủ kín tam giác để không điểm nào thoát ra ngoài. Cách chia tự nhiên nhất là chia mỗi cạnh thành n phần bằng nhau.
Cách chia lưới
Chia mỗi cạnh của tam giác đều ABC thành n đoạn bằng nhau. Qua mỗi điểm chia kẻ đường thẳng song song với hai cạnh còn lại. Ba họ đường thẳng song song với ba cạnh chia tam giác ABC thành các tam giác đều nhỏ. Ta gọi mỗi tam giác nhỏ đó là một ô .
Hình 1. Với 3 phần mỗi cạnh: 6 ô hướng lên (số 1 đến 6) và 3 ô hướng xuống (số 7 đến 9), tất cả là 9 ô.
Hình 1 là trường hợp nhỏ nhất đủ để thấy quy luật: n=3 cho 9 ô, trong đó có hai kiểu ô. Ô hướng lên (tô nhạt) có đỉnh quay lên trên giống tam giác lớn, còn ô hướng xuống (tô đậm) có đỉnh quay xuống dưới.
Vì sao các ô đều là tam giác đều cạnh a/n?
Đặt các điểm chia ở đáy là L(i, 0) và ở cạnh trái là L(0, j). Nói rộng hơn, gọi L(i, j) là điểm có được khi đi i bước theo chiều đáy và j bước theo chiều cạnh trái, mỗi bước dài \frac{a}{n} (với a là cạnh tam giác lớn). Hai chiều đó tạo góc 60^{\circ}.
- Ô hướng lên có ba đỉnh L(i, j), L(i+1, j), L(i, j+1). Hai cạnh xuất phát từ L(i, j) cùng dài \frac{a}{n} và tạo góc 60^{\circ}; tam giác cân có góc ở đỉnh 60^{\circ} là tam giác đều.
- Ô hướng xuống có ba đỉnh L(i+1, j), L(i, j+1), L(i+1, j+1). Ở đỉnh L(i+1, j+1), hai cạnh nối tới hai đỉnh kia dài \frac{a}{n} và cũng tạo góc 60^{\circ}; nên đây cũng là tam giác đều cạnh \frac{a}{n}.
Vậy mọi ô đều là tam giác đều cạnh \frac{a}{n}, do đó bằng nhau (cạnh-cạnh-cạnh). Ta suy ra diện tích mỗi ô là như nhau.
Đếm ô và tính diện tích
Đếm theo hàng từ đỉnh xuống đáy. Hàng thứ nhất chỉ có 1 ô hướng lên. Hàng thứ hai có 2 ô hướng lên và 1 ô hướng xuống, tổng 3 ô. Cứ như vậy hàng thứ k có k ô hướng lên và k-1 ô hướng xuống, tổng 2k-1 ô.
1+3+5+\cdots+(2n-1)=n^{2}
Tổng của n số lẻ đầu tiên bằng n^{2}: viết tổng hai lần, một lần theo thứ tự tăng và một lần theo thứ tự giảm, cộng từng cặp được n số hạng, mỗi số hạng bằng 2n, nên gấp đôi tổng bằng 2n^{2}. Vậy có đúng n^{2} ô. Trong đó số ô hướng lên là 1+2+\cdots+n=\frac{n(n+1)}{2}, số ô hướng xuống là 0+1+\cdots+(n-1)=\frac{n(n-1)}{2}.
Kết quả cần nhớ
Chia mỗi cạnh thành n phần: có n^{2} ô bằng nhau, gồm \frac{n(n+1)}{2} ô hướng lên và \frac{n(n-1)}{2} ô hướng xuống. Nếu tam giác có diện tích S thì mỗi ô có diện tích \frac{S}{n^{2}}.
Về diện tích: các ô bằng nhau và phủ kín tam giác nên diện tích tam giác chia đều cho n^{2} ô. Cũng có thể kiểm tra bằng tỉ số đồng dạng: mỗi ô đồng dạng với tam giác lớn theo tỉ số \frac{1}{n}, nên diện tích của ô bằng \frac{1}{n^{2}} diện tích tam giác lớn.
Hình 2. Chia mỗi cạnh làm 9 phần rồi kẻ các đường song song với ba cạnh: được 81 ô. Hai ô được tô màu để làm ví dụ: ô xanh nhạt hướng xuống, ô xanh đậm hướng lên.
GV
Cô Lukato
Hình 2 là lưới 9\times 9 của bài toán. Em thử đếm nhanh: hàng dưới cùng có 17 ô, gồm 9 ô hướng lên xen kẽ 8 ô hướng xuống. Cộng cả 9 hàng ta được 81.
n · Số ô · Lên · Xuống · Diện tích
3 · 9 · 6 · 3 · 2/3
5 · 25 · 15 · 10 · 6/25
9 · 81 · 45 · 36 · 2/27
Trong bảng, "Lên" và "Xuống" là số ô hướng lên và hướng xuống; "Diện tích" là diện tích một ô khi tam giác lớn có diện tích 6.