Tổ hợp và Toán rời rạc

Nguyên lý Dirichlet

Nếu số đồ vật đặt vào các hộp nhiều hơn số hộp, thì phải có hộp chứa nhiều hơn một đồ vật.

Trực giácVì sao phải có hai con bồ câu chung một tổ?

Giả sử bạn có $10$ con bồ câu nhưng chỉ có $9$ cái tổ, và mỗi con bồ câu đều phải bay vào một tổ nào đó. Dù xếp khéo léo thế nào, cũng sẽ có ít nhất một tổ chứa từ hai con bồ câu trở lên — đơn giản là không đủ tổ để mỗi con có riêng một tổ. Sự thật nghe có vẻ hiển nhiên này được gọi là nguyên lý Dirichlet (nguyên lý chuồng bồ câu), và dù đơn giản, nó chứng minh được những kết quả sâu sắc đến bất ngờ trong lý thuyết số, hình học và khoa học máy tính.

Đồ thị

K_{3,3}

nhỏ này là mô hình sơ đồ gồm ba vật và ba hộp: các cạnh biểu thị những cách phân vào hộp có thể có, không phải một cách phân cụ thể. Trong ví dụ

10

con bồ câu,

9

cái tổ ở phần văn bản, thêm một con nữa buộc có tổ nhận từ hai con trở lên.

Phổ thôngPhát biểu chính xác nguyên lý

Định nghĩa: Nguyên lý Dirichlet

Nếu $n$ đồ vật được đặt vào $k$ cái hộp và $n > k$ , thì ít nhất một hộp chứa ít nhất $2$ đồ vật. Tổng quát hơn, nếu $n$ đồ vật được đặt vào $k$ cái hộp, thì có một hộp chứa ít nhất $\lceil n/k\rceil$ đồ vật.

n>k\ \Longrightarrow\ \exists\text{ box with}\ge2\text{ objects}

Số $\lceil n/k\rceil$ (" $n/k$ làm tròn lên") là số nguyên nhỏ nhất không nhỏ hơn $n/k$ ; đó là số lượng tối thiểu được đảm bảo trong hộp đầy nhất khi $n$ đồ vật được chia đều nhất có thể vào $k$ cái hộp. Ví dụ, chia $n=10$ đồ vật vào $k=3$ hộp đều nhất có thể cho số lượng $4,3,3$ , và quả thực $\lceil 10/3\rceil=4$ .

\left\lceil\frac{n}{k}\right\rceil=\left\lfloor\frac{n-1}{k}\right\rfloor+1

Bao nhiêu đồ vật, bao nhiêu hộp, điều gì được đảm bảo
Đồ vật $n$ / hộp $k$	Số tối thiểu được đảm bảo trong hộp đầy nhất
$n=10,\ k=9$	$\lceil 10/9\rceil=2$
$n=13,\ k=12$	$\lceil 13/12\rceil=2$
$n=100,\ k=9$	$\lceil 100/9\rceil=12$
$n=k+1,\ k$ bất kỳ	$\lceil (k+1)/k\rceil=2$

Đại họcHai định lý: nguyên lý cơ bản và nguyên lý tổng quát

Định lý: Nguyên lý Dirichlet cơ bản

Nếu $n$ đồ vật được phân phối vào $k$ cái hộp với $n>k$ , thì có ít nhất một hộp chứa ít nhất $2$ đồ vật.

Vì sao đúng?

Đây thực chất là một phát biểu về đếm, được chứng minh bằng cách giả sử điều ngược lại và dẫn tới mâu thuẫn: nếu mỗi hộp chứa nhiều nhất $1$ đồ vật, thì tổng số đồ vật mà các hộp chứa được không thể vượt quá $k$ .

Chứng minh

Giả sử, để phản chứng, kết luận không đúng: mỗi hộp trong $k$ cái hộp chứa nhiều nhất $1$ đồ vật.

Khi đó tổng số đồ vật được phân phối nhiều nhất là $k\times1=k$ .

Nhưng ta đã phân phối $n$ đồ vật, và theo giả thiết $n>k$ , nên tổng số đồ vật được phân phối là $n>k$ .

Hai cách đếm cùng một tập đồ vật này mâu thuẫn nhau ( $n>k$ nhưng tổng lại $\le k$ ), vậy giả thiết phản chứng sai: phải có một hộp chứa ít nhất $2$ đồ vật.

Định lý: Nguyên lý Dirichlet tổng quát

Nếu $n$ đồ vật được phân phối vào $k$ cái hộp, thì có một hộp chứa ít nhất $\lceil n/k\rceil$ đồ vật.

Vì sao đúng?

Nguyên lý cơ bản chỉ đảm bảo có $2$ đồ vật ở đâu đó; phiên bản tổng quát làm sắc nét điều này thành mức tối thiểu chính xác bị ép buộc khi chia đều $n$ đồ vật cho $k$ cái hộp, dùng cùng ý tưởng phản chứng nhưng so sánh với $\lceil n/k\rceil-1$ thay vì $1$ .

