Đến nội dung

Hình ảnh

Trận 9 - Tổ hợp, rời rạc

mo 2014

  • Please log in to reply
Chủ đề này có 11 trả lời

#1
E. Galois

E. Galois

    Chú lùn thứ 8

  • Quản lý Toán Phổ thông
  • 3861 Bài viết

Vào hồi 20h00, Thứ Sáu, ngày 09/05/2014, Tổ trọng tài sẽ ra đề vào topic này, sau khi có đề, các toán thủ bắt đầu thi đấu.
 

 

 

 

II - Lưu ý

1) Các toán thủ khi thi đấu, cứ yên tâm rằng, sau khi trả lời là bài làm đã được lưu, BTC đã nhận được bài làm của bạn, có điều bạn không nhìn thấy được mà thôi. Bạn nên mừng vì điều này, như thế các toán thủ khác không thể copy bài của bạn được.


Bạn cũng nên sử dụng chức năng xem trước của diễn đàn để sửa các lỗi LATEX trước khi gửi bài, vì gửi rồi sẽ không xem và sửa lại được nữa.

 

 
Để sử dụng chức năng xem trước, bạn click vào Sử dụng bộ soạn thảo đầy đủ và chọn Xem trước.

 


2) Các toán thủ chớ quên rằng mỗi một mở rộng đúng sẽ được 10 điểm, các bạn nên mở rộng bài toán để thu được nhiều điểm hơn

 

3) Thành viên diễn đàn không đăng kí thi đấu vẫn có thể giải bài, nhưng phải ghi rõ là: Mình không phải là toán thủ thi đấu

 

4) Trận 9 sẽ loại 4 toán thủ có số điểm thấp nhất


1) Xem cách đăng bài tại đây
2) Học gõ công thức toán tại: http://diendantoanho...oạn-thảo-latex/
3) Xin đừng đặt tiêu đề gây nhiễu: "Một bài hay", "... đây", "giúp tớ với", "cần gấp", ...
4) Ghé thăm tôi tại 
http://Chúlùnthứ8.vn

5) Xin đừng hỏi bài hay nhờ tôi giải toán. Tôi cực gà.


#2
hxthanh

hxthanh

    Tín đồ $\sum$

  • Hiệp sỹ
  • 3915 Bài viết

Đề bài của BTC

 

Đế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ể! 



#3
LNH

LNH

    Bất Thế Tà Vương

  • Hiệp sỹ
  • 581 Bài viết

Bài làm của toán thủ MO10-LNH

Gọi $x_1,x_2,x_3,x_4$ là số kẹo ở mỗi phần và $x_1<x_2<x_3<x_4$

Ta có:

$0 \leq x_1-1 \leq x_2-2 \leq x_3-3 \leq x_4-4$

$x_1+x_2+x_3+x_4=32$

Đặt $y_i=x_i-i$,$i=\overline{1,4}$

Từ đây suy ra:

$y_1+y_2+y_3+y_4=22$ với $y_i \geq 0$

Theo bài toán chia kẹo Euler, ta có số cách chọn $y_1,y_2,y_3,y_4$ là $\binom{25}{3}$

Vậy số cách chia $32$ cái kẹo thành $4$ phần là $\binom{25}{3}$



#4
Tru09

Tru09

    Thiếu úy

  • Thành viên
  • 625 Bài viết

Bài Làm :

Bài toán tương đương số nghiệm của hệ phương trình

