Bài toán chia kẹo Euler và ứng dụng

Bài viết đề cập đến bài toán chia kẹo nổi tiếng của Euler và ứng dụng của nó trong một số trường hợp như tìm số nghiệm nguyên dương, nghiệm nguyên không âm của phương trình nhiều ẩn hoặc bài toán phân phối đồ vật giống nhau vào nhiều hộp phân biệt,...cùng nhiều ứng dụng khác sau khi đọc xong bài viết này các bạn có thể liên hệ để phát triển và ứng dụng vào giải quyết các bài tập khó của đại số tổ hợp.

Bài toán chia kẹo Euler

Bài toán 1: Có bao nhiêu cách chia n chiếc kẹo giống nhau m em bé sao cho mỗi em bé có ít nhất một chiếc kẹo?

Hay là bài toán, tìm số nghiệm nguyên dương của phương trình:

${{x}_{1}}+{{x}_{2}}+\cdot \cdot \cdot +{{x}_{m}}=n.$

Lời giải. Rõ ràng với $n<m$ ta không thể chia kẹo thỏa mãn đề bài.

Với $n\ge m.$ Ta đặt n chiếc kẹo thành một hàng, tạo ra (n-1) khoảng trống (giữa mỗi hai chiếc kẹo).

Bây giờ ta chỉ việc chọn ra (m-1) khoảng trống trong (n-1) khoảng trống đó, sau đó đặt vào các khoảng trống vừa chọn các thanh sẽ chia được n chiếc kẹo này thành m phần mà mỗi phần luôn có ít nhất một chiếc kẹo.

**|*|***|...|****

Vậy số cách chia kẹo là $C_{n-1}^{m-1}.$

Bài toán 2: Có bao nhiêu cách chia n chiếc kẹo giống nhau m em bé?

Hay là bài toán, tìm số nghiệm nguyên không âm của phương trình:

${{x}_{1}}+{{x}_{2}}+\cdot \cdot \cdot +{{x}_{m}}=n.$

Đặt ${{y}_{1}}={{x}_{1}}+1,{{y}_{2}}={{x}_{2}}+1,...,{{y}_{n}}={{x}_{n}}+1$ đưa về tìm số nghiệm nguyên dương của phương trình:

${{y}_{1}}+{{y}_{2}}+\cdot \cdot \cdot +{{y}_{m}}=n+m.$

Số cách chia kẹo là $C_{n+m-1}^{m-1}.$

>>Bản đọc tại website

>>TẢI VỀ BÀI VIẾT BẢN IN PDF