Đặt vấn đề

Có một sự thật hơi buồn của vũ trụ:

Không phải lúc nào cũng còn đủ chỗ để chúng ta khác nhau.

Giả sử có 11 con chim bồ câu và 10 cái chuồng. Mỗi con chim có thể rất cá tính: con thứ nhất thích jazz, con thứ hai nghe bolero, con thứ ba đang suy nghĩ về ý nghĩa cuộc đời.

Nhưng mặc kệ nội tâm phong phú đến đâu, nếu cả 11 con đều phải chui vào 10 cái chuồng thì ít nhất một chuồng sẽ chứa từ hai con trở lên.

Không cần biết chúng bay theo thứ tự nào. Không cần xác suất, AI hay một triệu lần mô phỏng. Chỉ cần biết:

111 con chim
210 cái chuồng

là đủ kết luận:

1Ít nhất hai con chim phải chung một chuồng.

Đó là nguyên lý chuồng bồ câu (Pigeonhole Principle).

Nghe giống kiến thức dành cho lớp mẫu giáo, nhưng đây lại là một trong những ý tưởng nền tảng của toán học tổ hợp, lý thuyết số và khoa học máy tính. MIT mở đầu học phần Principles of Discrete Applied Mathematics bằng nguyên lý này cùng nhiều ứng dụng bất ngờ. (MIT OpenCourseWare)

Điều thú vị không nằm ở con chim hay cái chuồng. Nó nằm ở một ý sâu hơn:

Khi số trạng thái mà thế giới cho phép ít hơn số thứ ta muốn phân biệt, sự trùng lặp không còn là khả năng. Nó trở thành điều bắt buộc.

Nguyên lý nói gì?

Phiên bản cơ bản nhất là:

Nếu có $n+1$ vật được đặt vào $n$ hộp thì tồn tại ít nhất một hộp chứa từ hai vật trở lên.

Phiên bản tổng quát mạnh hơn một chút:

Nếu $N$ vật được chia vào $K$ hộp, với $K > 0$, thì tồn tại ít nhất một hộp chứa tối thiểu

$$ \left\lceil \frac{N}{K} \right\rceil $$

vật. Ký hiệu $\lceil x \rceil$ nghĩa là làm tròn $x$ lên số nguyên gần nhất. (MathWorld)

Ví dụ, đặt 100 con chim vào 9 chuồng:

$$ \left\lceil \frac{100}{9} \right\rceil = 12. $$

Bất kể phân bố thế nào, ít nhất một chuồng phải chứa từ 12 con trở lên.

Một chứng minh chỉ mất vài dòng

Giả sử ngược lại rằng mọi chuồng đều chứa nhiều nhất

$$ \left\lceil \frac{N}{K} \right\rceil - 1 $$

vật. Khi đó tổng số vật tối đa trong $K$ chuồng là

$$ K\left(\left\lceil \frac{N}{K} \right\rceil - 1\right) < N, $$

mâu thuẫn với việc ta đã đặt đủ $N$ vật vào các chuồng. Vậy phải có ít nhất một chuồng đạt ngưỡng $\left\lceil N/K \right\rceil$.

Đây không phải dự đoán về cách các vật sẽ phân bố. Nó là một cận dưới không thể né tránh.

Kỹ năng thật sự: tìm đúng “chim” và “chuồng”

Nếu đề bài nói thẳng “13 con chim và 12 cái chuồng” thì gần như ai cũng nhìn ra. Nhưng bài toán thật không tử tế như vậy. Chim và chuồng thường hóa trang thành những thứ khác:

Kỹ năng quan trọng không phải là thuộc lòng câu “nhiều chim hơn chuồng”. Kỹ năng thật sự là:

Nhìn một bài toán hỗn loạn rồi nhận ra đâu là vật đang được phân loại, đâu là các trạng thái dùng để phân loại chúng.

Từ đôi tất đến số học modulo

13 người và 12 tháng

