MATHPIAD

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

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ự 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.

DOWNLOAD