Đến nội dung

Hình ảnh

Số nghiệm nguyên $x_{1}+x_{2}+x_{3}+x_{4}=20$ với $0\leq x_i<8$.

- - - - -

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

#1
Baoriven

Baoriven

    Thượng úy

  • Điều hành viên OLYMPIC
  • 1422 Bài viết

Tìm số nghiệm nguyên của phương trình sau $$\mathrm{x}_{1}+\mathrm{x}_{2}+\mathrm{x}_{3}+\mathrm{x}_{4}=20$$ với $0 \leq \mathrm{x}_{\mathrm{i}}<8, \forall \mathrm{i} \in\{1,2,3,4\}$.

 

Ghi chú: Bài có thể tiếp cận bằng nhiều cách (hàm sinh, nguyên lý bù trừ, ...) 


Bài viết đã được chỉnh sửa nội dung bởi Baoriven: 16-06-2022 - 16:04

$$\mathbf{\text{Every saint has a past, and every sinner has a future}}.$$


#2
Nobodyv3

Nobodyv3

    Generating Functions Faithful

  • Thành viên
  • 935 Bài viết
Tiến thêm 1 bước nữa (lập công thức tổng quát):
*Tính số nghiệm của phương trình $$ x_{1}+x_{2}+...+x_{k}=n$$
với $0\leq x_{i}\leq r$ và $
i\in \left \{ 1,2,...,k \right \} $ .

Bài viết đã được chỉnh sửa nội dung bởi Nobodyv3: 16-06-2022 - 22:13

===========
Thà rót cho ta..... trăm nghìn chung... rượu độc ...miễn sao đừng bắt em làm toán!..hu hu...

#3
Nobodyv3

Nobodyv3

    Generating Functions Faithful

  • Thành viên
  • 935 Bài viết
...thêm vào series tổng quát hóa:
Tính số nghiệm nguyên của phương trình
$$\left |x_{1}  \right |+\left |x_{2}  \right |+...+\left |x_{k}  \right |= n $$
===========
Thà rót cho ta..... trăm nghìn chung... rượu độc ...miễn sao đừng bắt em làm toán!..hu hu...

#4
Nobodyv3

Nobodyv3

    Generating Functions Faithful

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

...thêm vào series tổng quát hóa:
Tính số nghiệm nguyên của phương trình
$$\left |x_{1} \right |+\left |x_{2} \right |+...+\left |x_{k} \right |= n $$

Theo kết quả của bài toán chia kẹo Euler ta có $\binom{k}{i}\binom{n-1}{k-1}$ nghiệm trong đó có $i$ số nguyên dương và các số còn lại là các số $0$. Ngoài ra, mỗi nghiệm nguyên khác 0 có 2 giá trị trái dấu do đó số nghiệm nguyên của phương trình là $\sum_{i=1}^{min(n,k)}2^{i}\binom{k}{i}\binom{n-1}{k-1}$

Bài viết đã được chỉnh sửa nội dung bởi Nobodyv3: 18-06-2022 - 22:35

===========
Thà rót cho ta..... trăm nghìn chung... rượu độc ...miễn sao đừng bắt em làm toán!..hu hu...

#5
Nobodyv3

Nobodyv3

    Generating Functions Faithful

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

Tiến thêm 1 bước nữa (lập công thức tổng quát):
*Tính số nghiệm của phương trình $$ x_{1}+x_{2}+...+x_{k}=n$$
với $0\leq x_{i}\leq r$ và $
i\in \left \{ 1,2,...,k \right \} $ .