Giả sử trong phòng có 13 người. Mỗi người được đưa vào “chuồng” tương ứng với tháng sinh của mình:

113 người  → 13 con chim
212 tháng  → 12 cái chuồng

Vì có nhiều người hơn số tháng, chắc chắn tồn tại ít nhất hai người sinh cùng tháng.

Nguyên lý không cho ta biết đó là hai người nào. Nó chỉ chứng minh rằng họ phải tồn tại. Đây là điểm đẹp của kiểu chứng minh tồn tại: ta biết có đáp án mà chưa cần tìm ra đáp án cụ thể.

Lấy tất trong bóng tối

Một ngăn kéo có tất thuộc 5 màu. Bạn tắt đèn và lấy từng chiếc. Năm chiếc đầu tiên vẫn có thể mang năm màu khác nhau, nhưng chiếc thứ sáu bắt buộc phải trùng màu với một chiếc đã lấy.

16 chiếc tất  → chim
25 màu        → chuồng

Vậy phải lấy 6 chiếc để bảo đảm có hai chiếc cùng màu.

Từ khóa quan trọng là “bảo đảm”: không phải khả năng cao hay 99,99%, mà là không tồn tại cách phân bố nào thoát được.

11 số nguyên và 10 số dư

Khi chia một số nguyên cho 10, số dư chỉ có thể là:

10, 1, 2, 3, 4, 5, 6, 7, 8, 9

Lấy 11 số nguyên bất kỳ, ta có 11 “chim” nhưng chỉ 10 lớp số dư. Vì vậy tồn tại hai số $a$ và $b$ có cùng số dư khi chia cho 10:

$$ a \equiv b \pmod{10}. $$

Suy ra:

$$ a-b \equiv 0 \pmod{10}, $$

hay $a-b$ chia hết cho 10.

Từ một đàn bồ câu, ta vừa bước sang số học modulo. Con chim vẫn còn đó; nó chỉ mặc áo khác.

Khi đề bài không cho sẵn cái chuồng

Không phải lúc nào “chuồng” cũng tồn tại sẵn. Đôi khi ta phải tự xây nó.

Giả sử có 5 điểm nằm trong một hình vuông cạnh 2. Chia hình vuông lớn thành 4 hình vuông nhỏ cạnh 1:

1+-----+-----+
2|     |     |
3+-----+-----+
4|     |     |
5+-----+-----+

Khi đó:

15 điểm            → chim
24 hình vuông nhỏ  → chuồng

Ít nhất một hình vuông nhỏ phải chứa hai điểm. Khoảng cách lớn nhất giữa hai điểm trong hình vuông cạnh 1 là độ dài đường chéo:

$$ \sqrt{1^2+1^2}=\sqrt{2}. $$

Vậy trong 5 điểm ban đầu, chắc chắn có hai điểm cách nhau không quá $\sqrt{2}$.

Bài toán không hề nhắc tới hộp. Ta tự chia không gian thành các vùng rồi dùng nguyên lý chuồng bồ câu để ép hai điểm vào cùng một vùng. Đây là một kỹ thuật quan trọng trong toán tổ hợp và hình học rời rạc: muốn dùng nguyên lý, đôi khi phải thiết kế cái chuồng trước.

Hash function: chuồng bồ câu ở tầng silicon

Giả sử một hàm hash có đầu ra 32 bit. Dù được thiết kế tốt đến đâu, nó cũng chỉ tạo được

$$ 2^{32}=4.294.967.296 $$

giá trị khác nhau.

Trong khi đó, tập hợp các chuỗi có thể đưa vào hàm là lớn hơn rất nhiều; nếu cho phép chuỗi dài tùy ý thì tập input là vô hạn. Vì số input lớn hơn số giá trị đầu ra, chắc chắn tồn tại hai input khác nhau $x \ne y$ sao cho

$$ h(x)=h(y). $$

Collision là không thể tránh khỏi.

