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

[Nobodyv3]

Có bao nhiêu cách đổi 1 tờ tiền mệnh giá  n đồng thành các tờ tiền mệnh giá  1, 2, hoặc 3 đồng.

[chanhquocnghiem]

Có bao nhiêu cách đổi 1 tờ tiền mệnh giá  n đồng thành các tờ tiền mệnh giá  1, 2, hoặc 3 đồng.

Gọi số cách cần tìm là $s(n)$.

$s(n)$ cũng chính là số bộ nghiệm nguyên không âm của phương trình $x+2y+3z=n$.

Trong không gian $Oxyz$ lấy các điểm $A\left ( 0,\frac{n}{2},0 \right ),B\left ( 0,0,\frac{n}{3} \right ),C(n,0,0)$.

Hình chiếu của $\Delta ABC$ trên $Oyz$ là $\Delta ABO$. Và $s(n)$ chính là số điểm nguyên của $\Delta ABO$ này

$(AB):y=\frac{n-3z}{2}\Rightarrow s(n)=\sum_{z=0}^{\left \lfloor \frac{n}{3} \right \rfloor}\left \lfloor \frac{n-3z}{2}+1 \right \rfloor$

Đặt $n=6m+p\ (0\leqslant p\leqslant 5)$.

$\textbf{TH1}$ : $(0\leqslant p\leqslant 2)$

$s(n)=\sum_{z=0}^{2m}\left \lfloor 3m+1-2z+\frac{z+p}{2} \right \rfloor=(3m+1)(2m+1)-2m(2m+1)+\sum_{z=0}^{2m}\left \lfloor \frac{z+p}{2} \right \rfloor=$

   $=2m^2+3m+1+m^2+pm+\left \lfloor \frac{p}{2} \right \rfloor=3m^2+(p+3)m+\left \lfloor \frac{p}{2} \right \rfloor+1$

$\textbf{TH2}$ : $(3\leqslant p\leqslant 5)$

$s(n)=\sum_{z=0}^{2m+1}\left \lfloor 3m+1-2z+\frac{z+p}{2} \right \rfloor=(3m+1)(2m+2)-2(m+1)(2m+1)+\sum_{z=0}^{2m+1}\left \lfloor \frac{z+p}{2} \right \rfloor=$

   $=2m^2+2m+m^2+(p+1)m+p=3m^2+(p+3)m+p$

Thống nhất kết quả trong cả $2$ trường hợp, ta có :

$s(n)=3\left \lfloor \frac{n}{6} \right \rfloor^2+(p+3)\left \lfloor \frac{n}{6} \right \rfloor+\left \lfloor \frac{p}{2} \right \rfloor+\sum_{k=1}^{2}\left \lfloor \frac{p}{2k+1} \right \rfloor+1$

(trong đó $p=n-6\left \lfloor \frac{n}{6} \right \rfloor$)

[Nobodyv3]

Nhìn vào là biết bài giải có bản quyền của anh @chanhquocnghiem.
Cảm ơn anh.
===========
Đây, lời giải của em.

Gọi $a_n$ là số cách đổi tiền thỏa yêu cầu, ta có hàm sinh cho số cách đổi tiền :$$\begin {align*}
f(x)&=\frac {1}{(1-x)(1-x^2)(1-x^3)}\\
&=\frac{ \frac{17}{72}}{1-x}+\frac{\frac{1}{4}}{\left(1-x\right)^{2}}\\
&+\frac{ \frac{1}{6}}{\left(1-x\right)^{3}}+\frac{\frac{1}{8}}{x + 1}+\frac{\frac{x}{9} + \frac{2}{9}}{x^{2} + x + 1}\\
&=\frac{17}{72}\sum_{k\geq 0}x^k+\frac{1}{4}\sum_{k\geq0}\binom{k+1}{1}x^k\\
&+\frac{1}{6}\sum_{k\geq0}\binom{k+2}{2}x^k+\frac{1}{8}\sum_{k\geq0}(-1)^kx^k+\frac{1}{9}(x+2)\frac {(1-x)}{(1-x^3)}\\
\text{Đặt }r(x)&=\frac{1}{9}(x+2)\frac {(1-x)}{(1-x^3)}=\frac{1}{9}\frac {(-x^2-x+2)}{(1-x^3)}\\
&=\frac {1}{9}(-x^2-x+2)\sum_{k\geq0}x^{3k}\\
\Rightarrow [x^n]r(x)&=\begin {cases}
\quad \frac {2}{9}&&\text{nếu }3\mid n\\
-\frac {1}{9}&&\text{nếu }3\nmid n
\end{cases}
\end{align*}$$Vậy ta có :$$\begin{align*}
[x^n]f(x)=\frac{1}{8} (-1)^n+\frac {47}{72}+\frac {n}{2}+\frac {n^2}{12}+[x^n]r(x)
\end{align*}$$ Cuối cùng, số cách đổi tiền thỏa yêu cầu là :$$\color{blue}a_n=\begin{cases}
\frac{1}{8} (-1)^n+\frac {47}{72}+\frac {n}{2}+\frac {n^2}{12}+\frac {2}{9}&&\text{nếu }3\mid n\\
\frac{1}{8} (-1)^n+\frac {47}{72}+\frac {n}{2}+\frac {n^2}{12}-\frac {1}{9}&&\text{nếu }3\nmid n
\end{cases} $$

Bài viết đã được chỉnh sửa nội dung bởi Nobodyv3: 18-07-2023 - 00:16