$\left\{\begin{matrix} x+y+z+t =32 \\ x,y,z,t \in N* \\ x\neq y \neq z \neq t \end{matrix}\right.$
$\Leftrightarrow $$\left\{\begin{matrix} x-1+y-1+z-1+t-1 =28 \\ x,y,z,t \in N* \\ x\neq y \neq z \neq t \end{matrix}\right.$
$\Leftrightarrow $$\left\{\begin{matrix} a+b+c+d =28 \\ a,b,c,d :\text{Không âm} \\ a \neq b \neq c \neq d \end{matrix}\right.$
Ta xét phần bù . Số nghiệm không âm của phương trình a+b+c+d =28 là 4495
Trước hết ta tính số nghiệm không âm của phương trình a+b+c+d=28 với :$\begin{pmatrix} 31 \\ 3\end{pmatrix}$ =4495
 @~ > Với chỉ đúng 2 số trong 4 số bằng nhau .Không mất tính tổng quát giả sử 2 số đó là $a=b=k ( 0 \leq k \leq 14)$
$\Rightarrow c+d =28 -2k$
Để có đúng 2 số bằng nhau thì ta loại đi trường hợp $c=d  \neq 7$ ( xảy ra khi $0 \leq k \leq 14 ,k \neq 7$) ( có 14 trường hợp như vậy ) và Chỉ 1 trong 2 só $c,d =k$ ( chỉ xảy ra khi $0 \leq k\leq 9 và k \neq 7$) (có 18 trường hợp như vậy) và loại đi trường hợp $k=c=d$ ( chỉ xảy ra khi $ k=7$).( có 1 trường hợp như vậy )
Tóm lại ta phải loại đi 33 trường hợp .
Tóm lại với a=b thì số nghiệm không âm của phương trình $a+b+c+d =28$ là :$\sum (28 -2k) -32 =178$
Như vậy tổng cộng có 1068 nghiệm không âm của phương trình $a+b+c+d =28$ mà chỉ có đúng 2 số bằng nhau.
@~> Với chỉ đúng 3 số trong 4 số bằng nhau .Không mất tính tổng quát giả sử 3 số đó là $a=b=c=k (0 \leq k\leq9)$
$\Rightarrow d =28 -3k$
Để có đúng 3 số bằng nhau thì ta loại đi trường hợp $d= k$ nghĩa là $k =7$ .Vậy chỉ loại đi 1 trường hợp.
Vậy số nghiệm không âm  của phương trình $a+b+c+d=28$ có đúng 3 số bằng nhau là $9x4 =36.$
@~> Với đúng 4 số bằng nhau ( 1 trường hợp)
Tóm lại số nguyệm không âm có ít nhất 2 số bằng nhau của phương trình a+b+c+d =28 là 1068+36+1=1083
Vậy số nghiệm không âm đôi 1 khác nhau của phương trình $a+b+c+d =28$ là $4495-1083=3412$
Vậy số cách chia kẹo là 3412 cách chia .
 
 
 


#5
LNH

LNH

    Bất Thế Tà Vương

  • Hiệp sỹ
  • 581 Bài viết

Cho em làm lại bài của mình

Bài làm của toán thủ MO10-LNH

Gọi $x_1,x_2,x_3,x_4$ lần lượt là số kẹo ở mỗi phần

Không mất tính tổng quát, giả sử $x_1<x_2<x_3<x_4$

Đặt $x_i=x_{i-1}-s_i$, với $i=2,3,4$. Ta có:

$32=x_1+x_2+x_3+x_4=x_1+x_2+2x_3+s_4=x_1+3x_2+2s_3+s_4=4x_1+3s_2+2s_3+s_4$

Ta đưa bài toán từ tìm số bộ nguyên dương $\left ( x_1,x_2,x_3,x_4 \right )$ thành đếm số bộ nguyên dương $\left ( x_1,s_2,s_3,s_4 \right )$

Đặt $y_1=x_1-1$, $y_i=s_i-1$, $i=2,3,4$, ta có:

$y_1+2y_2+...+4y_4=22$

Ta có:

$y_1+2y_2+...+4y_4=22$

$y_1 \leq 22$, $y_2 \leq 11$, $y_3 \leq 7$, $y_4 \leq 5$

Số bộ nguyên không âm $\left ( y_1,y_2,y_3,y_4 \right )$ chính là hệ số của $x^22$ trong đa thức sau:

$P\left ( x \right )=(1+x^4+...+x^{20})(1+x^3+...+x^{21})(1+x^2+...+x^{22})(1+x+...+x^{22})$

$=\frac{\left ( x^{24}-1 \right )^3(x^{23}-1)}{\left ( x-1 \right )...(x^4-1)}$

$=\frac{(x^{23}-1)(x^{24}-1)(x^{12}+1)^2(x^6+1)(x^2-x+1)(x^8+x^4+1)}{(x-1)^2}$

$=(...+x^{22}-2 x^{21}+4 x^{20}-2 x^{19}+4 x^{18}-2 x^{17}+3 x^{16}-x^{15}+3 x^{14}-2 x^{13}+3 x^{12}-x^{11}+2 x^{10}-x^9+2 x^8-x^7+2 x^6-x^5+x^4+x^2-x+1)(1+2x+3x^2+...)$

$=(...+x^{22}-2 x^{21}+5 x^{20}-2 x^{19}+4 x^{18}-2 x^{17}+3 x^{16}-x^{15}+3 x^{14}-2 x^{13}+3 x^{12}-x^{11}+2 x^{10}-x^9+2 x^8-x^7+2 x^6-x^5+x^4+x^2-x+1)(1+2x+3x^2+...)$

Hệ số $x^{22}$ trong đa thức trên là $1\times 1-2\times 2+5\times 3-2 \times 4+4 \times 5-2 \times 6+3 \times 7-8+3 \times 9-2 \times 10+3 \times 11-12+2\times 13-14+2 \times 15-16+2 \times 17-18+19+21-22+23=136$

Vậy số cách chia kẹo thoả mãn yêu cầu đề bài là $136$

P/s: cuối cùng cũng xong :))

 

__________________________________

Điểm bài: $d=10$

Điểm thưởng $d_t=5$

Điểm mở rộng $d_{mr}=0$

Điểm thảo luận $d_{tl}=0$

$S = \left \lfloor\frac{52 - \left (t_{lb} - t_{rd} \right )}{3} \right \rfloor+3\times d+d_{mr}+d_{t}+d_{tl}=\left \lfloor\frac{52 - 16}{3} \right \rfloor+3\times 10 +0+5+0=47$


Bài viết đã được chỉnh sửa nội dung bởi hxthanh: 13-07-2014 - 11:12
Chấm điểm


#6
tienthcsln

tienthcsln

    Hạ sĩ

  • Thành viên
  • 99 Bài viết

Đề bài của BTC

 

Đế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ể! 

Bài làm của MO 02

Xét dãy nhị phân có độ dài 31 kí tự, trong đó gồm 28 số 1 và 3 số 0. Khi đó dãy được chia làm 4 nhóm các số 1 liền nhau có dạng:

$\underbrace{11...1}0\underbrace{11...1}0\underbrace{11...1}0\underbrace{11...1}$

     (I)        (II)        (III)         (IV)

Gọi $a,b,c,d$ thứ tự là số phần tử của các nhóm (I), (II), (III), (IV) thì $a,b,c,d\in N$, $a+b+c+d=28$ và mỗi bộ $(a,b,c,d)$ ứng với duy nhất một cách chia 32 cái kẹo thành 4 phần mà mỗi phần có số kẹo tương ứng là $a+1,b+1,c+1,d+1$. Ngược lại, với mỗi cách chia thỏa mãn điều kiện bài toán ta cũng xây dựng được duy nhất một bộ $(a,b,c,d)$ như trên. Do đó, số cách chia thỏa mãn đề bài chính là số bộ $(a,b,c,d)$ như trên có thể lập được. Tuy nhiên, số bộ $(a,b,c,d)$ chính là số cách chọn ra 3 vị trí đặt số 0 trong 31 vị trí. Vì vậy, số cách chia thỏa mãn yêu cầu là: $C_{31}^{3}\textrm{ }$

Mở rộng:

Bằng cách như trên, ta có kết quả sau (Bài toán chia kẹo của Euler)

Số cách chia $n$ cái kẹo giống nhau thành $m$ phần ($1\leq m\leq n$) mà mỗi phần có ít nhất $k$ cái kẹo ($k\leq \left [ \frac{n}{m} \right ]$) là $C_{m-1+n-mk}^{m-1}\textrm{ }$

 

NX: Không nắm rõ đề bài

$S=d=2$


Bài viết đã được chỉnh sửa nội dung bởi hxthanh: 13-07-2014 - 11:13
Chấm điểm!


#7
Tru09

Tru09

    Thiếu úy

  • Thành viên
  • 625 Bài viết

Bài Làm :

Bài toán tương đương số nghiệm của hệ phương trình

$\left\{\begin{matrix} x+y+z+t =32 \\ x,y,z,t \in N* \\ x\neq y \neq z \neq t \end{matrix}\right.$

$\Leftrightarrow $$\left\{\begin{matrix} x-1+y-1+z-1+t-1 =28 \\ x,y,z,t \in N* \\ x\neq y \neq z \neq t \end{matrix}\right.$

$\Leftrightarrow $$\left\{\begin{matrix} a+b+c+d =28 \\ a,b,c,d :\text{Không âm} \\ a \neq b \neq c \neq d \end{matrix}\right.$

Ta xét phần bù .

( Ở đây ta xét tính thứ tự của a,b,c,d)

Số nghiệm không âm của phương trình a+b+c+d =28 là 4495

Trước hết ta tính số nghiệm không âm của phương trình a+b+c+d=28 với :$\begin{pmatrix} 31 \\ 3\end{pmatrix}$ =4495

 @~ > Với chỉ đúng 2 số trong 4 số bằng nhau .Không mất tính tổng quát giả sử 2 số đó là $a=b=k ( 0 \leq k \leq 14)$

$\Rightarrow c+d =28 -2k$

Để có đúng 2 số bằng nhau thì ta loại đi trường hợp $c=d  \neq 7$ ( xảy ra khi $0 \leq k \leq 14 ,k \neq 7$) ( có 14 trường hợp như vậy ) và Chỉ 1 trong 2 só $c,d =k$ ( chỉ xảy ra khi $0 \leq k\leq 9 và k \neq 7$) (có 18 trường hợp như vậy) và loại đi trường hợp $k=c=d$ ( chỉ xảy ra khi $ k=7$).( có 1 trường hợp như vậy )

Tóm lại ta phải loại đi 33 trường hợp .

Số nghiệm không âm của phương trình c+d =28 -2k với (0\leq c ,d \leq 28-2k , k chạy từ 0 đến 14) là $\sum (28-2k +1) =225$

Tóm lại với a=b thì số nghiệm không âm của phương trình $a+b+c+d =28$ là :$225 -33 =192$

Như vậy tổng cộng có 1152 nghiệm không âm của phương trình $a+b+c+d =28$ mà chỉ có đúng 2 số bằng nhau.

@~> Với chỉ đúng 3 số trong 4 số bằng nhau .Không mất tính tổng quát giả sử 3 số đó là $a=b=c=k (0 \leq k\leq9)$

$\Rightarrow d =28 -3k$

Để có đúng 3 số bằng nhau thì ta loại đi trường hợp $d= k$ nghĩa là $k =7$ .Vậy chỉ loại đi 1 trường hợp.

Vậy số nghiệm không âm  của phương trình $a+b+c+d=28$ có đúng 3 số bằng nhau là $9x4 =36.$

@~> Với đúng 4 số bằng nhau ( 1 trường hợp)

@~> Với đúng 2 cặp 2 số bằng nhau  ( 2 cặp này khác nhau ) Không mất tính tổng quát giả sử $a=b=k ,c=d =t (k \neq t)$

Khi đó $k+t =14$ khi đó có 14 trường hợp

Vậy số nghiệm không âm của phương trình $a+b+c+d =28$ với 2 cặp 2 số bằng nhau ( 2 cặp khác nhau) là $14x3 =42$

Tóm lại số nguyệm không âm có ít nhất 2 số bằng nhau của phương trình $a+b+c+d =28$ là $1152+36+42+1=1231$

Vậy số nghiệm không âm đôi 1 khác nhau của phương trình $a+b+c+d =28$ là $4495-1231=3264$

Do a,b,c,d ở trên ta xét có tính thứ tự 

Nên số cách chia kẹo vào các hôp không tính thứ tự là 3264 :24= 136 cách.

Tóm lại Số cách chia kẹp vào các hộp sao cho mỗi hộp có số lượng kẹo khác nhau là 136 cách chia .

 

____________________________

NX: Sai về cách trình bày ký hiệu đôi một khác nhau (- 1đ )

Điểm bài: $d=9$

Điểm thưởng $d_t=8$

Điểm mở rộng $d_{mr}=0$

Điểm thảo luận $d_{tl}=0$

$S = \left \lfloor\frac{52 - \left (t_{lb} - t_{rd} \right )}{3} \right \rfloor+3\times d+d_{mr}+d_{t}+d_{tl}=\left \lfloor\frac{52 - 42}{3} \right \rfloor+3\times 9 +0+8+0=38$


Bài viết đã được chỉnh sửa nội dung bởi hxthanh: 13-07-2014 - 11:23
Chấm điểm!


#8
E. Galois

E. Galois

    Chú lùn thứ 8

  • Quản lý Toán Phổ thông
  • 3861 Bài viết

Trận đấu đã kết thúc, mời các toán thủ nhận xét bài làm của nhau


1) Xem cách đăng bài tại đây
2) Học gõ công thức toán tại: http://diendantoanho...oạn-thảo-latex/
3) Xin đừng đặt tiêu đề gây nhiễu: "Một bài hay", "... đây", "giúp tớ với", "cần gấp", ...
4) Ghé thăm tôi tại 
http://Chúlùnthứ8.vn

