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 = m x1+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 = m x1+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<nm < nm<n thì phương trình vô nghiệm.
- Nếu m≤nm le nm≤n thì bài toán lại trở thành dạng giống với bài toán cơ bản, lúc này số nghiệm của phương trình chính là số bộ giá trị (y1,y2,…,yn)(y_1, y_2, dots, y_n)(y1,y2,…,yn) thỏa mãn phương trình (1),(1),(1), đó là:
Cm−1n−1C^{n – 1}_{m – 1} Cm−1n−1
3. Phát triển bài toán tổng quát
Các bài toán có dạng như hai bài toán nói trên đều có thể phát biểu thành dạng tổng quát như sau: Đếm số nghiệm nguyên của phương trình x1+x2+⋯+xn=m;x_1 + x_2 + cdots + x_n = m;x1+x2+⋯+xn=m; với xi≥ai (∀i:1≤i≤n)x_i ge a_i (forall i: 1 le i le n)xi≥ai (∀i:1≤i≤n).
Lời giải của bài toán này tương tự với bài toán số 2, ta gọi yi=xi−ai;∀i:1≤i≤ny_i = x_i – a_i; forall i: 1 le i le nyi=xi−ai;∀i:1≤i≤n và s=∑i=1nais = sum_{i = 1}^n a_is=∑i=1nai. Phương trình đã cho sẽ trở thành:
y1+y2+⋯+yn=(x1−a1)+(x2−a2)+⋯+(xn−an)=m−s (2)y_1 + y_2 + cdots + y_n = (x_1 – a_1) + (x_2 – a_2) + cdots + (x_n – a_n) = m – s (2) y1+y2+⋯+yn=(x1−a1)+(x2−a2)+⋯+(xn−an)=m−s (2)
Giờ ta cần xét tới ba trường hợp kết quả:
- Nếu m<s,m < s,m<s, thì phương trình đã cho sẽ vô nghiệm.
- Nếu m=s,m = s,m=s, thì phương trình đã cho có duy nhất một nghiệm là xi=ai;∀i:1≤i≤nx_i = a_i; forall i: 1 le i le nxi=ai;∀i:1≤i≤n.
- Nếu m>s,m > s,m>s, thì ta cần đếm số bộ giá trị (y1,y2,…,yn)(y_1, y_2, dots, y_n)(y1,y2,…,yn) thỏa mãn phương trình (2),(2),(2), đó là:
Cm+n−s−1n−1C^{n – 1}_{m + n – s – 1} Cm+n−s−1n−1
Bây giờ chúng ta hãy cùng xét một vài bài toán ứng dụng của công thức chia kẹo Euler trong lập trình thi đấu, để hiểu rõ hơn về ứng dụng của công thức này trong các kì thi lập trình!
1. Đếm đường đi
Đề bài
Cho một lưới gồm các ô vuông. Các ô được đánh số từ 000 đến mmm theo chiều từ trái sang phải và từ 000 đến nnn theo chiều từ dưới lên trên. Giả sử ta đang ở ô (0,0);(0,0);(0,0); ta chỉ có thể di chuyển trên cạnh các ô vuông theo chiều từ trái sang phải hoặc từ dưới lên trên.
Yêu cầu: Hãy tính số đường đi khác nhau từ ô (0,0)(0,0)(0,0) đến ô (m,n)(m,n)(m,n) của lưới ô vuông?
Input:
- Một dòng duy nhất chứa hai số nguyên mmm và nnn.
Ràng buộc:
- 1≤m,n≤50001 le m, n le 50001≤m,n≤5000.
- m+n≤5000m + n le 5000m+n≤5000.
Output:
- In ra số dư của kết quả của bài toán sau khi chia cho 109+710^9 + 7109+7.
Sample Input:
2 3
Sample Output:
10
Ý tưởng
Nhận xét thấy, một đường đi thỏa mãn gồm m+nm + nm+n bước đi (mỗi bước đi là một cạnh ô vuông). Tại mỗi bước đi chỉ được chọn một trong hai giá trị đi lên (ta đặt là 111) hoặc đi sang phải (ta đặt là 000). Số bước đi lên đúng bằng nnn và số bước sang phải đúng bằng mmm. Bài toán lúc này dẫn đến việc tìm xem có bao nhiêu dãy nhị phân có độ dài m+nm + nm+n trong đó có đúng nnn thành phần có giá trị bằng 111.
Dựa trên bài toán chia kẹo Euler, kết quả cần tìm lúc này là (m+nm)m + n choose m(mm+n).
Ta có thể tính tổ hợp (nk)n choose k(kn) bằng quy hoạch động dựa trên tính chất sau của tổ hợp:
(nk)=(n−1k−1)+(n−1k){n choose k} = {n – 1 choose k – 1} + {n – 1 choose k} (kn)=(k−1n−1)+(kn−1)
Độ phức tạp: O(n2)O(n^2)O(n2). Các bạn cần kết hợp với việc tính toán modulo liên tục để tránh gây ra tràn số nếu như sử dụng ngôn ngữ C++.
Cài đặt
#include <bits/stdc++.h> using namespace std; const int MOD = 1e9 + 7; long long ncr[5005][5005], n, m; void pre_compute() { int k; for (int i = 0; i < 5001; i++) { ncr[i][0] = ncr[i][i] = 1; // Chỉ tính đến vị trí cột thứ i / 2 là đủ cho hàng i. k = i >> 1; for (int j = 1; j < k + 1; j++) ncr[i][j] = ncr[i][i – j] = (ncr[i – 1][j] + ncr[i – 1][j – 1]) % MOD; } } int main() { int m, n; cin >> m >> n; pre_compute(); cout << ncr[m + n][m]; return 0; }
2. Hợp nhất danh sách
Đề bài
Hôm nay Tí vừa học xong về danh sách liên kết trên trường. Cậu ấy đã được học về cách hợp nhất hai danh sách liên kết. Khi ta hợp nhất hai danh sách liên kết, thứ tự của các phần tử của mỗi danh sách không thay đổi. Ví dụ, nếu ta hợp nhất [1,2,3][1,2,3][1,2,3] và [4,5,6][4,5,6][4,5,6], ta sẽ thu được danh sách mới là [1,4,2,3,5,6][1,4,2,3,5,6][1,4,2,3,5,6], tuy nhiên [1,4,3,2,5,6][1,4,3,2,5,6][1,4,3,2,5,6] không hợp lệ vì 333 đứng sau 222.
Yêu cầu: Tí có hai danh sách liên kết gồm nnn và mmm phần tử, hãy giúp cậu ấy tính xem có bao nhiêu cách để hợp nhất cả hai danh sách. Dữ liệu đảm bảo rằng n+mn + mn+m phần tử trong hai danh sách đều phân biệt.
Input:
- Dòng đầu tiên chứa số nguyên ttt chỉ số lượng truy vấn.
- ttt dòng tiếp theo, mỗi dòng chứa một truy vấn gồm hai số nguyên là nnn và mmm.
Ràng buộc:
- 1≤t≤101 le t le 101≤t≤10.
- 1≤n,m≤1001 le n, m le 1001≤n,m≤100.
Output:
- In ra đáp án của bài toán sau khi chia cho 109+710^9 + 7109+7 và lấy số dư làm kết quả.
Sample Input:
1 2 2
Sample Output:
6
Giải thích:
Giả sử hai danh sách là [1,2][1,2][1,2] và [3,4][3,4][3,4], các cách khác nhau để hợp nhất các danh sách này là:
- [1,2,3,4][1,2,3,4][1,2,3,4].
- [1,3,2,4][1,3,2,4][1,3,2,4].
- [3,4,1,2][3,4,1,2][3,4,1,2].
- [3,1,4,2][3,1,4,2][3,1,4,2].
- [1,3,4,2][1,3,4,2][1,3,4,2].
- [3,1,2,4][3,1,2,4][3,1,2,4].
Ý tưởng
Bạn phải hợp nhất hai danh sách gồm mmm và nnn phần tử lại với nhau. Điều này tương đương với việc sắp xếp mmm vật thuộc cùng một loại với nnn vật cùng thuộc loại khác trên cùng một hàng. Đây chính là bài toán chia kẹo Euler!
Tổng số cách để hợp nhất hai danh sách sẽ là (n+mn)n + m choose n(nn+m). Lí do là vì ta cần chọn ra nnn vị trí trong m+nm + nm+n vị trí để đặt nnn vật thuộc loại thứ 222 vào. Kết quả không có gì thay đổi nếu như bạn chọn nó bằng (n+mm)n + m choose m(mn+m).
Ta có thể tính tổ hợp (nk)n choose k(kn) bằng quy hoạch động dựa trên tính chất sau (chính là tam giác Pascal, nếu các bạn chưa nhớ về công thức này thì hãy tìm đọc lại trên internet):
(nk)=(n−1k−1)+(n−1k){n choose k} = {n – 1 choose k – 1} + {n – 1 choose k} (kn)=(k−1n−1)+(kn−1)
Độ phức tạp: O(n2)O(n^2)O(n2). Các bạn nên khởi tạo trước mảng hai chiều lưu tam giác Pascal rồi đưa ra kết quả của mỗi test case trong O(1)O(1)O(1).
Cài đặt
#include <bits/stdc++.h> #define int long long using namespace std; const int MOD = 1e9 + 7; void pre_compute(vector < vector < int > > &ncr, int max_size) { ncr = vector < vector < int > >(max_size + 1, vector < int >(max_size + 1)); for (int i = 0; i <= max_size; ++i) { ncr[i][0] = ncr[i][i] = 1; for (int j = 1; j < i; ++j) ncr[i][j] = (ncr[i – 1][j] + ncr[i – 1][j – 1]) % MOD; } } main() { vector < vector < int > > ncr; pre_compute(ncr, 200); int t; cin >> t; while (t-) { int n, m; cin >> n >> m; cout << c[n + m][m] << endl; } return 0; }
- https://www.dropbox.com/s/q69pd0ctlzhjaim/Bài toán chia kẹo của Euler.pdf?dl=0
- https://vted.vn/tin-tuc/bai-toan-chia-keo-euler-va-ung-dung-4529.html
- https://math.stackexchange.com/questions/1586500/share-m-candy-bars-for-n-people
©️ Tác giả: Vũ Quế Lâm từ Viblo
