Bài toán chia kẹo EulerI. Bài toán mở đầu

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 hayvà 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 LeohardEuler đã phát biểu nó thành một bài toán như sau:

"Có m chiếc kẹo giống nhau, cần chia chúng cho n 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ánnà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ôisẽ 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ảntớ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ản2. 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 11 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:

II. Một số bài toán minh họa1. Đếm đường điĐề bài

Cho một lưới gồm các ô vuông. Các ô được đánh số từ 0 đến

m

theo chiều từ trái sang phải vàtừ 0 đến

n

theo chiều từ dưới lên trên. Giả sử ta đang ở ô (0,0);(0,0); ta chỉ có thể di chuyển trêncạ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) đến ô (0,0) đến ô (

m

,

n

) của lưới ôvuông?

Input:



Một dòng duy nhất chứa hai số nguyên

m

và

n

.

Ràng buộc:



1≤

m

,

n

≤5000.



m

+

n

≤5000.

Output:



In ra số dư của kết quả của bài toán sau khi chia cho 10

9

+7.Input output2 3 10

Cài đặt

include 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++) {

Bài toán chia kẹo của Euler là bài toán nổi tiếng trong Lý thuyết tổ hợp. Với những học sinh chuyên Toán cấp 3 thì đây là bài toán quen thuộc và có nhiều ứng dụng. Dưới đây là một cách tiếp cận bài toán chia kẹo của Euler cho học sinh lớp 6 & 7 để thấy rằng các bài toán đếm nói riêng và các bài toán tổ hợp nói chung luôn là những bài toán mà lời giải của nó chứa đựng sự hồn nhiên và ngây thơ.

Trước hết, xin phát biểu lại bài toán chia kẹo của Euler

Bài toán chia kẹo của Euler: Có cái kẹo (giống nhau) chia cho em bé, hỏi có bao nhiêu cách chia sao cho em nào cũng có kẹo.

Một cách hợp lí, ta hãy xét bài toán trong trường hợp cụ thể, đơn giản hơn để từ đó định hướng đưa ra lời giải cho bài toán tổng quát.

Bài toán 1. Có cái kẹo (giống nhau) chia cho 3 em bé, hỏi có bao nhiêu cách chia sao cho

1. mỗi em có ít nhất cái kẹo.

2. mỗi em có ít nhất cái kẹo.

3. em thứ nhất có ít nhất cái kẹo, em thứ hai có ít nhất cái kẹo và em thứ ba có nhiều nhất cái kẹo.

Lời giải.

1. Nhận thấy rằng, vì mỗi em có ít nhất một cái kẹo nên số kẹo của em thứ nhất nhận được ít nhất là và nhiều nhất là Xét các trường hợp

Trường hợp 1. Em thứ nhất nhận được cái kẹo, thì số kẹo của em thứ hai có thể là em thứ ba nhận số kẹo còn lại sau khi chia cho em thứ nhất và em thứ hai xong, nghĩa là trong trường hợp này có cách chia kẹo. Trường hợp 2. Em thứ nhất nhận được 2 cái kẹo, khi đó số kẹo của em thứ hai có thể là em thứ ba nhận số kẹo còn lại, nghĩa là trong trường hợp này có cách chia kẹo

…

Hoàn toàn tương tự cho các trường hợp còn lại, ta nhận thấy số cách chia cái kẹo cho em bé sao cho em nào cũng có kẹo là

Trên đây là lời giải của bài toán chia kẹo Euler – bài toán đếm nổi tiếng với nhiều ứng dụng trong các bài toán đếm khác. Bài này tác giả sẽ trình bày bài toán gốc cơ bản và một số bài toán đếm dạng ứng dụng mà nếu đếm theo cách thông thường sẽ rất khó khăn, nhưng khi hiểu theo các đếm của bài toán Euler thì bài toán lại trở thành đơn giản.