Không phải vì lập trình viên viết hàm hash dở hay CPU hôm đó buồn. Toán học đơn giản là không cho phép một miền lớn hơn ánh xạ vào một miền hữu hạn mà mọi phần tử vẫn giữ được giá trị riêng.

Một hash function tốt không xóa được collision; nó chỉ cố phân bố input đều hơn và khiến collision khó bị lợi dụng hơn.

Đừng nhầm với nghịch lý ngày sinh

Nguyên lý chuồng bồ câu trả lời câu hỏi:

Collision có bắt buộc tồn tại hay không?

Nghịch lý ngày sinh trả lời một câu khác:

Khi lấy mẫu ngẫu nhiên, từ quy mô nào xác suất collision bắt đầu đáng kể?

Với một không gian định danh có $M$ trạng thái, nguyên lý chuồng bồ câu chỉ bảo đảm collision sau khi tạo hơn $M$ định danh. Nhưng nếu định danh được chọn ngẫu nhiên, xác suất va chạm đã đáng chú ý khi số mẫu mới ở bậc $\sqrt{M}$.

Hai ý tưởng liên quan nhưng không giống nhau:

1Pigeonhole Principle  → sự tất yếu
2Birthday Paradox      → xác suất

Đừng trộn hai ông này vào một nồi rồi khuấy.

Cận dưới trong hệ thống máy tính

Phiên bản tổng quát đặc biệt hữu ích khi ta cần suy luận về tải tối thiểu mà một thành phần phải nhận.

1.000 request và 8 worker

Nếu 1.000 request được phân vào 8 worker thì tồn tại ít nhất một worker nhận

$$ \left\lceil \frac{1000}{8} \right\rceil = 125 $$

request trở lên.

Kết luận này đúng dù load balancer dùng round robin, random, least connections hay một thuật toán do AI ngoài hành tinh viết. Ta chưa biết worker nào bận nhất, nhưng biết rằng không thuật toán nào có thể làm cho cả tám worker đều nhận ít hơn 125 request.

Một tỷ key và 100 shard

Tương tự, nếu một tỷ key phải được lưu trên 100 shard thì ít nhất một shard chứa

$$ \left\lceil \frac{1.000.000.000}{100} \right\rceil = 10.000.000 $$

key.

Hệ thống thực tế còn có kích thước key khác nhau, replication, hot key và partition skew. Nguyên lý chuồng bồ câu không mô tả toàn bộ hệ thống; nó chỉ cung cấp một cận dưới sạch trước khi ta benchmark, dựng dashboard hay chạy một dòng code.

Không gian định danh hữu hạn

IPv4 có $2^{32}$ mẫu bit địa chỉ. Nếu số thiết bị cần một địa chỉ công khai duy nhất vượt quá không gian khả dụng, ta không thể tiếp tục gán một-một mãi mãi.

Khi “chim” ngày càng nhiều mà “chuồng” hữu hạn, ta buộc phải đổi luật chơi: chia sẻ địa chỉ, thêm tầng ánh xạ hoặc mở rộng không gian địa chỉ. NAT và IPv6 có nhiều động lực kỹ thuật, nhưng giới hạn không gian địa chỉ là một phần cốt lõi của câu chuyện.

Nói rộng hơn, nhiều kỹ thuật máy tính xuất hiện vì một lý do rất đời thường: hết chỗ.

Nguyên lý này không nói điều gì?

Nguyên lý chuồng bồ câu mạnh, nhưng đừng bắt nó làm việc ngoài hợp đồng. Nó thường chỉ cho ta biết một collision hoặc một nhóm đủ lớn tồn tại. Nó không nhất thiết chỉ ra:

• đối tượng nào bị trùng;
• có tổng cộng bao nhiêu collision;
• collision xảy ra với xác suất bao nhiêu;
• phân bố có đều hay không;
• bucket nào sẽ đông nhất trong thực tế.

Với 11 chim và 10 chuồng, cả hai phân bố sau đều hợp lệ:

