© Được viết bởi CaolacVC. Blog https://caolacvc.blogspot.com
CHUYÊN ĐỀ: BÀI TOÁN CHIA KẸO EULER (STARS AND BARS)
1. Lý Thuyết Cơ Bản
Bài toán gốc: Có $n$ chiếc kẹo giống nhau chia cho $k$ em bé ($n \ge k$). Hỏi có bao nhiêu cách chia sao cho mỗi em bé đều có ít nhất 1 chiếc kẹo?
Số cách chia là số nghiệm nguyên dương của phương trình: $$x_1 + x_2 + ... + x_k = n$$
Công thức 1 (Nghiệm nguyên dương):
Số nghiệm nguyên dương ($x_i \ge 1$) của phương trình $x_1 + x_2 + ... + x_k = n$ là:
$$ \binom{n-1}{k-1} = C_{n-1}^{k-1} $$
Công thức 2 (Nghiệm nguyên không âm):
Số nghiệm nguyên không âm ($x_i \ge 0$) của phương trình $x_1 + x_2 + ... + x_k = n$ là:
$$ \binom{n+k-1}{k-1} = C_{n+k-1}^{k-1} $$
Phương trình $\sum_{i=1}^{k} x_i = n$ thỏa mãn $x_i \ge d_i$ (với $d_i \ge 0$) có số nghiệm là:
$$ \binom{n + k - D - 1}{k - 1} $$
Trong đó $D = \sum_{i=1}^{k} d_i$.
2. Các Ví Dụ Minh Họa
Ví dụ 1 (Bài toán khai triển): Xét khai triển $P = (2022a + 2023b + 2024c + 2025d)^{2025}$. Hỏi có tất cả bao nhiêu số hạng trong khai triển này?
Lời giải:
Số hạng tổng quát có dạng $Hệ\_số \times a^{x_1} b^{x_2} c^{x_3} d^{x_4}$ với $x_i \in \mathbb{N}$ và $x_1 + x_2 + x_3 + x_4 = 2025$.
Đây là bài toán tìm số nghiệm nguyên không âm của phương trình 4 ẩn với tổng bằng 2025.
Số nghiệm là: $\binom{2025 + 4 - 1}{4 - 1} = \binom{2028}{3}$.
Ví dụ 2 (Nghiệm có điều kiện): Có bao nhiêu bộ số tự nhiên $x_i$ ($i=\overline{1,5}$) thỏa mãn:
$$x_1 + x_2 + x_3 + x_4 + x_5 = 2016$$
với $x_1 \ge 5, x_2 \ge 4, x_3 \ge 3, x_4 \ge 2, x_5 \ge 1$.
Lời giải:
Đặt $y_1 = x_1 - 5, y_2 = x_2 - 4, y_3 = x_3 - 3, y_4 = x_4 - 2, y_5 = x_5 - 1$.
Khi đó $y_i \ge 0$. Phương trình trở thành:
$$ (y_1+5) + (y_2+4) + (y_3+3) + (y_4+2) + (y_5+1) = 2016 $$
$$ \Leftrightarrow y_1 + y_2 + y_3 + y_4 + y_5 = 2016 - (5+4+3+2+1) = 2001 $$
Số bộ số thỏa mãn là số nghiệm nguyên không âm của phương trình mới:
$$ \binom{2001 + 5 - 1}{5 - 1} = \binom{2005}{4} $$
Ví dụ 3 (Bất phương trình): Có bao nhiêu bộ số tự nhiên $x_i$ thỏa mãn:
$$x_1 + x_2 + x_3 + x_4 + x_5 \le 44$$
Lời giải:
Ta thêm một biến giả $x_6 \ge 0$ (phần bù) sao cho:
$$x_1 + x_2 + x_3 + x_4 + x_5 + x_6 = 44$$
Số nghiệm của bất phương trình ban đầu chính bằng số nghiệm nguyên không âm của phương trình trên (6 ẩn).
Kết quả: $\binom{44 + 6 - 1}{6 - 1} = \binom{49}{5}$.
Ví dụ 4 (Bài toán số học): Có bao nhiêu bộ số nguyên dương $(a; b; c)$ thỏa mãn $a < b < c$ và $a + b + c = 222$?
Lời giải:
Bỏ qua điều kiện $a < b < c$, số nghiệm nguyên dương của $a+b+c=222$ là $\binom{222-1}{3-1} = \binom{221}{2} = 24310$.
Xét các trường hợp trùng nhau:
- $a=b=c$: $3a=222 \Rightarrow a=74$. Có 1 bộ $(74; 74; 74)$.
- $a=b \ne c$: $2a+c=222$. Vì $c > 0 \Rightarrow 2a < 222 \Rightarrow a < 111$. Có 110 giá trị $a$, trừ trường hợp $a=74$ (ba số bằng nhau), còn lại 109 bộ. Tương tự cho $a=c$ và $b=c$. Tổng cộng $3 \times 109 = 327$ bộ có đúng 2 số bằng nhau.
Số bộ có 3 số phân biệt là: $24310 - 1 - 327 = 23982$.
Vì vai trò $a, b, c$ như nhau, số bộ thỏa mãn thứ tự $a < b < c$ là: $\frac{23982}{3!} = 3997$.
Ví dụ 5: Có bao nhiêu bộ số tự nhiên $x_i, i = \overline{1,6}$ thỏa mãn $x_1 + x_2 + x_3 + x_4 + x_5 + x_6 = 100$, với $x_i$ là bội của 5.
Lời giải:
Đặt $x_i = 5y_i, i = \overline{1,6}$ thì $y_1 + y_2 + y_3 + y_4 + y_5 + y_6 = 20$.
Khi đó số nghiệm là $\binom{20 + 6 - 1}{6 - 1} = \binom{25}{5}$.
Ví dụ 6: Có bao nhiêu bộ số tự nhiên $x_i$ thỏa mãn $x_1 + x_2 + x_3 = 1000$, với $x_1 \leqslant 100$.
Lời giải:
Với bài toán này ta sẽ sử dụng phần bù để giải quyết, ta sẽ đếm theo các bước sau:
- Đếm các bộ số tự nhiên thỏa mãn phương trình $x_1 + x_2 + x_3 = 1000$ (bỏ qua điều kiện $x_1 \leqslant 100$).
- Đếm các bộ số tự nhiên thỏa mãn phương trình nhưng vi phạm điều kiện (tức là $x_1 \geqslant 101$).
Trước tiên, số nghiệm không âm của phương trình $x_1 + x_2 + x_3 = 1000$ là:
$$\binom{1000 + 3 - 1}{3 - 1} = \binom{1002}{2}$$
Tiếp theo với $x_1 \geqslant 101$ thì đặt $y_1 = x_1 - 101$, đưa về phương trình $y_1 + x_2 + x_3 = 899$. Số nghiệm là $\binom{901}{2}$.
Do đó, số bộ số thỏa mãn yêu cầu bài toán là: $\binom{1002}{2} - \binom{901}{2}$.
Ví dụ 7: Có bao nhiêu bộ số tự nhiên $x_i$ thỏa mãn $x_1 + x_2 + x_3 = 10$, với $x_3 \neq 3$.
Lời giải:
Bài này sẽ tiếp tục dùng nguyên lý bù trừ giống bài toán trên, trước tiên ta thấy số nghiệm của phương trình $x_1 + x_2 + x_3 = 10$ là
$$\binom{10 + 3 - 1}{3 - 1} = \binom{12}{2} = 66.$$
Nếu $x_3 = 3$ thì ta đưa về xét $x_1 + x_2 = 7$ với số nghiệm là
$$\binom{7 + 2 - 1}{2 - 1} = \binom{8}{1} = 8.$$
Khi đó số bộ số tự nhiên thỏa mãn là $66 - 8 = 58$.
Ví dụ 8 (Đề thi thử Sở Phú Thọ 2025): Có bao nhiêu số tự nhiên có 4 chữ số mà tổng tất cả các chữ số của số đó bằng 7?
Lời giải:
Đây là một bài toán mới đây đã xuất hiện trong đề thi của sở Phú Thọ, nhìn chung ý tưởng khá là dễ. Trước tiên ta giả sử rằng số thỏa mãn có dạng $\overline{abcd}$.
Khi đó theo giả thiết ta sẽ có $a + b + c + d = 7$, ở đây $a \geqslant 1$ và $b, c, d \geqslant 0$. Chú ý rằng bài toán gốc của chúng ta xét có điều kiện các biến đều lớn hơn hoặc bằng 1, như vậy để đưa về bài toán Euler thì ta cần áp dụng thủ thuật giống như ví dụ 2 ở phần trước. Ta có:
$$\underbrace{a}_{\geqslant 1} + \underbrace{(b + 1)}_{\geqslant 1} + \underbrace{(c + 1)}_{\geqslant 1} + \underbrace{(d + 1)}_{\geqslant 1} = 10$$
Tới đây thì quá đơn giản rồi, số bộ số thỏa mãn sẽ là $\binom{10 - 1}{4 - 1} = 84$.
Ví dụ 9 (Chọn đội tuyển lớp 11 Bình Dương 2020–2021). Có 5 con xúc xắc được đánh 5 số thứ tự 1, 2, 3, 4, 5. Gieo đồng thời cả 5 xúc xắc đó. Tính xác suất để tổng của 5 số trên mặt xuất hiện của 5 xúc xắc bằng 14.
Lời giải:
Gọi con số xuất hiện trên con xúc sắc thứ $i$ ($1 \leqslant i \leqslant 5$) là $x_i$ ($1 \leqslant x_i \leqslant 6$). Khi này ta cần tìm số nghiệm nguyên dương của phương trình
$$x_1 + x_2 + x_3 + x_4 + x_5 = 14, \quad 1 \leqslant x_i \leqslant 6.$$
Ở đây chú ý rằng không thể có 2 giá trị $x_j$ và $x_k$ nào cùng lớn hơn hoặc bằng 7 cả nên để đếm số nghiệm của bài toán ta sẽ thực hiện theo 2 bước sau:
Bước 1. Đếm số bộ nghiệm nguyên dương của phương trình $x_1 + x_2 + x_3 + x_4 + x_5 = 14$;
Bước 2. Trừ đi các trường hợp mà có một giá trị $x_k$ nào đó lớn hơn hoặc bằng 7.
Đầu tiên, theo bài toán chia kẹo Euler thì số nghiệm nguyên dương của phương trình $x_1 + x_2 + x_3 + x_4 + x_5 = 14$ là $\binom{13}{4}$. Tiếp theo ta đếm các trường hợp mà có một giá trị $x_k$ nào đó lớn hơn hoặc bằng 7. Giả sử
$$x_1 \geqslant 7,$$
khi đó ta đổi biến $y_1 = x_1 - 6 \geqslant 1$, phương trình trở thành
$$y_1 + x_2 + x_3 + x_4 + x_5 = 8,$$
theo bài toán chia kẹo số nghiệm nguyên dương của phương trình này là
$$\binom{8 - 1}{5 - 1} = \binom{7}{4}.$$
Vì vai trò của các xúc xắc là như nhau nên số nghiệm của trường hợp này sẽ là
$$5 \times \binom{7}{4}.$$
Như vậy nếu ta gọi $A$ là biến cố để tổng 5 số bằng 14 thì
$$n(A) = \binom{13}{4} - 5 \times \binom{7}{4} = 540.$$
Cuối cùng ta có $n(\Omega) = 6^5 = 7776$ nên xác suất cần tính
$$\mathcal{P}(A) = \frac{n(A)}{n(\Omega)} = \frac{540}{7776} = \frac{5}{72}.$$
3. Bài Tập Tự Luyện
Bài tập 3.1: Tìm số bộ số nguyên không âm $(x, y, z, t)$ thỏa mãn $1 \le x \le y \le z \le t \le 1000$.
Bài tập 3.3: Tìm số nghiệm nguyên của phương trình $a + b + c + d = 17$ với $a \ge 1, b \ge 2, c \ge 3, d \ge 4$.
Bài tập 3.4: Tìm số nghiệm nguyên của phương trình $x_1 + x_2 + x_3 + x_4 = 17$ với $3 \le x_i \le 5$ ($i=\overline{1,4}$).
Bài tập 3.6: Tìm số nghiệm nguyên không âm của bất phương trình $x_1 + x_2 + x_3 + x_4 \le 11$.
Bài tập 3.10: Có $n$ vật giống hệt nhau và $m$ hộp phân biệt ($n \ge m$).
- a) Hỏi có bao nhiêu cách phân phối hết $n$ vật vào $m$ hộp?
- b) Hỏi có bao nhiêu cách phân phối sao cho mỗi hộp có ít nhất 1 vật?
Bài tập 3.23: Có bao nhiêu cách lập một số tự nhiên có ba chữ số $\overline{abc}$ thỏa mãn $a \le b \le c$.
4. Kiểm Tra Nhanh (Quiz)
Câu 1: Số nghiệm nguyên dương của phương trình $x_1 + x_2 + x_3 + x_4 = 10$ là:
Câu 2: Số nghiệm nguyên không âm của phương trình $x_1 + x_2 + x_3 = 10$ là:
Biên soạn: PimaX (Dựa trên tài liệu Chuyên đề bài toán chia kẹo Euler)
0 Comments
Vui lòng đăng nhập google để bình luận
Để gõ công thức toán, hãy đặt [biểu thức toán] trong dấu $$
Ví dụ: $[biểu thức toán]$