Chủ đề này có 4 trả lời

[hxthanh]

Với $n$ là số nguyên dương cho trước $(n\ge 6)$

Xét hai hệ nguyên:

$\begin{cases}a+b+c=n\\ 1\le a<b<c\le n\end{cases} \quad (1) \qquad \begin{cases}2x=3y+4z\\ 1\le x,y,z\le n-1\end{cases}\quad (2)$

 

$\boxed 1$ Chứng minh rằng số các bộ nguyên dương $(a,b,c)$ thỏa mãn $(1)$ và số các bộ nguyên dương $(x,y,z)$ thỏa mãn $(2)$ là bằng nhau! (Hai hệ có số nghiệm như nhau!)

 

$\boxed 2$ Gọi $S_n$ là số nghiệm của mỗi hệ. Chứng minh rằng:

$S_n=\left\lceil\dfrac{(n-1)(n-5)}{12}\right\rceil$

với $\lceil x\rceil$ là hàm Ceilling (số nguyên nhỏ nhất không nhỏ hơn $x$)

 

hoặc chứng minh rằng:

$S_n=1+\left\lfloor\dfrac{n(n-6)}{12}\right\rfloor$

với $\lfloor x\rfloor$ là hàm Phần nguyên (số nguyên lớn nhất không lớn hơn $x$)

[hxthanh]

Với $n$ là số nguyên dương cho trước $(n\ge 6)$

Xét hai hệ nguyên:

$\begin{cases}a+b+c=n\\ 1\le a<b<c\le n\end{cases} \quad (1) \qquad \begin{cases}2x=3y+4z\\ 1\le x,y,z\le n-1\end{cases}\quad (2)$

 

$\boxed 1$ Chứng minh rằng số các bộ nguyên dương $(a,b,c)$ thỏa mãn $(1)$ và số các bộ nguyên dương $(x,y,z)$ thỏa mãn $(2)$ là bằng nhau! (Hai hệ có số nghiệm như nhau!)

 

$\boxed 2$ Gọi $S_n$ là số nghiệm của mỗi hệ. Chứng minh rằng:

$S_n=\left\lceil\dfrac{(n-1)(n-5)}{12}\right\rceil$

với $\lceil x\rceil$ là hàm Ceilling (số nguyên nhỏ nhất không nhỏ hơn $x$)

 

hoặc chứng minh rằng:

$S_n=1+\left\lfloor\dfrac{n(n-6)}{12}\right\rfloor$

với $\lfloor x\rfloor$ là hàm Phần nguyên (số nguyên lớn nhất không lớn hơn $x$)

 

Nguồn gốc

Hệ $(1)$ được phát biểu dưới hình thức màu mè một chút là: "Có bao nhiêu cách chia $n$ cái kẹo thành ba phần không giống nhau?". Bài toán này được tôi phát biểu từ khi còn là học sinh, khi được học về "Bài toán chia kẹo của Euler" tôi đã thắc mắc bài toán này với thầy giáo của tôi, thầy tôi bảo để ông về xem lại và trả lời tôi sau. Sau đó thì nó từ từ trôi dần vào quên lãng!

Bằng các công cụ tính tổng và những kiến thức tổng hợp về phần nguyên thực tế tôi đã tìm được câu trả lời cho mình với bài toán này. (Lời giải đó khá dài dòng và phức tạp!) Tuy nhiên, với những công cụ đếm của tổ hợp, một lần nữa tôi lại khai quật bài toán này lên và thấy rằng nó thật đơn giản biết bao!

 

Đầu tiên ta sẽ giải quyết vấn đề $\boxed 1$ bằng các phép biến đổi song ánh.

Phần 1

Vì $a,b,c\;$ là những số nguyên dương và $a<b<c\;$ nên ta có thể đặt:

$\begin{cases}a=x\\b=x+y\\c=x+y+z\end{cases}$