12 1 1 1 1 1 1 1 1 1

111 0 0 0 0 0 0 0 0 0

Nguyên lý chỉ bảo đảm rằng ít nhất một chuồng có từ hai con. Muốn biết phân bố cụ thể, ta cần thêm dữ kiện hoặc một mô hình xác suất.

Bốn bước nhận diện một bài toán chuồng bồ câu

Khi gặp một bài toán về “hai thứ phải giống nhau”, “ít nhất một nhóm đủ lớn” hoặc “không thể tất cả đều khác nhau”, thử đi theo bốn bước:

1. Xác định các vật đang được phân loại. Đó là những “con chim”: người, số, điểm, request, file, key hoặc chuỗi.
2. Chọn thuộc tính phân loại. Mỗi giá trị có thể có của thuộc tính là một “chuồng”: tháng sinh, số dư, hash value, server, bucket hay vùng không gian.
3. Đếm số chim và số chuồng. Nếu số chim lớn hơn số chuồng, sự trùng lặp là bắt buộc. Nếu cần một nhóm lớn hơn, dùng $\lceil N/K \rceil$.
4. Dịch kết luận về ngôn ngữ ban đầu. “Hai số nằm cùng lớp dư” phải được đổi thành “hiệu của chúng chia hết cho modulo”; “hai điểm nằm cùng ô” phải được đổi thành một cận khoảng cách.

Bước thứ hai thường khó nhất. Chọn sai chuồng thì nguyên lý vẫn đúng, nhưng kết luận có thể chẳng giúp được gì.

Tìm một collision và chứng minh collision tồn tại là hai việc khác nhau

Ta có thể viết code để tìm những người sinh cùng tháng:

 1from collections import defaultdict
 2
 3people = [
 4    ("An", 1), ("Bình", 2), ("Cường", 3), ("Dũng", 4),
 5    ("Hà", 5), ("Hùng", 6), ("Lan", 7), ("Minh", 8),
 6    ("Nam", 9), ("Phúc", 10), ("Quân", 11), ("Trang", 12),
 7    ("Tùng", 2),
 8]
 9
10months = defaultdict(list)
11
12for name, month in people:
13    months[month].append(name)
14
15for month, names in months.items():
16    if len(names) >= 2:
17        print(month, names)

Chương trình phải duyệt dữ liệu để tìm ra tháng nào bị trùng. Nguyên lý chuồng bồ câu thì không cần chạy: chỉ từ “13 người, 12 tháng”, ta đã biết một collision chắc chắn tồn tại.

Đó là sự khác biệt giữa:

1tìm một lời giải

và:

1chứng minh lời giải phải tồn tại.

Tổng kết

Nguyên lý chuồng bồ câu có thể gói trong một câu:

Nếu số vật nhiều hơn số hộp thì ít nhất một hộp phải chứa nhiều hơn một vật.

Phiên bản tổng quát là:

$$ N \text{ vật},\ K \text{ hộp} \quad\Longrightarrow\quad \exists \text{ một hộp chứa ít nhất } \left\lceil \frac{N}{K} \right\rceil \text{ vật}. $$

Công thức nhỏ, nhưng ý tưởng phía sau rất lớn. Những đôi tất cùng màu, người sinh cùng tháng, các số có cùng số dư, hash collision, tải trên worker và dữ liệu trên shard đều có chung một bộ xương:

1Có nhiều thứ hơn số trạng thái dùng để phân biệt chúng.

Khi đó, sự trùng lặp không còn là tai nạn. Nó là định mệnh.

Có lẽ đó là điều thú vị nhất của nguyên lý chuồng bồ câu: nó không thực sự nói về chim. Nó nói về giới hạn của sự khác biệt.

Tham khảo

• MIT OpenCourseWare — Lecture 1: Pigeonhole Principle, Principles of Discrete Applied Mathematics, Spring 2024.
• Wolfram MathWorld — Dirichlet’s Box Principle.