Thế nào là nguyên tắc ô kéo?

Có sáu quyển sách cần xếp vào năm ô kéo. Dù có nhiều cách xếp khác nhau, có ô không có quyển nào, có ô có một quyển, hai quyển, thậm chí nhiều hơn, thì chắc chắn vẫn có ít nhất một ô chứa từ hai quyển sách trở lên.

Nếu xem mỗi ô kéo là một tập hợp, mỗi quyển sách là một phần tử của tập hợp, ta có thể phát biểu tổng quát hơn: nếu có n + 1 hoặc nhiều hơn n + 1 phần tử được xếp vào n tập hợp, thì ít nhất có một tập hợp chứa từ hai phần tử trở lên. Đó là ý nghĩa trừu tượng của nguyên tắc ô kéo, hay còn gọi là nguyên lý Dirichlet.

Ví dụ, trong một lớp có 54 học sinh, giả sử các em đều sinh cùng một năm, thì ít nhất có hai học sinh sinh trong cùng một tuần. Vì một năm có 53 tuần, nếu xem mỗi tuần là một ô kéo và mỗi học sinh là một quyển sách, 54 học sinh xếp vào 53 tuần thì chắc chắn có một tuần có ít nhất hai học sinh sinh ra.

Số phần tử không nhất thiết chỉ nhiều hơn số ô một đơn vị. Chẳng hạn, có 31 quyển sách xếp vào 5 ô kéo thì dù xếp thế nào, ít nhất một ô phải có 7 quyển sách. Tổng quát hơn, nếu có m x n + 1 hoặc nhiều hơn số đó phần tử xếp vào n tập hợp, thì ít nhất một tập hợp có m + 1 phần tử.

Nguyên tắc ô kéo có thể dùng để giải “bài toán nhóm 6 người”: trong bất kỳ nhóm 6 người nào, ít nhất có 3 người từng bắt tay nhau, hoặc ít nhất có 3 người chưa từng bắt tay nhau.

Bài toán 3x + 1 cũng là một trò chơi số học nổi tiếng. Chọn tùy ý một số tự nhiên x. Nếu x là số chẵn thì chia cho 2; nếu x là số lẻ thì nhân 3 rồi cộng 1. Lặp lại quy tắc này liên tục, ta sẽ được một dãy số mới.

Ví dụ, bắt đầu từ số 18 hoặc số 21, sau nhiều bước biến đổi, cuối cùng đều rơi vào vòng tuần hoàn 4, 2, 1. Ban đầu đây chỉ là một trò chơi số học ở Mỹ, sau đó lan sang châu Âu, rồi sang châu Á và nhiều nơi khác trên thế giới.

Người ta đã dùng máy tính kiểm tra rất nhiều số tự nhiên, thậm chí đến những phạm vi rất lớn, và đều thấy cuối cùng xuất hiện vòng 4, 2, 1. Bài toán này được gọi là bài toán 3x + 1, hay vấn đề Collatz. Tuy vậy, cho đến nay kết luận tổng quát vẫn chưa có chứng minh hoàn chỉnh trong phạm vi số tự nhiên.