Bài toán chia kẹo Euler

Tài liệu học tập: Bài toán chia kẹo Euler - Số cách chia kẹo cho trẻ em

1. Giới thiệu bài toán

Bài toán chia kẹo Euler là một bài toán tổ hợp kinh điển, có nhiều ứng dụng trong thực tế và thường xuất hiện trong các kỳ thi học sinh giỏi Toán. Bài toán có thể được phát biểu một cách tổng quát như sau:

Bài toán: Có n cái kẹo giống nhau, cần chia cho k em bé. Hỏi có bao nhiêu cách chia?

Đây là dạng bài toán cơ bản. Tuy nhiên, bài toán sẽ trở nên thú vị và đa dạng hơn khi có thêm các điều kiện ràng buộc khác nhau, ví dụ như mỗi em bé phải nhận được ít nhất một cái kẹo, hoặc số kẹo mỗi em bé nhận được phải nằm trong một khoảng nhất định.

2. Các dạng bài toán và phương pháp giải

2.1. Dạng 1: Chia kẹo không có điều kiện ràng buộc

Bài toán: Có n cái kẹo giống nhau, chia cho k em bé. Mỗi em bé có thể nhận 0, 1, 2, ... cái kẹo. Hỏi có bao nhiêu cách chia?

Phương pháp giải:

Sử dụng phương pháp "vách ngăn". Ta tưởng tượng n cái kẹo được xếp thành một hàng ngang. Để chia n cái kẹo này cho k em bé, ta cần đặt k - 1 vách ngăn vào giữa các kẹo.

Ví dụ, nếu có 5 cái kẹo và 3 em bé, ta có thể biểu diễn một cách chia như sau:

**|*|**

Trong ví dụ này, em bé thứ nhất nhận 2 cái kẹo, em bé thứ hai nhận 1 cái kẹo, và em bé thứ ba nhận 2 cái kẹo.

Tổng cộng, ta có n cái kẹo và k - 1 vách ngăn. Số cách chia kẹo tương ứng với số cách chọn vị trí cho k - 1 vách ngăn trong tổng số n + k - 1 vị trí.

Vậy, số cách chia kẹo là:

$C_{n+k-1}^{k-1} = C_{n+k-1}^{n} = \binom{n+k-1}{k-1} = \binom{n+k-1}{n}$

Ví dụ:

Có 7 cái kẹo, chia cho 3 em bé. Hỏi có bao nhiêu cách chia?

Áp dụng công thức, ta có:

Số cách chia = $C_{7+3-1}^{3-1} = C_9^2 = \frac{9!}{2!7!} = \frac{9 \times 8}{2} = 36$ cách.

2.2. Dạng 2: Chia kẹo mỗi em bé nhận ít nhất 1 cái

Bài toán: Có n cái kẹo giống nhau, chia cho k em bé. Mỗi em bé phải nhận ít nhất 1 cái kẹo. Hỏi có bao nhiêu cách chia? (Điều kiện: n ≥ k)

Phương pháp giải:

Đầu tiên, ta chia cho mỗi em bé 1 cái kẹo. Như vậy, ta còn lại n - k cái kẹo. Bây giờ, ta chia n - k cái kẹo còn lại cho k em bé một cách tùy ý (mỗi em bé có thể nhận 0, 1, 2,... cái kẹo).

Áp dụng công thức ở dạng 1, số cách chia n - k cái kẹo cho k em bé là:

$C_{n-k+k-1}^{k-1} = C_{n-1}^{k-1} = \binom{n-1}{k-1}$

Ví dụ:

Có 10 cái kẹo, chia cho 4 em bé, mỗi em bé phải có ít nhất 1 cái kẹo. Hỏi có bao nhiêu cách chia?

Ta chia trước cho mỗi em bé 1 cái kẹo. Còn lại 10 - 4 = 6 cái kẹo.

Số cách chia 6 cái kẹo cho 4 em bé là:

$C_{6+4-1}^{4-1} = C_9^3 = \frac{9!}{3!6!} = \frac{9 \times 8 \times 7}{3 \times 2 \times 1} = 84$ cách.

2.3. Dạng 3: Chia kẹo mỗi em bé nhận số kẹo trong một khoảng cho trước

Bài toán: Có n cái kẹo giống nhau, chia cho k em bé. Em bé thứ i phải nhận số kẹo nằm trong đoạn $[a_i, b_i]$ (a_i, b_i là các số nguyên không âm). Hỏi có bao nhiêu cách chia?

Phương pháp giải:

Đây là dạng bài toán phức tạp hơn và thường đòi hỏi kỹ năng biến đổi và áp dụng nguyên lý bù trừ.

Bước 1: Đặt ẩn

Gọi x_i là số kẹo em bé thứ i nhận được. Ta có:

$a_i \le x_i \le b_i$

Và tổng số kẹo phải bằng n:

$x_1 + x_2 + ... + x_k = n$

Bước 2: Đổi biến

Đặt $y_i = x_i - a_i$. Khi đó, $0 \le y_i \le b_i - a_i$.

Phương trình trở thành:

$y_1 + a_1 + y_2 + a_2 + ... + y_k + a_k = n$

$y_1 + y_2 + ... + y_k = n - (a_1 + a_2 + ... + a_k)$

Đặt $m = n - (a_1 + a_2 + ... + a_k)$. Ta có:

$y_1 + y_2 + ... + y_k = m$, với $0 \le y_i \le b_i - a_i$

Bước 3: Giải bài toán không ràng buộc

Gọi S là tập hợp các nghiệm nguyên không âm của phương trình $y_1 + y_2 + ... + y_k = m$.

Số nghiệm của phương trình này là:

$|S| = C_{m+k-1}^{k-1}$

Bước 4: Áp dụng nguyên lý bù trừ

Ta cần loại bỏ các nghiệm không thỏa mãn điều kiện $y_i \le b_i - a_i$.

Đặt $A_i$ là tập hợp các nghiệm của phương trình $y_1 + y_2 + ... + y_k = m$ mà $y_i > b_i - a_i$.

Số nghiệm cần tìm là:

$|S \setminus (A_1 \cup A_2 \cup ... \cup A_k)| = |S| - \sum |A_i| + \sum |A_i \cap A_j| - \sum |A_i \cap A_j \cap A_l| + ...$

Để tính $|A_i|$, ta đặt $z_i = y_i - (b_i - a_i) - 1$. Khi đó, $z_i \ge 0$.

Phương trình trở thành:

$z_i + (b_i - a_i) + 1 + \sum_{j \ne i} y_j = m$

$z_i + \sum_{j \ne i} y_j = m - (b_i - a_i) - 1$

Số nghiệm của phương trình này là:

$|A_i| = C_{m - (b_i - a_i) - 1 + k - 1}^{k-1} = C_{m - (b_i - a_i) + k - 2}^{k-1}$

Tương tự, ta tính các giao của các tập $A_i$ và áp dụng công thức bù trừ để tìm kết quả cuối cùng.

Ví dụ:

Có 10 cái kẹo, chia cho 3 em bé. Em bé thứ nhất nhận ít nhất 2 cái và không quá 4 cái, em bé thứ hai nhận ít nhất 1 cái và không quá 3 cái, em bé thứ ba nhận ít nhất 3 cái và không quá 5 cái. Hỏi có bao nhiêu cách chia?

Giải:

Đặt x_i là số kẹo em bé thứ i nhận được. Ta có:

$2 \le x_1 \le 4$ $1 \le x_2 \le 3$ $3 \le x_3 \le 5$ $x_1 + x_2 + x_3 = 10$

Đặt $y_1 = x_1 - 2, y_2 = x_2 - 1, y_3 = x_3 - 3$. Khi đó:

$0 \le y_1 \le 2$ $0 \le y_2 \le 2$ $0 \le y_3 \le 2$ $y_1 + y_2 + y_3 = 10 - (2 + 1 + 3) = 4$

Gọi S là tập hợp các nghiệm nguyên không âm của phương trình $y_1 + y_2 + y_3 = 4$.

$|S| = C_{4+3-1}^{3-1} = C_6^2 = 15$

Gọi $A_i$ là tập hợp các nghiệm của phương trình $y_1 + y_2 + y_3 = 4$ mà $y_i > 2$.

• Tính $|A_1|$: Đặt $z_1 = y_1 - 3$. Ta có $z_1 + y_2 + y_3 = 4 - 3 = 1$. $|A_1| = C_{1+3-1}^{3-1} = C_3^2 = 3$
• Tương tự, $|A_2| = |A_3| = 3$.
• Tính $|A_1 \cap A_2|$: Đặt $z_1 = y_1 - 3, z_2 = y_2 - 3$. Ta có $z_1 + z_2 + y_3 = 4 - 3 - 3 = -2$. Phương trình này vô nghiệm, do đó $|A_1 \cap A_2| = 0$.
• Tương tự, $|A_1 \cap A_3| = |A_2 \cap A_3| = 0$.
• $|A_1 \cap A_2 \cap A_3| = 0$

Vậy số cách chia kẹo là:

$|S \setminus (A_1 \cup A_2 \cup A_3)| = |S| - (|A_1| + |A_2| + |A_3|) = 15 - (3 + 3 + 3) = 6$ cách.

3. Bài tập tự luyện

1. Có 12 quả táo giống nhau, chia cho 4 người. Hỏi có bao nhiêu cách chia nếu: a) Không có điều kiện gì? b) Mỗi người có ít nhất 1 quả?
2. Có 20 viên bi giống nhau, chia cho 5 hộp. Hỏi có bao nhiêu cách chia nếu: a) Mỗi hộp có thể có bao nhiêu viên cũng được? b) Mỗi hộp có ít nhất 2 viên?
3. Có 10 cái bút, chia cho 3 học sinh. Học sinh thứ nhất nhận ít nhất 1 bút và không quá 4 bút, học sinh thứ hai nhận ít nhất 2 bút và không quá 3 bút, học sinh thứ ba nhận ít nhất 3 bút. Hỏi có bao nhiêu cách chia?
4. Giải lại các bài toán trên bằng ngôn ngữ lập trình (ví dụ Python) để kiểm tra kết quả.

4. Kết luận

Bài toán chia kẹo Euler là một ví dụ điển hình cho thấy sức mạnh của phương pháp tổ hợp trong việc giải quyết các bài toán thực tế. Việc nắm vững các dạng bài toán và phương pháp giải sẽ giúp các bạn học sinh tự tin hơn khi đối mặt với các bài toán tương tự trong các kỳ thi. Chúc các bạn học tốt!