Ta có :
$f(z)=\sum_{x_{1}=0}^{r}\sum_{x_{2}=0}^{r}...\sum_{x_{k}=0}^{r}z^{x_{1}+x_{2}+...x_{k}}$
Gọi $N$ là số nghiệm thì :
$\Rightarrow N=\left [ z^{n} \right ]f(z)=\sum_{x_{1}=0}^{r}\sum_{x_{2}=0}^{r}...\sum_{x_{k}=0}^{r}\overbrace{\left [ z^{n} \right ]z^{x_{1}+x_{2}+...x_{k}}}^{A}$
Nhận thấy $A=1$ khi $x_{1}+x_{2}+...x_{k}=n$ và ngược lại thì $A=0$. Ta có :
$N=\left [ z^{n} \right ]\left ( \sum_{x=0}^{r} z^x\right )^{k}=\left [ z^{n} \right ]\left ( \frac{1-z^{r+1}}{1-z} \right )^{k}=\left [ z^{n} \right ]\left [ \sum_{i=0}^{k}\binom{k}{i} \left ( -z^{r+1} \right )^i\right ]\left [ \sum_{j=0}^{\infty } \binom{-k}{j}\left ( -z \right )^{j}\right ]=\\
\left [ z^{n} \right ]\sum_{i=0}^{k}\left ( -1 \right )^{i}\binom{k}{i}\sum_{j=0}^{\infty }\left [ \left ( -1 \right )^{j}\binom{k+j-1}{j}\left ( -1 \right )^{j} \right ]z^{\left ( r+1 \right )i+j}=\\
\sum_{i=0}^{k}\left ( -1 \right )^{i}\binom{k}{i}\sum_{j=0}^{\infty }\binom{k+j-1}{k-1}\left [\left [n= \left ( r+1 \right )i+j \right ] \right ]$
Ký hiệu $\left [ \left [ P \right ] \right ]=1$ nếu P đúng,ngược lại bằng 0. Tiếp tục :
$\sum_{i=0}^{k}\left (-1\right )^{i}\binom{k}{i}\sum_{j=0}^{\infty }\binom{k+j-1}{k-1}\left [\left [j=n- \left ( r+1 \right )i \right ] \right ]=\\
\sum_{i=0}^{k}\left ( -1 \right )^{i}\binom{k}{i}\binom{k+n-\left ( r+1 \right )i-1}{k-1}\left [\left [n-\left ( r+1 \right )i\geq 0 \right ] \right ]=\\
\sum_{i=0}^{k}\left ( -1 \right )^{i}\binom{k}{i}\binom{k+n-\left(r+1\right)i-1}{k-1}\left [\left [i\leq \frac{n}{r+1} \right ] \right ]\\
\Rightarrow N= \sum_{i=0}^{m}\left ( -1 \right )^{i}\binom{k}{i}\binom{k+n-\left (r+1\right )i-1}{k-1}$ với $\text{m=min}\left (k,\left \lfloor \frac{n}{r+1} \right \rfloor \right )$
Áp dụng vào bài của anh Baoriven với k=4, r=7, n=20 thì số nghiệm là:
$\binom{23}{3}-4\binom{15}{3}+6\binom{7}{3}=\boxed {161}$

Bài viết đã được chỉnh sửa nội dung bởi Nobodyv3: 19-06-2022 - 18:35

===========
Thà rót cho ta..... trăm nghìn chung... rượu độc ...miễn sao đừng bắt em làm toán!..hu hu...

#6
Baoriven

Baoriven

    Thượng úy

  • Điều hành viên OLYMPIC
  • 1422 Bài viết

Có thể dùng hàm sinh nhé.

Nhân tử đa thức cho $x_i$ là: $1+t+\dots + t^7$. 

Ta được hàm sinh:

$$ G(x) = (1+t+\dots + t^7)^4 = [(1+x)(1+x^2)(1+x^4)]^4. $$

Mục tiêu là tìm hệ số của $x^{20}$ trong hàm sinh.

Có thể làm hai cách: $G(x) = \dfrac{(1-x^8)^4}{(1-x)^4}$ hoặc tìm thẳng từ hàm sinh ở trên luôn.

 

Kết quả là $\boxed{161}$ đúng nhá! :D 


$$\mathbf{\text{Every saint has a past, and every sinner has a future}}.$$





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

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