Chứng minh

Giả sử, để phản chứng, mọi hộp đều chứa nhiều nhất $\lceil n/k\rceil-1$ đồ vật.

Khi đó tổng số đồ vật được phân phối nhiều nhất là $k\left(\lceil n/k\rceil-1\right)$ .

Vì $\lceil n/k\rceil$ là số nguyên nhỏ nhất không nhỏ hơn $n/k$ , ta có $\lceil n/k\rceil-1<n/k$ , nên $k\left(\lceil n/k\rceil-1\right)<k\cdot\frac{n}{k}=n$ .

Vậy tổng số được phân phối nhỏ hơn hẳn $n$ , mâu thuẫn với việc toàn bộ $n$ đồ vật đã được phân phối. Do đó có một hộp chứa ít nhất $\lceil n/k\rceil$ đồ vật.

Đại họcỨng dụng thực tiễn và ví dụ minh họa

Dù đơn giản, nguyên lý Dirichlet là một công cụ tiêu chuẩn trong khoa học máy tính (chứng minh rằng một bảng băm có nhiều khóa hơn số ô phải xảy ra va chạm), trong lý thuyết số (chứng minh rằng một bội số nào đó của một số nguyên cho trước có một mẫu chữ số cụ thể), và trong các bài toán tổ hợp đời thường về lập lịch, sắp xếp và mạng xã hội.

Ví dụ: Tất trong ngăn kéo

Một ngăn kéo chứa tất có $4$ màu, mỗi màu có nhiều chiếc nhưng bị trộn lẫn trong bóng tối. Số tất ít nhất bạn phải lấy ra để chắc chắn có một đôi cùng màu là bao nhiêu?

Lời giải

Coi $4$ màu như $k=4$ cái hộp, và mỗi chiếc tất bạn lấy ra là một đồ vật được thả vào hộp ứng với màu của nó. "Một đôi cùng màu" nghĩa là có hộp nhận ít nhất $2$ đồ vật.

Theo nguyên lý Dirichlet cơ bản, một khi bạn lấy $n$ chiếc tất với $n>k=4$ , tức $n\ge5$ , sẽ có một hộp màu chứa ít nhất $2$ chiếc tất — một đôi cùng màu được đảm bảo.

Liệu $5$ có thực sự là số nhỏ nhất như vậy? Với chỉ $4$ chiếc tất, có thể (dù không may) lấy đúng mỗi màu một chiếc trong $4$ màu, chưa có đôi nào. Vậy $4$ chiếc tất không đảm bảo có đôi, nhưng $5$ chiếc thì có.

Đáp số là $5$ chiếc tất.

Ví dụ: Hai người trong bữa tiệc có cùng số bạn

Trong một bữa tiệc có $n\ge2$ người, "tình bạn" là quan hệ hai chiều và không ai là bạn của chính mình. Hãy chỉ ra rằng phải có hai người trong bữa tiệc có đúng cùng số bạn có mặt.

Lời giải

Số bạn của mỗi người trong bữa tiệc là một số nguyên từ $0$ đến $n-1$ (không thể có nhiều bạn hơn $n-1$ người còn lại có mặt), cho $n$ giá trị có thể và $n$ người — nếu áp dụng nguyên lý Dirichlet trực tiếp lên số bạn thì chỉ có $n$ hộp cho $n$ người, chưa ép được va chạm.

Quan sát thêm mấu chốt là các giá trị $0$ và $n-1$ không thể cùng xảy ra: nếu có người có $0$ bạn, thì không ai có thể có $n-1$ bạn (nghĩa là làm bạn với tất cả mọi người, kể cả người đó), và ngược lại. Vậy thực ra chỉ có $n-1$ giá trị số bạn khác nhau có thể xảy ra: hoặc là $\{0,1,\dots,n-2\}$ , hoặc là $\{1,2,\dots,n-1\}$ .

Bây giờ áp dụng nguyên lý Dirichlet cơ bản với $n$ người (đồ vật) và nhiều nhất $n-1$ giá trị số bạn có thể (hộp). Vì $n>n-1$ , có một hộp số bạn nhận ít nhất $2$ người.

Vậy có ít nhất hai người trong bữa tiệc có đúng cùng số bạn có mặt.

Nếu $13$ con bồ câu bay vào $12$ cái tổ, nguyên lý Dirichlet cơ bản đảm bảo điều gì?

Dùng nguyên lý Dirichlet tổng quát, số đồ vật tối thiểu được đảm bảo trong hộp đầy nhất khi $n=100$ đồ vật được đặt vào $k=9$ hộp là bao nhiêu?

Tình huống đời thường nào sau đây là một ứng dụng trực tiếp của nguyên lý Dirichlet?

Trong ví dụ bữa tiệc với tình bạn hai chiều, vì sao số bạn $0$ và $n-1$ không thể cùng xảy ra trong số $n$ khách?