Bài toán chia kẹo Euler là một bài toán tổ hợp xuất hiện từ thời xa xưa, đây là một bài toán rất hay và có nhiều ứng dụng trong Toán học. Xuất phát từ một vấn đề rất đơn giản, nhà bác học Leohard Euler đã phát biểu nó thành một bài toán như sau:
"Có mmm chiếc kẹo giống nhau, cần chia chúng cho nnn em bé. Hỏi có bao nhiêu cách chia kẹo như vậy?"
Bài toán tưởng chừng như đơn giản, nhưng nó lại gây khó khăn cho không ít học sinh. Từ bài toán này, người ta đã phát triển ra cách giải cho vô số bài toán đếm khác nhau. Trong bài viết này, tôi sẽ giới thiệu tới các bạn phương pháp giải bài toán chia kẹo Euler và một số ứng dụng từ cơ bản tới nâng cao của nó. Tất nhiên, nội dung các bài toán sẽ liên quan nhiều tới lập trình, do đó tôi sẽ bỏ qua những bài toán quá khó [mà chỉ dành cho học sinh chuyên Toán].
1. Phương pháp giải bài toán cơ bản
Nếu gọi số kẹo mà mỗi em bé nhận được lần lượt là x1,x2,…,xn [0≤xi≤m;∀i:1≤i≤n]x_1, x_2, \dots, x_n \ [0 \le x_i \le m; \forall i: 1 \le i \le n]x1,x2,…,xn [0≤xi≤m;∀i:1≤i≤n]. Bài toán khi đó sẽ trở thành: Đếm số nghiệm nguyên không âm của phương trình:
x1+x2+⋯+xn=mx_1 + x_2 + \cdots + x_n = mx1+x2+⋯+xn=m
Sử dụng kĩ thuật song ánh, coi rằng giữa mỗi em bé có một số 000 và số kẹo của em bé thứ iii nhận được sẽ biểu diễn bằng một dãy gồm xix_ixi số 1,1,1, thì bài toán trở thành đếm số cấu hình có dạng:
Với mmm số 111 và n−1n - 1n−1 số 000
Như vậy, thực tế ta đang đếm số cách đặt n−1n - 1n−1 số 000 vào một dãy gồm m+n−1m + n - 1m+n−1 vị trí, còn lại sẽ là các số 111. Theo quy tắc tổ hợp không lặp, số nghiệm của bài toán sẽ là:
Cm+n−1n−1C^{n - 1}_{m + n - 1}Cm+n−1n−1
Tuy nhiên, khi lập trình các bạn sẽ cần lưu ý cả tới giới hạn dữ liệu của bài toán. Nếu như bài toán yêu cầu đưa ra kết quả là phần dư sau khi chia cho một giá trị nào đó thì cần sử dụng các phương pháp phù hợp như Nghịch đảo modulo, Thuật toán bình phương và nhân hay Phép nhân Ấn Độ tương ứng. Lập trình ở phần này không khó nên tôi sẽ không viết lại code nữa!
2. Nếu các em bé đều phải nhận được ít nhất 1 chiếc kẹo?
Bài toán có thể lắt léo hơn một chút, nếu như đề bài yêu cầu rằng khi chia kẹo, mỗi em bé đều phải được nhận ít nhất 111 chiếc kẹo. Khi đó, bài toán sẽ trở thành: Đếm số nghiệm nguyên dương của phương trình:
x1+x2+⋯+xn=mx_1 + x_2 + \cdots + x_n = mx1+x2+⋯+xn=m
Đối với bài toán này, ta giải như sau: Đặt yi=xi−1;∀i:1≤i≤ny_i = x_i - 1; \forall i: 1 \le i \le nyi=xi−1;∀i:1≤i≤n. Khi đó ta có:
y1+y2+⋯+yn=x1+x2+⋯+xn−n=m−n [1]y_1 + y_2 + \cdots + y_n = x_1 + x_2 + \cdots + x_n - n = m - n \ [1]y1+y2+⋯+yn=x1+x2+⋯+xn−n=m−n [1]
Lúc này phương trình xảy ra hai trường hợp kết quả:
- Nếu m