với $x,y,z$ cũng là những số nguyên dương và khi đó $(1)\Leftrightarrow n=a+b+c=3x+2y+z=n\quad (1')$

Như vậy đếm số nghiệm của $(1)$ cũng tương đương với việc đếm số nghiệm nguyên dương của $(1')$

 

Rồi xét đến $(2)$, ta có:

Dễ thấy $y$ phải là số chẵn: Đặt $y=2y'$ ($y'$ cũng nguyên dương) thì ta có phương trình tương đương

$x=3y'+2z\quad (2')$

mà điều kiện là $x=3y'+2z\le n-1<n\;$ nên ta đặt $x'=n-x\;$ thì $x'$ cũng nguyên dương (cũng thuộc đoạn [1,n-1]) và khi đó $(2')$ trở thành:

$3y'+2z+x'=n\quad (2'')$

Rõ ràng là số nghiệm nguyên dương của $(2'')$ với $(1')$ là như nhau! Suy ra điều phải chứng minh.

 

Bây giờ sẽ là phần $\boxed 2$, phần hay nhất của bài toán này! Ta sẽ dùng phép gộp vào-loại ra (inclusion - exclusion) để đếm!

Phần 2

Xét tập các bộ nghiệm nguyên dương $(a,b,c)\;\;$ của bài toán chia kẹo Euler (với $n\;$ cái kẹo và 3 đứa trẻ sao cho đứa nào cũng có kẹo). Ta có tất cả $\displaystyle {n-1\choose 3-1}=\frac{(n-1)(n-2)}{2}\;\;$ bộ như vậy.

Trong số này, ta sẽ loại đi các bộ có $2\;$ số bằng nhau kiểu $(a,a,b)\;$. Có 3 dạng loại này là $(a,a,b);\;(a,b,a)\;\;$ và $\;(b,a,a)$.

Ta có: $a+a+b=2a+b=n\Rightarrow 2a=n-b\le n-1\Rightarrow a\le \left\lfloor\dfrac{n-1}{2}\right\rfloor$

Ta được: $S_1=\frac{(n-1)(n-2)}{2}-3\left\lfloor\dfrac{n-1}{2}\right\rfloor$

Với $S_1$ thì ta đã loại đi 3 lần bộ $(a,a,a)\;$ nên ta sẽ thêm vào 2 lần số bộ này.

Gọi số bộ $(a,a,a)\;$ là $S_0$ thì $S_0=0\;$ nếu $3\nmid n\;$ và $S_0=1\;$ nếu $3\mid n$

Như vậy ta có:

$S_2=\frac{(n-1)(n-2)}{2}-3\left\lfloor\dfrac{n-1}{2}\right\rfloor+2\times\begin{cases}0:\quad if\quad 3\nmid n\\1:\quad if\quad 3\mid n\end{cases}$

 

$S_2$ chính là số bộ $(a,b,c)\;\;$ với $a,b,c\;$ nguyên dương và đôi một khác nhau thỏa $\;a+b+c=n$

Và nghiệm của bài toán chính là $\dfrac{S_2}{3!}$

 

Cuối cùng thì chỉ còn phải xét 6 trường hợp tương ứng $n=6m+r\;\;$ với $r=\{0,1,2,3,4,5\}\;\;$ để có điều cần chứng minh.

[hxthanh]

Các bạn có thể giải bài toán tương tự: ở đây

và ...

Bài toán 2

Tìm số nghiệm nguyên dương của phương trình: $a+b+c\equiv 0\pmod n$ thỏa mãn điều kiện $1\le a<b<c\le n$

Bài toán 3

Gieo một hột xí ngầu (súc xắc) 3 lần. Tính xác suất để được tổng số chấm (mặt trên) của xí ngầu là $10$

[quocbaolqd11]

em nhớ bài 1 thầy đã làm ở bên MS, lời giải rất kinh.
 

Diễn đạt theo các điều kiện của bài toán, ta có bài toán đếm nghiệm của hai hệ sau:

$\begin{cases}a+b+c=n\\ 1\le a<b<c\le n\end{cases}\quad(1){}\quad$ và ${}\quad\begin{cases}a+b+c=2n\\1\le a<b<c\le n\end{cases}\quad(2)$

$\boxed{\text{Xét Hệ điều kiện }(1)}$

Ta có: $n=a+b+c \ge a+(a+1)+(a+2) \Rightarrow a\le \left\lfloor \frac{n}{3} \right\rfloor -1$

Với mỗi giá trị của $a$, đặt $b=a+x$ còn lại $c=n-2a-x$

Từ điều kiện $b<c$ suy ra $a+x<n-2a-x$ Suy ra $x\le \left\lfloor \frac{n-3a-1}{2} \right\rfloor$

Như vậy ta có số nghiệm của hệ là:

$A=\displaystyle\sum_{a=1}^{\left\lfloor \frac{n}{3} \right\rfloor -1}\left\lfloor \frac{n-3a-1}{2} \right\rfloor$

$\quad =\displaystyle\sum_{a=1}^{\left\lfloor \frac{n}{3} \right\rfloor -1}\left(\left\lfloor \frac{n-1-a}{2} \right\rfloor -a\right)$

$\displaystyle\quad =-\frac{1}{2}\left\lfloor \frac{n}{3} \right\rfloor \left( \left\lfloor \frac{n}{3} \right\rfloor -1 \right)+\underbrace{\displaystyle\sum_{a=1}^{\left\lfloor \frac{n}{3} \right\rfloor -1} \left\lfloor \frac{n-1-a}{2} \right\rfloor}_{S_1}$

Ta có:

$\displaystyle\quad S_1=\sum_{a=2}^{\left\lfloor \frac{n}{3} \right\rfloor}\left\lfloor \frac{n-a}{2} \right\rfloor \quad\text{(Tịnh tiến)}$

$\displaystyle\Rightarrow 2S_1=\left\lfloor \frac{n-2}{2} \right\rfloor+\left\lfloor \dfrac{n-\left\lfloor \frac{n}{3}\right\rfloor}{2} \right\rfloor +\sum_{a=2}^{\left\lfloor \frac{n}{3} \right\rfloor -1}\left( \left\lfloor \frac{n-1-a}{2} \right\rfloor +\left\lfloor \frac{n-a}{2} \right\rfloor \right)$

$\displaystyle\Rightarrow 2S_1=\left\lfloor \frac{n-2}{2} \right\rfloor +\left\lfloor \dfrac{n-\left\lfloor \frac{n}{3} \right\rfloor}{2} \right\rfloor +\sum_{a=2}^{\left\lfloor \frac{n}{3} \right\rfloor-1}(n-1-a)\quad\text{(Hermite's identity)}$

Đến đây ta gặp tổng cơ bản rồi! Tuy nhiên biểu thức nhận được của tổng này khá dài dòng.

Sử dụng phép thế $n=6p+r$ với $p=\left\lfloor \frac{n}{6} \right\rfloor$ và $r=n-6\left\lfloor \frac{n}{6} \right\rfloor=\{0,1,2,3,4,5\}\quad(*)$

$(*)$ mỗi giá trị tương ứng với các số dư của $n$ khi chia cho $6$.

Thay vào biểu thức tìm được rồi rút gọn lại ta được:

$A=3p^2+p\{-3,-2,-1,0,1,2\}+\{1,0,0,0,0,0\}$

$\quad=3p^2+p(r-3)-\left\lfloor \frac{r-1}{6} \right\rfloor$

$\quad=3\left\lfloor \frac{n}{6} \right\rfloor^2+\left\lfloor \frac{n}{6} \right\rfloor \left(n-6\left\lfloor \frac{n}{6} \right\rfloor -3\right) - \left\lfloor \frac{n-6\left\lfloor \frac{n}{6} \right\rfloor -1}{6} \right\rfloor $

$\quad=(n-2)\left\lfloor \frac{n}{6} \right\rfloor -3 \left\lfloor \frac{n}{6} \right\rfloor^2 -\left\lfloor \frac{n-1}{6} \right\rfloor $

$\boxed{\text{Xét Hệ điều kiện }(2)}$

Ta có:

$2n=a+b+c\ge a+(a+1)+(a+2)\Rightarrow a\le\left\lfloor\frac{2n}{3}\right\rfloor-1$

$a+1\le b\le c-1\le n-1$

$b+1\le c\le n$

Lưu ý rằng với $x,y$ nguyên dương thì

$\quad \Delta_x \left( \left\lfloor \frac{x}{y} \right\rfloor \right) =\left\lfloor \frac{x+1}{y} \right\rfloor - \left\lfloor \frac{x}{y} \right\rfloor = \begin{cases} 1\quad\text{nếu } y\mid x+1 \\ 0 \quad \text{các trường hợp khác} \end{cases}\quad(**)$

Do đó ta quy các điều kiện về tổng:

$B=\displaystyle \sum_{a=1}^{\left\lfloor \frac{2n}{3} \right\rfloor - 1} \sum_{b=a+1}^{n-1} \sum_{c=b+1}^n \Delta_c \left( \left\lfloor \frac{a+b+c-1}{2n} \right\rfloor \right) $

$\displaystyle\quad =\sum_{a=1}^{\left\lfloor \frac{2n}{3} \right\rfloor - 1}\sum_{b=a+1}^{n-1}\left( \left\lfloor \frac{a+b+n}{2n} \right\rfloor - \left\lfloor \frac{a+2b}{2n} \right \rfloor\right) $

$\quad=\underbrace{\displaystyle \sum_{a=1}^{\left\lfloor \frac{2n}{3} \right\rfloor - 1}\sum_{b=a+1}^{n-1}\left\lfloor \frac{a+b+n}{2n} \right\rfloor}_{S_2} -\underbrace{\displaystyle \sum_{a=1}^{\left\lfloor \frac{2n}{3} \right\rfloor - 1} \sum_{b=a+1}^{n-1}\left\lfloor \frac{a+2b}{2n} \right\rfloor }_{S_3} $

Đối với 2 tổng $S_2$ và $S_3$ ta cần vận dụng tới các kỹ thuật tính toán SPTP, phân đoạn modul-2 và tính chất $(**)$ nữa mới giải quyết ổn thỏa!

$\boxed{\text{Xét Tổng }S_2}$

Ta có:

$\displaystyle S_2 = \sum_{a=1}^{\left\lfloor \frac{2n}{3} \right\rfloor - 1}\sum_{b=a+1}^{n-1}\left\lfloor \frac{a+b+n}{2n} \right\rfloor \Delta(b)$

$\displaystyle\quad =\sum_{a=1}^{\left\lfloor \frac{2n}{3}\right\rfloor - 1}\left( b \left\lfloor \frac{a+b+n}{2n} \right\rfloor\Bigg|_{b=a+1}^n - \underbrace{\displaystyle \sum_{b=a+1}^{n-1} (b+1) \Delta_b \left( \left\lfloor \frac{a+b+n}{2n} \right\rfloor \right)}_{S_4} \right) $

Theo tính chất $(**)$ thì tổng $S_4$

$\displaystyle S_4=\sum_{b=a+1}^{n-1}(b+1) \Delta_b \left( \left\lfloor \frac{a+b+n}{2n} \right\rfloor \right) = \begin{cases} \displaystyle \sum_{b=a+1}^{n-1}(b+1)\quad\text{với } 2n\mid a+b+n+1 \text{ và } a+1\le b\le n-1 \\ 0 \quad \text{ các trường hợp khác} \end{cases} $

Nên với $a+b+n+1=2n$ hay $b=n-1-a\ge a+1$ suy ra $a\le \left\lfloor \frac{n}{2} \right\rfloor -1 $ thì

$S_4=b+1=n-a$. Các trường hợp khác $S_4=0$

Do đó:

$\displaystyle S_2=\sum_{a=1}^{\left\lfloor \frac{n}{2} \right\rfloor-1} \left( b\left\lfloor \frac{a+b+n}{2n} \right\rfloor \Bigg|_{b=a+1}^n-(n-a) \right) + \sum_{a=\left\lfloor \frac{n}{2} \right\rfloor}^{\left\lfloor \frac{2n}{3} \right\rfloor -1} \left( b\left\lfloor \frac{a+b+n}{2n} \right\rfloor\Bigg|_{b=a+1}^n \right) $

$\displaystyle =\sum_{a=1}^{\left\lfloor \frac{n}{2} \right\rfloor -1} (n-n+a) + \sum_{a=\left\lfloor \frac{n}{2} \right\rfloor}^{\left\lfloor \frac{2n}{3} \right\rfloor - 1} (n-(a+1).1) $

(Căn cứ vào đoạn biến thiên của $a$ để có được điều trên)

Đến đây ta coi như đã tính được $S_2$

$\boxed{\text{Xét Tổng }S_3}$

Tổng này ta phải phân loại tính chẵn lẻ của $a$ để rồi chia $S_3$ thành $2$ tổng nữa. Sau đó mỗi tổng được tính tương tự như $S_2$

....

Cuối cùng ta được kết quả (chưa rút gọn là: )

$B=S_2-S_3$

$\quad =\left\lfloor \frac{n}{2} \right\rfloor^2 -n\left\lfloor \frac{n}{2} \right\rfloor + \frac{1}{2} \left((2n-1)\left\lfloor \frac{2n}{3} \right\rfloor - \left\lfloor \frac{2n}{3} \right\rfloor ^2 + \left\lfloor \frac{n}{3} \right\rfloor - \left\lfloor \frac{n}{3} \right\rfloor ^2 - \left\lfloor \frac{n-2}{3} \right\rfloor \left\lfloor \frac{n-1}{3} \right\rfloor \right) $

Sử dụng phép thế $n=6p+r$ với $p=\left\lfloor \frac{n}{6}\right\rfloor $ và $r=n-6\left\lfloor \frac{n}{6}\right\rfloor=\{0,1,2,3,4,5\}$

Thay vào biểu thức tìm được rồi rút gọn lại ta được:

$B=3p^2+p\{0,1,2,3,4,5\}+\{0,0,0,1,1,2\}$

$\quad =(n-3)\left\lfloor \frac{n}{6} \right\rfloor - 3\left\lfloor \frac{n}{6} \right\rfloor ^2 + \left\lfloor \frac{n}{3} \right\rfloor + \left\lfloor \frac{n+1}{6} \right\rfloor $

CUỐI CÙNG TA CÓ ĐÁP SỐ CỦA BÀI TOÁN LÀ

Số các tập con 3 phần tử của tập $n$ số nguyên dương đầu tiên thỏa mãn điều kiện tổng các phần tử chia hết cho $n$ là:

$S_n=A+B=\boxed{\displaystyle (2n-5)\left\lfloor \frac{n}{6} \right\rfloor - 6\left\lfloor \frac{n}{6} \right\rfloor ^2 + \left\lfloor \frac{n}{3} \right\rfloor + \left\lfloor \frac{n+1}{6} \right\rfloor - \left\lfloor \frac{n-1}{6} \right\rfloor} $

 

[hxthanh]

em nhớ bài 1 thầy đã làm ở bên MS, lời giải rất kinh.
 

 

Lời giải đó đúng là rất "khủng" mà nó còn không có tính phương pháp. Nếu thêm vào một biến $d$ nữa thì lời giải "ngắn" cũng phải $15$ trang $A4$

Trong khi đó dùng phương pháp đếm bao gồm - loại trừ thì mất khoảng $15$ dòng!

 

Dường như có thể có cách dùng số phức để "đếm" nữa!

 

Các em thử làm xem!

Kết quả gọn gàng của Bài toán 2 là $\left\lceil\dfrac{(n-1)(n-2)}{6}\right\rceil$