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ạn đang đọc: BÀI TOÁN CHIA KẸO EULER VÀ ỨNG DỤNG
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
a) mỗi em có ít nhất 
cái kẹo.
b) mỗi em có ít nhất 
cái kẹo.
c) 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 .
a) 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ự như cho những 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à giải thuật 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 những bài toán đếm khác. Bài này tác giả sẽ trình diễn bài toán gốc cơ bản và 1 số ít bài toán đếm dạng ứng dụng mà nếu đếm theo cách thường thì sẽ rất khó khăn vất vả, nhưng khi hiểu theo những đếm của bài toán Euler thì bài toán lại trở thành đơn thuần .
Source: https://bem2.vn
Category: Ứng dụng hay
