Nguyên lí Dirichlet: chọn nhóm để chứng minh điều chắc chắn
Chuyên đề Toán THCS về nguyên lí Dirichlet, sức chứa và ngưỡng, số dư, chẵn lẻ tọa độ, phần lẻ và chiều chia hết; chứng minh tồn tại, phản ví dụ và điều kiện…
CHUYÊN ĐỀ TOÁN THCS · LẬP LUẬN TỒN TẠI
Nguyên lí Dirichlet: chọn nhóm để chứng minh điều chắc chắn
Có những tình huống không cần tìm ngay đối tượng cụ thể: chỉ cần số lượng và một cách phân nhóm đúng, ta đã chứng minh được điều chắc chắn tồn tại. Khó khăn không nằm ở phép chia, mà ở việc tạo nhóm sao cho hai đối tượng cùng nhóm mang tính chất cần tìm.
Chuẩn bị: số nguyên, phép chia có dư, chẵn lẻ, lũy thừa của 2, trung điểm trong mặt phẳng tọa độ. Mục tiêu: phát biểu đúng nguyên lí; dựng nhóm bao quát và không chồng lấn; phân biệt tồn tại với mọi trường hợp; kiểm tra ngưỡng bằng phản ví dụ. Mọi tình huống dưới đây tự biên soạn để học phương pháp, không kèm đề thi hoặc bảng điểm.
1. Vì sao nhiều vật hơn ngăn buộc một ngăn có ít nhất hai vật?
Giả sử N đối tượng được xếp vào k nhóm, mỗi đối tượng thuộc đúng một nhóm, N,k là số nguyên dương. Nếu N>k, có ít nhất một nhóm chứa ít nhất hai đối tượng.
Chứng minh bằng phản chứng: giả sử mỗi nhóm chứa nhiều nhất một đối tượng. Khi đó tổng số đối tượng không vượt quá số nhóm k, trái với N>k. Vì vậy giả sử ấy không thể đúng.
Không cần các nhóm có kích thước bằng nhau, không cần mọi nhóm đều có người, và không cần biết trước nhóm đông là nhóm nào. Tên “thỏ và chuồng” chỉ là hình ảnh; trong ứng dụng, đối tượng có thể là số, điểm hoặc một lựa chọn.
Kết luận là có ít nhất một nhóm , không phải mọi nhóm đều có hai đối tượng. Nguyên lí cũng không tự chỉ ra tên cặp cụ thể; muốn tìm cặp, phải quan sát hoặc phân loại các đối tượng thực tế.
Dự đoán: 6 vật trong 6 ngăn có bảo đảm một ngăn chứa hai vật không?
Không. Có thể mỗi ngăn một vật. Nhưng cũng có cách xếp làm một ngăn rất đông. “Không bảo đảm” không có nghĩa “không thể xảy ra”; nó có nghĩa tồn tại ít nhất một cách xếp không đạt tính chất ấy.
2. Bản tổng quát: từ sức chứa tối đa đến ngưỡng
Muốn bảo đảm một nhóm có ít nhất q đối tượng, với q\ge2 nguyên, hãy giả sử mọi nhóm chỉ có nhiều nhất q-1. Tổng khi ấy không vượt k(q-1). Nếu số đối tượng lớn hơn mức này, giả sử bị bác bỏ.
Gọi n_j là số đối tượng trong nhóm thứ j, với j=1,\ldots,k.
N>k(q-1)\quad\Longrightarrow\quad\max(n_1,\ldots,n_k)\ge q.
Vì số lượng là số nguyên, ngưỡng đủ là k(q-1)+1. Khi việc xếp vào các nhóm không bị ràng buộc thêm, ngưỡng này tối ưu: với đúng k(q-1) đối tượng, có thể cho mỗi nhóm q-1, chưa nhóm nào đạt q.
Một cách viết tương đương của mức bảo đảm tổng quát là:
\max(n_1,\ldots,n_k)\ge\left\lceil\frac Nk\right\rceil,\qquad n_1+\cdots+n_k=N.
Kí hiệu trần là số nguyên nhỏ nhất không nhỏ hơn số bên trong. Đây là chặn dưới cho nhóm đông nhất, không phải khẳng định nhóm đông nhất luôn có đúng số đó.
Ví dụ tự biên soạn: xếp 13 thẻ vào 5 ngăn, chắc chắn có một ngăn ít nhất 3 thẻ. Hình dưới là một cách xếp đạt đúng mức bảo đảm, với số thẻ 3,3,3,2,2.
Nếu dồn cả 13 thẻ vào một ngăn, nhóm đông nhất là 13, vẫn phù hợp với kết luận “ít nhất 3”. Ví dụ cân đối giúp kiểm tra ngưỡng, không mô tả mọi cách xếp.
3. Chọn nhóm theo điều cần kết luận, không theo vẻ giống nhau
Ba câu hỏi tạo một mô hình đúng: đối tượng là gì; có bao nhiêu nhóm và mỗi đối tượng thuộc nhóm nào; hai đối tượng cùng nhóm có bảo đảm tính chất cần tìm không?
Mục tiêu · Nhóm hợp lí · Điều cùng nhóm bảo đảm
Hai số có hiệu chia hết cho m · Số dư khi chia cho m>0 · Hai số dư bằng nhau nên hiệu chia hết
Hai điểm có trung điểm nguyên · Cặp chẵn lẻ của cả hai tọa độ · Tổng từng cặp tọa độ đều chẵn
Hai số dương mà số lớn là bội của số nhỏ · Phần lẻ sau khi tách mọi thừa số 2 · Cùng phần lẻ, chỉ khác lũy thừa của 2
Một cách phân nhóm có thể rất đẹp mà không phục vụ mục tiêu. Ví dụ, để xét hiệu chia hết cho 4, chỉ chia số thành chẵn và lẻ chưa đủ: 2 và 4 cùng chẵn nhưng hiệu 2 không chia hết cho 4.
Kiểm tra cả hai điều: nhóm phải tạo một phân loại hợp lệ của mọi đối tượng đang xét, và cùng nhóm phải đủ để suy ra kết luận. Đếm nhiều hơn số nhóm mà thiếu điều thứ hai chỉ chứng minh “có hai đối tượng cùng nhóm”, chưa chứng minh tính chất mong muốn.
4. Số dư: một lớp chứa nhiều số nhưng có một tính chất chung
Với số nguyên a và số nguyên dương m, viết a=mt+r, trong đó 0\le r<m. Có m số dư khả dĩ từ 0 đến m-1. Nếu hai số a,b cùng dư r, thì:
a=mu+r,\quad b=mv+r\quad\Longrightarrow\quad a-b=m(u-v).
Vì thế hiệu chia hết cho m. Chọn m+1 số nguyên bất kì theo các vị trí trong một danh sách, ta bảo đảm hai vị trí có số cùng dư. Các giá trị có thể trùng nhau; nếu trùng, hiệu 0 vẫn chia hết cho m.
Số âm vẫn cần dư đúng miền: -5=4(-2)+3, nên dư khi chia -5 cho 4 là 3; 7=4\cdot1+3 cũng dư 3. Hiệu 7-(-5)=12 chia hết cho 4. Không gọi -1 là số dư trong quy ước 0\le r<4.
Hiệu chia hết khác tổng chia hết. Hai số cùng dư 1 khi chia 4 có hiệu chia hết cho 4, nhưng tổng dư 2, không chia hết. Muốn xét tổng, phải thiết kế nhóm hoặc ghép dư theo một quan hệ khác.
Dự đoán: chỉ có4số nguyên thì hiệu chia hết4 có luôn tồn tại không?
Không. Danh sách 0,1,2,3 có bốn số dư khác nhau; mọi hiệu giữa hai vị trí phân biệt có trị tuyệt đối từ 1 đến 3. Đây là một phản ví dụ kiểm tra ngưỡng, không nói mọi danh sách bốn số đều thất bại.
5. Tọa độ nguyên: phải phân loại cả hai tọa độ cùng lúc
Trung điểm của P(x_1,y_1) và Q(x_2,y_2) có tọa độ:
\left(\frac{x_1+x_2}{2},\frac{y_1+y_2}{2}\right).
Muốn trung điểm có hai tọa độ nguyên, cả hai tổng phải chẵn. Vì vậy cần hai hoành độ cùng tính chẵn lẻ và hai tung độ cùng tính chẵn lẻ. Có bốn nhóm: chẵn–chẵn, chẵn–lẻ, lẻ–chẵn, lẻ–lẻ.
Ví dụ để kiểm tra một nhóm: P(2,1),Q(6,5),T(8,3) cùng nhóm chẵn–lẻ. Ba trung điểm của các cặp trong nhóm này lần lượt là (4,3),(5,2),(7,4), đều nguyên. Trong 9 điểm nguyên phân biệt, nguyên lí bảo đảm ít nhất 3 điểm ở một nhóm; vì vậy mọi cặp trong nhóm ba điểm ấy có trung điểm nguyên.
Không suy ra mọi cặp trong toàn bộ 9 điểm đều tốt. Các điểm ở nhóm khác vẫn có thể cho trung điểm không nguyên. Kết luận rộng đến đâu phụ thuộc đối tượng “trong cùng nhóm” mà ta đã chọn.
Chỉ xét hoành độ là thiếu: P(2,1) và S(6,2) cùng hoành độ chẵn, nhưng trung điểm (4,3/2) không có tung độ nguyên. Phản ví dụ này chỉ ra chính xác phần phân loại bị bỏ sót.
Tự thử: có thể ghép “x chẵn” với “y chẵn” làm hai nhóm riêng không?
Không tạo phân loại đúng một nhóm: một điểm có thể vào cả hai hoặc không vào nhóm nào. Phải dùng cặp chẵn lẻ để mỗi điểm vào đúng một trong bốn nhóm, đồng thời giữ cả hai điều kiện cho trung điểm.
6. Phần lẻ: bảo toàn thứ gì khi tách thừa số2?
Mỗi số nguyên dương n viết duy nhất dưới dạng n=2^s u, với s\ge0 nguyên và u lẻ dương. Ta chia n cho 2 liên tiếp đến khi còn số lẻ; số còn lại là phần lẻ.
12=2^2\cdot3,\qquad24=2^3\cdot3.
Hai số cùng phần lẻ u có dạng 2^s u,2^t u. Nếu s<t, số lớn bằng số nhỏ nhân với 2^{t-s}; do đó số lớn là bội của số nhỏ . Nói “số nhỏ chia hết cho số lớn” là đảo chiều. Cách nói đúng khác là “số lớn chia hết cho số nhỏ”.
Trong tập \{1,2,\ldots,24\}, phần lẻ có 12 khả năng: các số lẻ từ 1 đến 23. Bởi vậy chọn 13 giá trị phân biệt trong tập, chắc chắn có hai số cùng phần lẻ, tạo một cặp chia hết như trên.
Phần lẻ · Một số nhóm trong tập1–24 · Quan hệ trong nhóm
1 · 1,2,4,8,16 · Chỉ khác số lần nhân 2
3 · 3,6,12,24 · Số lớn là bội số nhỏ
5 · 5,10,20 · Số lớn là bội số nhỏ
13 · 13 · Có nhóm chỉ một phần tử
Kiểm tra tối ưu: chọn 12 số từ 13 đến 24. Với hai số phân biệt trong đó, số lớn nhỏ hơn hai lần số nhỏ, nên không thể là bội nguyên từ 2 trở lên của số nhỏ. Không có cặp tốt; do đó ngưỡng 13 là nhỏ nhất.
Phần lẻ cùng nhau là điều kiện đủ cho cặp chia hết, không phải điều kiện cần. Ví dụ 3 và 9 có phần lẻ khác nhau nhưng 9 vẫn chia hết cho 3. Ta chỉ cần nhóm đảm bảo tính chất, không cần nhóm chứa mọi cặp có tính chất ấy.
7. Viết một chứng minh tồn tại và thử phản ví dụ
Một chứng minh đầy đủ có bốn việc: định nghĩa nhóm; xác nhận mỗi đối tượng vào đúng một nhóm; so số lượng với sức chứa; chuyển “cùng nhóm” thành tính chất đích. Nếu yêu cầu ngưỡng nhỏ nhất, cần thêm một cách xếp ngay dưới ngưỡng không có tính chất.
Tình huống tự biên soạn: có 25 người, phân theo tháng sinh. Vì có 12 tháng, nếu mỗi tháng nhiều nhất 2 người thì tổng nhiều nhất 24. Vậy ít nhất một tháng có 3 người. Đây là kết luận cùng tháng sinh, không bảo đảm cùng ngày sinh.
Các tháng có thể có số ngày khác nhau nhưng ta đang đếm tháng, không tính xác suất. Nguyên lí không cần các nhóm có cùng khả năng xảy ra. Nó là lập luận đếm về mọi cách phân loại hợp lệ.
Một hình vẽ minh họa một cách xếp không chứng minh mọi cách xếp. Chứng minh tổng quát phải dùng sức chứa hoặc mâu thuẫn. Ngược lại, để bác bỏ một khẳng định “luôn”, chỉ cần một cách xếp hợp lệ không đạt tính chất.
Dự đoán: cần bao nhiêu đối tượng trong4nhóm để bảo đảm một nhóm ít nhất5?
Nếu mỗi nhóm nhiều nhất 4, tổng nhiều nhất 16; nên 17 đối tượng đủ. Với 16, cách xếp 4,4,4,4 không nhóm nào đạt 5. Trong mô hình không thêm ràng buộc, 17 là ngưỡng tối ưu.
8. Tự kiểm tra: chọn nhóm trước khi dùng công thức
A. Chia 18 vật vào 7 ngăn. Mức chắc chắn cho ngăn đông nhất là gì? Có được nói ngăn đông nhất luôn có đúng mức ấy không?
Gợi ý A
Nếu mỗi ngăn nhiều nhất 2, tổng tối đa chỉ 14. Để kiểm tra mức cao hơn, thử xếp 3,3,3,3,2,2,2.
Kiểm tra A
Bảo đảm ít nhất 3; cách xếp trên có tổng 18 và ngăn lớn nhất 3, nên không bảo đảm 4. Nhưng có thể dồn cả 18 vào một ngăn; vì vậy không khẳng định “luôn đúng 3”.
B. Hai số cùng dư 2 khi chia 5. Điều gì được bảo đảm về tổng và hiệu?
Kiểm tra B
Hiệu chia hết cho 5. Tổng có dạng 5(u+v)+4, dư 4, không chia hết cho 5. Cùng số dư không cho cùng kết luận về tổng và hiệu.
C. Trong phân loại điểm nguyên, một bạn chỉ dùng hai nhóm hoành độ chẵn và lẻ rồi kết luận trung điểm nguyên.
Kiểm tra C
Cách phân loại đúng là một phân hoạch, nhưng thiếu điều kiện về tung độ. Nó chỉ bảo đảm hoành độ của trung điểm nguyên cho cặp cùng nhóm. Để cả hai tọa độ nguyên, cần bốn cặp chẵn lẻ.
D. Hai số 6,12 cùng phần lẻ. Hãy viết hai câu chia hết đúng chiều.
Kiểm tra D
12 là bội của 6; 12 chia hết cho 6. Không viết 6 chia hết cho 12. “Là ước của” đảo cách gọi: 6 là ước của 12.
Phiếu rà: đối tượng và nhóm có rõ không? Mỗi đối tượng vào đúng một nhóm chưa? Cùng nhóm có đủ cho tính chất đích không? Ngưỡng dùng dấu lớn hơn hay lớn hơn hoặc bằng? Kết luận “tồn tại” có bị đổi thành “mọi” không? Nếu nói tối ưu, đã có phản ví dụ dưới ngưỡng chưa? Quan hệ chia hết có đúng chiều không?
Nguyên lí Dirichlet mạnh vì nó biến việc tìm một đối tượng thành việc giới hạn sức chứa. Một cách phân nhóm tốt vừa giữ được điều kiện của đối tượng vừa tạo ra đúng tính chất cần chứng minh.