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.
#1
Đã gửi 16-07-2023 - 22:06
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...
#2
Đã gửi 17-07-2023 - 22:43
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$)
- DOTOANNANG và Nobodyv3 thích
...
Ðêm nay tiễn đưa
Giây phút cuối vẫn còn tay ấm tay
Mai sẽ thấm cơn lạnh khi gió lay
Và những lúc mưa gọi thương nhớ đầy ...
#3
Đã gửi 17-07-2023 - 23:16
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
- chanhquocnghiem và DOTOANNANG thích
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...
1 người đang xem chủ đề
0 thành viên, 1 khách, 0 thành viên ẩn danh