Bài toán chia kẹo Euler và các ứng dụng hay trong bài toán tổ hợp lớp 11

BÀI TOÁN CHIA KẸO EULER VÀ ỨNG DỤNG - HUỲNH KIM LINH

---------------------------

Bài toán1. (Bài toán  chia kẹo của EULER)

Cho k, n là các số nguyên dương. Tìm số nghiệm nguyên không âm của phương trình $x_1+x_2+...+x_k=n$.

Đây là bài toán quen thuộc của toán đếm tổ hợp. Có thể kể ra một vài phương pháp giải quyết đối với bài toán này nhưđệ quy, hàm sinh,… Nhưng ở đây chúng ta sẽ tiếp cận nó theo một góc nhìn khác : Song ánh. Một cách tự nhiên ta nghĩ đến việc thiết lập một ánh xạ từ tập {x1 , x2 , … ,xk }. Và để thuận tiện ta sẽ cho ánh xạ này chạy vào một dãy nhị phân , đưa bài toán trở về đếm tổ hợp thông thường.

Lời giải.

Gọi A là họ các bộ {x1 , x2 , …  xk }thoả mãn phương trình, B là họ các dãy nhị phân có độ dài n + k - 1 gồm k - 1 kí tự 0 và n kí tự 1. Xét ánh xạ f  cho bởi quy tắc : Với mỗi bộ {x1 , x2 , …  xk } ta thực hiện viết liên tiếp từ trái qua phải x1 số 1, rồi đến số 0, rồi lại đến x2 số 1, cứ như thế đến hết xn. Như vậy ứng với mỗi bộ{x1 , x2 , …  xk } ta xây dựng được một dãy nhị phân có độ dài n +k-1 gồm k-1 số 0 và n số 1. Ta chứng minh được f  là một song ánh.

Vậy số nghiệm của phương trình (*) sẽ tương ứng với số dãy nhị phân có độ dài n+k-1 gồm k-1 số 0 và n số 1. Mặt khác mỗi dãy nhị phân tương ứng với một cách chọn k-1 vị trí cho số 0 nên số dãy nhị phân thoả mãn là $C_{n+k-1}^{k-1}$.

Như vậy với cách giải trên, bằng phương pháp song ánh đã đưa bài toán tính số nghiệm nguyên về một bài toán vị trí của tổ hợp đơn giản bằng cách đưa về dãy nhị phân. Song ánh từ một tập số đến một dãy nhị phân được sử dụng khá nhiều trong các bài toán tổ hợp, đặc biệt là các bài toán ứng dụng của Bài toán chia kẹo của EULER . Ta có thể kể đến một số bài toán sau:

Bài toán 2.

Một cửa hàng kem có bán ba loại kem: kem xoài, kem socola và kem sữa. Một nhóm có 6 người vào ăn kem và gọi 6 cốc kem.

1. Hỏi họ có bao nhiêu sự lựa chọn?

2. Họ có tất cả bao nhiêu sự lựa chọn trong đó cả ba loại kem đều có mặt?

XEM TRỰC TUYẾN VÀ TẢI VỀ DƯỚI ĐÂY