Định lýĐã chứng minh

Nguyên lý Dirichlet cơ bản

Phát biểu

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$ .

Phác thảo 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.

Chủ đề chứa định lý này

Nguyên lý Dirichlet

Chứng minh từng bước

Chưa có chứng minh từng bước cho định lý này.