5) Xin đừng hỏi bài hay nhờ tôi giải toán. Tôi cực gà.


#9
hxthanh

hxthanh

    Tín đồ $\sum$

  • Hiệp sỹ
  • 3915 Bài viết
Chưa thấy ai vào nhận xét trận này!
Trên tư cách là người ra đề trận này tôi có vài nhận xét sau:
- Trận này có đúng 3 toán thủ tham gia, có một sự trùng hợp là cả 3 lời giải đầu tiên đều SAI! Nhưng sau khi giải lại lần thứ 2 thì cả 2 toán thủ LNHTru09 đều giải đúng! :D
- Đa số các bạn đều không nắm rõ đề bài. Khi đề bài toán chỉ nêu ra là "có bao nhiêu cách chia thành 4 phần ..." thì có ai quan tâm đến phần nào là A phần nào là B v.v... Giống như câu hỏi "có bao nhiêu cách chia 8 học sinh thành 2 nhóm, mỗi nhóm  ít nhất 1 học sinh  (để chơi kéo co :luoi:)" Ở đây "học sinh" thì cần phân biệt chứ nhóm thì phân biệt làm gì?
- Cách làm của LNH tuy ra được kết quả đúng, nhưng thành thật mà nói là tính toán dễ nhầm lẫn, lâu hơn cả việc thống kê ra cho đủ 136 trường hợp. Khỏi cần nói cũng biết là cách làm này không thể mở rộng được bài toán!
- Cách làm của Tru09 tuy đúng ý tưởng, nhưng cũng hơi bị cụ thể hóa và rất khó khăn để áp dụng cho bài toán tổng quát.
- Nhận xét cuối cùng: Đây không phải là một bài toán dễ! :D

#10
hxthanh

hxthanh

    Tín đồ $\sum$

  • Hiệp sỹ
  • 3915 Bài viết

Đá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...



#11
hxthanh

hxthanh

    Tín đồ $\sum$

  • Hiệp sỹ
  • 3915 Bài viết

Đã chấm điểm xong! Mọi thắc mắc khiếu nại vui lòng liên hệ thầy Thế theo sdt: 1900...



#12
toanhoc2017

toanhoc2017

    Thiếu úy

  • Banned
  • 628 Bài viết
Mở rộng rất hay





Được gắn nhãn với một hoặc nhiều trong số những từ khóa sau: mo 2014

1 người đang xem chủ đề

0 thành viên, 1 khách, 0 thành viên ẩn danh