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 phát biểu như sau: Có bao nhiêu cách chia ( n ) cái kẹo giống nhau cho ( k ) đứa trẻ khác nhau, sao cho mỗi đứa trẻ nhận được ít nhất một cái kẹo? Bài toán này tương đương với việc tìm số nghiệm nguyên dương của phương trình: [ x_1 + x_2 + dots + x_k = n ] với ( x_i geq 1 ) (mỗi ( x_i ) đại diện cho số kẹo của đứa trẻ thứ ( i )). 2. Công thức tổ hợp
Số cách chia ( n ) cái kẹo giống nhau cho ( k ) đứa trẻ (mỗi đứa ít nhất một cái) được tính bằng tổ hợp chập ( k-1 ) của ( n-1 ) (hay “bài toán chia kẹo Euler”): [ C_{n-1}^{k-1}]
Giải thích: – Ta có ( n ) cái kẹo xếp thành hàng, tạo ra ( n-1 ) khoảng trống giữa chúng. – Chọn ( k-1 ) khoảng trống để chia thành ( k ) phần (tương ứng với ( k ) đứa trẻ). – Mỗi cách chọn $k-1$ khoảng trống từ $n-1$ khoảng trống tương ứng với một cách chia kẹo. 3. Ví dụ minh họa Chia 5 cái kẹo cho 3 đứa trẻ, mỗi đứa ít nhất một cái.
– Áp dụng công thức: [ C_{5-1}^{3-1} = C_4^2 = 6 text{ cách} ] – Các cách chia: – (1, 1, 3) – (1, 2, 2) – (1, 3, 1) – (2, 1, 2) – (2, 2, 1) – (3, 1, 1)
4. Mở rộng bài toán cho trường hợp cho phép có đứa trẻ không nhận kẹo. Nếu mỗi đứa trẻ có thể nhận 0 cái kẹo, ta đặt ( y_i = x_i + 1 ), khi đó: [ y_1 + y_2 + dots + y_k = n + k ] Số cách chia là: [ C_{n + k – 1}^{k – 1} ]
Ví dụ: Chia 5 cái kẹo cho 3 đứa trẻ, có thể có đứa không nhận kẹo. [ C_{5 + 3 – 1}^{3 – 1} = C_7^2 = 21 text{ cách} ] 6. Áp dụng vào bài thi Tốt nghiệp THPT 2025.
Câu 5. Có bốn ngăn (trong một giá để sách) được đánh số thứ tự 1, 2, 3, 4 và tám quyển sách khác nhau. Bạn An xếp hết tám quyển sách nói trên vào bốn ngăn đó sao cho: Mỗi ngăn có ít nhất một quyển sách.
Các quyển sách được xếp thẳng đứng thành một hàng ngang với gáy sách quay ra ngoài ở mỗi ngăn. Hai cách xếp được gọi là giống nhau nếu thỏa mãn đồng thời hai điều kiện sau đây:
1. Số lượng quyển sách ở từng ngăn là như nhau trong cả hai cách xếp.
2. Thứ tự từ trái sang phải của các quyển sách trong từng ngăn là như nhau trong cả hai cách xếp.
Gọi $T$ là số cách xếp đôi một khác nhau của bạn An. Hỏi giá trị của $dfrac{T}{600}$ bằng bao nhiêu?
Gọi $a, b, c, d$ là số sách lần lượt được xếp vào ngăn $1, 2, 3, 4$. Ta có $a+b+c+d=8$.
Mỗi một cách xếp là một nghiệm nguyên dương của phương trình $x_1+x_2+x_3+x_4=8$. Theo Bài toán “chia kẹo Euler” (Euler’s Candy Division Problem) ta có số cách xếp là $C^{k-1}_{n-1}$, ở đây $k=4, n=8$.
Sau mỗi cách xếp ta hoán vị các quyển sách (các viên kẹo thì giống nhưng các quyển sách thì khác nhau). Vậy số tất cả cách xếp 8 quyển sách vào 4 ngăn là: $T=C^3_7times 8!$. $dfrac{T}{600}=$ Kết quả: 2352. 7. Kết luận Bài toán chia kẹo Euler là một dạng toán tổ hợp quan trọng, giúp rèn luyện tư duy đếm và áp dụng tổ hợp vào thực tế. Hiểu rõ công thức và các trường hợp mở rộng sẽ giúp giải quyết nhiều bài toán tương tự.
