Đáp án bài toán MO:
Đếm xem có bao nhiêu cách chia $32$ cái kẹo giống nhau thành $4$ phần có số lượng khác nhau. (Mỗi phần ít nhất 1 cái kẹo)
Mở rộng bài toán nếu có thể!
Lời giải:
Điều kiện đề bài tương đương với số nghiệm của
$\left\{\begin{align} &a+b+c+d=32 \label{h1} \\ &1\le a<b<c<d;\quad a,b,c,d\in\mathbb N \label{h2}\end{align}\right.$
Ta định nghĩa các tập hợp sau:
$\begin{align*}
S&=\{(a,b,c,d)\quad|\quad a+b+c+d=32;\; a,b,c,d\in\mathbb N^*\}\\
S_2&=\{(a,a,b,c)\quad|\quad a+a+b+c=32;\; a,b,c\in\mathbb N^*\}\\
S_{22}&=\{(a,a,b,b)\quad|\quad a+a+b+b=32;\; a,b\in\mathbb N^*\}\\
S_3&=\{(a,a,a,b)\quad|\quad a+a+a+b=32;\; a,b\in\mathbb N^*\}\\
S_4&=\{(a,a,a,a)\quad|\quad a+a+a+a=32;\; a\in\mathbb N^*\}
\end{align*}\Rightarrow \left\{\begin{aligned}S_4\subset S_3\subset S_2 \subset S \\S_4\subset S_{22}\subset S_2 \subset S \end{aligned}\right.$
Ta sẽ đếm bằng phương pháp Gộp vào-Loại ra (Công thức bù trừ)
Để có các số bộ $(a,b,c,d)$ có các số đôi một khác nhau thỏa \eqref{h1}, ta lấy tổng số bộ có thể có $|S|$ trừ đi số các bộ có 2 số bằng nhau là $C_4^2.|S_2|$, trừ tiếp số các bộ có 2 cặp bằng nhau là $\dfrac{C_4^2}{2}\cdot|S_{22}|$, trừ cả số các bộ có 3 số bằng nhau là $C_4^3.|S_3|$, trừ nốt số bộ cả 4 số bằng nhau là $|S_4|$
Được $|S|-6|S_2|-3|S_{22}|-4|S_3|-|S_4|$
Nhưng...
Mỗi bộ thuộc $S_2$ có 1 cách (cho $b=c$) để trở thành bộ thuộc $S_{22}$ nên phải cộng vào $6|S_{22}|$
Mỗi bộ thuộc $S_2$ cũng có 2 cách (cho $b=a$ hoặc $c=a$) để trở thành bộ thuộc $S_3$ nên cũng phải cộng vào $12|S_3|$
Được $|S|-6|S_2|+3|S_{22}|+8|S_3|-|S_4|$
Nhưng...
Các tập $S_2$ hay $S_{22}$ hay $S_3$ đều bao hàm $S_4$
Do đó thêm bớt tương ứng ta có số các bộ $(a,b,c,d)$ đôi một khác nhau thỏa \eqref{h1} là:
$T=|S|-6|S_2|+6|S_4|+3|S_{22}|-3|S_4|+8|S_3|-8|S_4|-|S_4|$
\begin{equation} \label{h3} T=|S|-6|S_2|+3|S_{22}|+8|S_3|-6|S_4| \end{equation}
(Kết quả này đem chia cho 4! ta được số các bộ không phân biệt thứ tự)
Bây giờ ta sẽ tính cụ thể:
$|S|$ là số nghiệm nguyên dương của pt $\quad a+b+c+d=32$
$\Rightarrow |S|=C_{31}^{3}=4495$
$|S_2|$ là số nghiệm nguyên dương của pt $\quad 2a+b+c=32$ hay $b+c=32-2a$
$\Rightarrow |S_2|=\sum_{a=1}^{15} (31-2a)=225$
$|S_{22}|$ là số nghiệm nguyên dương của pt $\quad 2a+2b=32$ hay $a+b=16$
$\Rightarrow |S_{22}|=15$
$|S_3|$ là số nghiệm nguyên dương của pt $\quad 3a+b=32$ hay $a=\dfrac{32-b}{3}\le \left\lfloor\dfrac{32-1}{3}\right\rfloor=10$
$\Rightarrow |S_{3}|=10$
và $|S_4|=1$
Do đó: $T=4495-6.225+3.15+8.10-6.1=3264$
Vậy số nghiệm của hệ \eqref{h1}, \eqref{h2} là $\dfrac{3264}{4!}=136$
______________________________________________________________________________
Lập luận tương tự cho trường hợp tổng quát số kẹo là $n$
Lưu ý rằng: Nếu $n$ lẻ thì $|S_{22}|=0$; nếu $n$ không chia hết cho 4 thì $|S_4|=0$
Ta có:
$|S|$ là số nghiệm nguyên dương của pt $\quad a+b+c+d=n$
$\Rightarrow |S|=C_{n-1}^3=\dfrac{(n-1)(n-2)(n-3)}{6}$
$|S_2|$ là số nghiệm nguyên dương của pt $\quad 2a+b+c=n$ hay $b+c=n-2a$
$\Rightarrow |S_2|=\sum_{a=1}^{\left\lfloor\frac{n-2}{2}\right\rfloor} (n-1-2a)=(n-1)\left\lfloor\dfrac{n-2}{2}\right\rfloor-\left\lfloor\dfrac{n-2}{2}\right\rfloor \cdot \left\lfloor\dfrac{n}{2}\right\rfloor = \left\lfloor \dfrac{n-2}{2} \right\rfloor \cdot \left\lfloor\dfrac{n-1}{2}\right\rfloor=\left\lfloor\dfrac{(n-2)^2}{4}\right\rfloor$
$|S_{22}|$ là số nghiệm nguyên dương của pt $\quad 2a+2b=n$ hay $a+b=\frac{n}{2}$ ($n$ chẵn)
$\Rightarrow |S_{22}|=\left(\left\lfloor\dfrac{n}{2}\right\rfloor-\left\lfloor\dfrac{n-1}{2}\right\rfloor\right) \left(\dfrac{n}{2}-1\right)$
$|S_3|$ là số nghiệm nguyên dương của pt $\quad 3a+b=n$ hay $a=\dfrac{n-b}{3}\le \left\lfloor\dfrac{n-1}{3}\right\rfloor $
$\Rightarrow |S_{3}|=\left\lfloor\dfrac{n-1}{3}\right\rfloor$
Và $|S_4|=\left(\left\lfloor\dfrac{n}{4}\right\rfloor-\left\lfloor\dfrac{n-1}{4}\right\rfloor\right)$
Do đó theo \eqref{h3} ta có, số nghiệm nguyên dương của
$$ \begin{cases} a+b+c+d=n \\ 1\le a<b<c<d \end{cases}$$
là $ \frac{T}{4!}$
$$\small \frac{T}{4!}=\frac{(n-1)(n-2)(n-3)}{144}-\frac{1}{4}\left\lfloor\dfrac{(n-2)^2}{4}\right\rfloor+\frac{n-2}{16}\left(\left\lfloor\dfrac{n}{2}\right\rfloor-\left\lfloor\dfrac{n-1}{2}\right\rfloor\right)+\frac{1}{3}\left\lfloor\dfrac{n-1}{3}\right\rfloor-\frac{1}{4}\left(\left\lfloor\dfrac{n}{4}\right\rfloor-\left\lfloor\dfrac{n-1}{4}\right\rfloor\right)$$
Kết quả này có thể ứng dụng để giải một số bài toán tương đương như đếm số nghiệm của
$\begin{cases} a+b+c+d=n \\ 1\le a \le b \le c \le d \end{cases}$ hoặc $\begin{cases} a+b+c+d=n \\ 0\le a \le b \le c \le d \end{cases}$ hoặc $\begin{cases} a+b+c+d=n \\ m\le a \le b \le c \le d \end{cases}$ hoặc $\begin{cases} n\mid a+b+c+d \\ 1< a < b < c < d \end{cases}$ v.v...