TÓM TẮT BÀI TOÁN CHIA KẸO EULER (PHƯƠNG PHÁP CHÈN VÁCH)
- Trường hợp 1 (Ai cũng có phần): Chia \(n\) vật giống nhau cho \(k\) đối tượng phân biệt sao cho mỗi đối tượng nhận ít nhất 1 vật. Số cách chia là số nghiệm nguyên dương của phương trình \(x_1 + x_2 + \dots + x_k = n\), tính bằng công thức \(C_{n-1}^{k-1}\) (với \(n \ge k \ge 1\)).
- Trường hợp 2 (Có thể nhận 0 vật): Chia \(n\) vật giống nhau cho \(k\) đối tượng phân biệt. Số cách chia là số nghiệm nguyên không âm của phương trình \(x_1 + x_2 + \dots + x_k = n\), tính bằng công thức \(C_{n+k-1}^{k-1}\).
- Kỹ thuật đổi biến: Khi có định mức tối thiểu \(x_i \ge a_i\), cấp trước cho người thứ \(i\) số lượng \(a_i\) vật, đưa bài toán về đếm số nghiệm không âm \(y_i = x_i - a_i \ge 0\).
A. LÝ THUYẾT VÀ PHƯƠNG PHÁP GIẢI
1. Nhận dạng bài toán chia kẹo
Chia hết \(n\) vật giống nhau cho \(k\) người phân biệt. Gọi \(x_i\) là số vật người thứ \(i\) nhận được. Mỗi cách chia ứng với đúng một bộ số theo thứ tự \((x_1, x_2, \dots, x_k)\) thỏa mãn \(x_1 + x_2 + \dots + x_k = n\).
– Ai cũng có phần (nghiệm nguyên dương): Xếp \(n\) viên kẹo thành hàng. Chọn \(k - 1\) trong \(n - 1\) khe giữa hai viên để đặt vách. Số cách là \(C_{n-1}^{k-1}\) (khi \(n \ge k \ge 1\)).
– Có thể nhận 0 viên (nghiệm nguyên không âm): Xếp chung \(n\) viên kẹo và \(k - 1\) vách. Chọn \(k - 1\) vị trí đặt vách trong \(n + k - 1\) vị trí, được \(C_{n+k-1}^{k-1}\) cách.
2. Đưa điều kiện về tổng các biến không âm
- Có định mức tối thiểu: Cấp trước \(a_i\) vật cho người thứ \(i\), rồi chia phần còn lại. Đặt \(y_i = x_i - a_i \ge 0\). Nếu phần còn lại âm thì có 0 cách.
- Tổng không vượt quá \(n\): Thêm biến không âm \(t = n - (x_1 + x_2 + \dots + x_k)\) biểu diễn số vật còn dư.
- Hệ số, chẵn lẻ hoặc so sánh hai biến: Cố định biến có hệ số hoặc liệt kê các giá trị đúng chẵn lẻ rồi đếm phần còn lại. Nếu \(x_1 \ge x_2 + c\), có thể đặt \(x_1 = x_2 + c + t\) với \(t \ge 0\).
Ví dụ nhanh: Chia 9 viên cho 3 bạn với định mức tối thiểu lần lượt là 1, 2 và 3 viên. Sau khi cấp trước 6 viên, chia tự do 3 viên còn lại cho 3 bạn, số cách là \(C_{3+3-1}^{3-1} = C_5^2 = 10\) cách.
3. Xử lý chặn trên và tính xác suất
Với điều kiện \(x_i \le b_i\), trường hợp vi phạm là \(x_i \ge b_i + 1\). Tính số cách vi phạm bằng cách cấp trước \(b_i + 1\) vật cho người thứ \(i\), đồng thời giữ định mức dưới của các người còn lại.
- Một chặn trên: Lấy tổng số cách chia trừ số cách vi phạm.
- Nhiều chặn trên: Trừ số cách vi phạm từng chặn, cộng lại số cách vi phạm đồng thời từng cặp, tiếp tục nguyên lý bù trừ.
- Xác suất: Chia số bộ thuận lợi cho tổng số bộ thỏa mãn điều kiện ban đầu.
B. VÍ DỤ MINH HỌA
Ví dụ 1. Tìm tổng số bộ nghiệm nguyên dương \((x_1, x_2, x_3, x_4, x_5)\) thỏa mãn phương trình:
\[x_1 + x_2 + x_3 + x_4 + x_5 = 20.\]Số bộ nghiệm nguyên dương là \(C_{20-1}^{5-1} = C_{19}^4 = 3876\).
KẾT QUẢ: 3876
Ví dụ 2. Một người mẹ có 15 chiếc kẹo sô-cô-la giống hệt nhau đem chia ngẫu nhiên cho 4 đứa con của mình (mỗi đứa con có thể nhận được từ 0 đến 15 chiếc kẹo). Các cách chia theo số lượng đều đồng khả năng. Gọi \(P\) là xác suất để sau khi chia, cả 4 đứa con đều nhận được ít nhất một chiếc kẹo. Tính \(T = 20400 \cdot P\).
Tổng số cách chia 15 chiếc kẹo cho 4 đứa con (số nghiệm nguyên không âm của \(x_1+x_2+x_3+x_4=15\)) là \(n(\Omega) = C_{15+4-1}^{4-1} = C_{18}^3 = 816\).
Số cách chia sao cho cả 4 đứa con đều có ít nhất 1 chiếc kẹo (số nghiệm nguyên dương của \(x_1+x_2+x_3+x_4=15\)) là \(n(A) = C_{15-1}^{4-1} = C_{14}^3 = 364\).
Xác suất \(P = \frac{364}{816} = \frac{91}{204}\).
Do đó \(T = 20400 \cdot \frac{91}{204} = 9100\).
KẾT QUẢ: 9100
Ví dụ 3. Tìm số bộ nghiệm nguyên không âm \((x_1, x_2, x_3, x_4, x_5)\) của phương trình:
\[x_1 + x_2 + x_3 + x_4 + x_5 = 12.\]Số bộ nghiệm nguyên không âm của phương trình là \(C_{12+5-1}^{5-1} = C_{16}^4 = 1820\).
KẾT QUẢ: 1820
Ví dụ 4. Giáo viên chủ nhiệm có 12 quyển vở giống nhau đem chia ngẫu nhiên cho 4 học sinh tiêu biểu gồm An, Bình, Cường và Dũng (mỗi bạn có thể nhận từ 0 đến 12 quyển vở). Các cách chia theo số lượng đều đồng khả năng. Gọi \(P\) là xác suất để học sinh An nhận được ít nhất 3 quyển vở. Tính \(T = 9100 \cdot P\).
Tổng số cách chia 12 quyển vở cho 4 học sinh là \(n(\Omega) = C_{12+4-1}^{4-1} = C_{15}^3 = 455\).
Để An nhận ít nhất 3 quyển vở, ta cấp trước 3 quyển cho An, còn lại 9 quyển chia tự do cho 4 bạn. Số cách chia thuận lợi là \(n(A) = C_{9+4-1}^{4-1} = C_{12}^3 = 220\).
Xác suất \(P = \frac{220}{455} = \frac{44}{91}\).
Do đó \(T = 9100 \cdot \frac{44}{91} = 4400\).
KẾT QUẢ: 4400
Ví dụ 5. Tìm tổng số bộ nghiệm nguyên \((x_1, x_2, x_3, x_4, x_5)\) của phương trình:
\[x_1 + x_2 + x_3 + x_4 + x_5 = 26\]thỏa mãn các điều kiện chặn dưới bậc thang: \(x_1 \ge 1, x_2 \ge 2, x_3 \ge 3, x_4 \ge 4, x_5 \ge 5\).
Đặt \(y_1 = x_1 - 1 \ge 0\), \(y_2 = x_2 - 2 \ge 0\), \(y_3 = x_3 - 3 \ge 0\), \(y_4 = x_4 - 4 \ge 0\), \(y_5 = x_5 - 5 \ge 0\).
Phương trình trở thành:
\[y_1 + y_2 + y_3 + y_4 + y_5 = 26 - (1 + 2 + 3 + 4 + 5) = 11.\]Số bộ nghiệm nguyên không âm \((y_1, y_2, y_3, y_4, y_5)\) là \(C_{11+5-1}^{5-1} = C_{15}^4 = 1365\).
KẾT QUẢ: 1365