Đến nội dung

hxthanh

hxthanh

Đăng ký: 30-10-2010
Offline Đăng nhập: Riêng tư
****-

#743890 Trong trò chơi Minesweeper, một số trên ô vuông biểu thị số lượng mìn có chun...

Gửi bởi hxthanh trong Hôm nay, 03:25

\begin{array}{|c|c|c|c|c|c|} &&x&&y& \\
\hline \;&\;&\;&\;&\;&\; \\
\hline \;&3&\;&1&\;&2 \\
\hline \;&\;&\;&\;&\;&\; \\
\hline\end{array}
Xét hai cột $x$ và $y$ như trong bảng trên. Ta nói $x=1$ nghĩa là cột $x$ có chứa đúng $1$ quả mìn.
$\bullet\quad$Nếu $x=1\Rightarrow y=0$ có ${3\choose 1}=3$ cách đặt $1$ quả mìn ở cột $x$
Khi đó ${5\choose 2}=10$ cách đặt $2$ quả mìn quanh ô số $3$ và ${2\choose 2}=1$ cách đặt $2$ quả mìn quanh ô số $2$
$\Rightarrow 3\times 10\times 1=30$ cách
$\bullet\quad$Nếu $y=1\Rightarrow x=0$ có ${3\choose 1}=3$ cách đặt $1$ quả mìn ở cột $y$
Khi đó có ${2\choose 1}=2$ cách đặt $1$ quả mìn quanh ô số $2$ và ${5\choose 3}=10$ cách đặt $3$ quả mìn quanh ô số $3$
$\Rightarrow 3\times 2\times 10=60$ cách
$\bullet\quad$Nếu $x=0$ và $\; y=0$
Có ${5\choose 3}\times {2\choose 1}\times {2\choose 2}=20$ cách
Vậy có tất cả $30+60+20=\boxed{\mathbf{110}}$ cách đặt mìn thoả yêu cầu.
_____

Đã chơi đến đây thì chơi cho trót. Nếu mở được ô trống thì các ô trống tiếp theo sẽ tự động mở cho đến khi xuất hiện các ô khác 0. Lựa chọn mở theo cách logic - nghĩa là chỉ mở các ô không chắc chắn khi không còn ô nào khẳng định không có mìn. Thử tính xem bước đầu tiên phải mở ô nào để khả năng thắng là cao nhất?



#743828 $L(n)$ là số cách phân hoạch lẻ, $C(n)$ là số cách phân h...

Gửi bởi hxthanh trong 25-02-2024 - 08:37

Cho một số nguyên dương $n$ ta định nghĩa $L(n)$ và $C(n)$ như sau:
$L(n)$ là số cách phân hoạch $n$ thành tổng một số lẻ các số nguyên dương phân biệt.
$C(n)$ là số cách phân hoạch $n$ thành tổng một số chẵn các số nguyên dương phân biệt.
Ví dụ ta có thể viết $7$ thành $7$ ; $6+1$ ; $5+2$ ; $4+3$ ; $4+2+1$. Khi đó có $L(n) = 2$ và $C(n) = 3$.
Chứng minh rằng với mọi $n$ nguyên dương ta đều có:
$$\left | L(n) - C(n) \right | \leq 1$$

Lập hàm sinh cho số cách phân hoạch $n$ thành tổng các số nguyên dương phân biệt:
$G(x)=(1+x)(1+x^2)…(1+x^n)…$
Ở đây ta có $[x^n]G(x)=L(n)+C(n)$
Nhưng để chứng minh $L(n)$ và $C(n)$ hơn kém nhau không quá $1$ thì chưa biết phải làm thế nào :(
Theo như những gì dãy $C(n)=A067661$ cho thấy
thì hàm sinh cho $C(n)$ là
$E(x)=\dfrac 12\left(\prod_{k\ge 1}(1+x^k)+\prod_{k\ge 1}(1-x^k)\right)$
(Điều này làm mình thấy hoang mang không hiểu được! :( )
Như vậy $G(x)-E(x)=O(x)$ là hàm sinh cho $L(n)$
$O(x)=\dfrac 12\left(\prod_{k\ge 1}(1+x^k)-\prod_{k\ge 1}(1-x^k)\right)$
Bài toán được giải quyết hoàn toàn nếu ta chỉ ra được
$\left|[x^n]\right|: \prod_{k\ge 1}(1-x^k)\le 1 $
Trong tài liệu này từ cuối trang 6 đến trang 9 có nhắc đến kết luận trên.
Tham khảo “Số ngũ giác - Euler"


#743793 Từ lưới ô vuông kích thước 29x29, chúng ta cắt ra 99 hình vuông 2x2. CMR vẫn...

Gửi bởi hxthanh trong 23-02-2024 - 15:54

Ta đặt tâm ô vuông góc trái dưới cùng làm gốc toạ độ $(0,0)$
Tô màu các ô toạ độ $(3x+1,3y+1)$
Với $0\le x,y\le 9$. Tất cả có $10\times 10$ ô được tô màu.
Sau khi cắt ra $99$ hình vuông $2\times 2$ thì ít nhất còn một ô đã tô màu chưa bị cắt. Khi đó hình vuông $3\times 3$ có tâm là ô vuông nói trên sẽ cắt được một hình vuông $2\times 2$ nữa.


#743785 Hãy tính xem có tất cả bao nhiêu số ''đẹp'' dạng $\...

Gửi bởi hxthanh trong 22-02-2024 - 21:47

Một số $\overline{abcde}$ được gọi là số ''đẹp'' nếu $a< b >c< d >e$ (Chẳng hạn $15243$ là số ''đẹp''). Hãy tính xem có tất cả bao nhiêu số ''đẹp'' dạng $\overline{abcde}$?

Lập tổng một cách trật tự ta có:
\begin{align*}
S&=\sum_{a=1}^8\sum_{b=a+1}^9\sum_{c=0}^{b-1}\sum_{d=c+1}^9\sum_{e=0}^{d-1} 1 \\ &= \sum_{a=1}^8\sum_{b=a+1}^9\sum_{c=0}^{b-1}\sum_{d=c+1}^9 {d \choose 1} \\
&= \sum_{a=1}^8\sum_{b=a+1}^9\sum_{c=0}^{b-1} \left[{10\choose 2}-{c+1\choose 2}\right] \\ &= \sum_{a=1}^8\sum_{b=a+1}^9 \left[{10\choose 2}{b\choose 1}-{b+1\choose 3}\right] \\
&=\sum_{a=1}^8\left[{10\choose 2}^2-{10\choose 2}{a+1\choose 2}-{11\choose 4}+{a+2\choose 4}\right]\\
&= 8{10\choose 2}^2-{10\choose 2}{10\choose 3}-8{11\choose 4} +{11\choose 5}\\ &=8622
\end{align*}


#743775 Số $k-$giác của $n-$giác lồi

Gửi bởi hxthanh trong 22-02-2024 - 13:00

Thực chất \eqref{s1} hoàn toàn tương tự như biểu thức (4) post #4
Và việc chứng minh tương tự kết quả của biểu thức (10) post #5. Ta có:
$$S(n,k)=\dfrac{n}{n-k} {n-k\choose k}$$


#743773 số nghiệm nguyên dương của phương trình $a+b+c=n$

Gửi bởi hxthanh trong 22-02-2024 - 01:14

1/ Lập hàm sinh $f(x)$ mà hệ số của $x^n$ là số nghiệm cần tìm. Ta có :
$$f(x)=\sum_{{a,b,c\ge 1\atop a\ge b \ge c }\atop a < b+c}x^{a+b+c}$$
Đặt :
$\begin {align*}
c=y_3+1 \quad\quad y_3\ge 0\\
b=y_2+c \quad\quad y_2\ge 0\\
a=y_1+b\quad\quad y_3\ge 0
\end {align*}$
Do $a<b+c$ nên :
$\begin {align*}
y_1+y_2+y_3+1&<(y_2+y_3+1)+(y_3+1)\\
y_1&<y_3+1\\
y_1&\leq y_3\\
a+b+c&=(y_1+y_2+y_3+1)+(y_2+y_3+1)+(y_3+1)\\
&=y_1+2y_2+3y_3+3\\
\Longrightarrow f(x)=\sum_{y_1,y_2,y_3\geq 0\atop y_1\leq y_3}x^{y_1+2y_2+3y_3+3}
\end {align*}$
Từ $y_1\leq y_3:$
$\begin {align*}
y_3&=t_3+y_1\quad\quad t_3\geq0\\
y_2&=t_2\quad\quad\quad t_2\geq0\\
y_1&=t_1\quad\quad\quad t_1\geq0\\
\Longrightarrow y_1+2y_2+3y_3+3&=t_1+2t_2+3(t_3+t_1)+3\\
&=4t_1+2t_2+3t_3+3\\
\Longrightarrow f(x)&=x^3\sum_{t_1,t_2,t_3\geq0}x^{4t_1+2t_2+3t_3}\\
&=x^3\sum_{t_2\geq0}x^{2t_2}\sum_{t_3\geq0}x^{3t_3}\sum_{t_1\geq0}x^{4t_1}\\
&=\boldsymbol {\frac {x^3}{(1-x^2)(1-x^3)(1-x^4)}}
\end{align*}$
Tách phân thức :
$\begin {align*}
\frac{1}{(1-x^2)(1-x^3)(1-x^4)}&=\frac{7}{32}\cdot \frac{1}{1+x}+\frac{1}{16}\cdot \frac{1}{(1+x)^2}\\
&+\frac{59}{288}\cdot\frac{1}{1-x}+\frac{1}{8}\cdot\frac{1}{(1-x)^2}+\frac{1}{24}\cdot\frac{1}{(1-x)^3}\\
&+\left(\frac{1}{8}-\frac{x}{8}\right )\cdot\frac{1}{1+x^2}+\left(\frac{2}{9}+\frac{x}{9}\right )\cdot\frac{1}{1+x+x^2}\\
\Longrightarrow \left [ x^n \right ]f(x)&=\left [ x^{n-3} \right ]\left( {\frac{7}{32}\sum_{k\geq0}(-1)^k x^k+\frac {1}{16}\sum_{k\geq0}(k+1)(-1)^kx^k} \right.\\
&+\frac {59}{288}\sum_{k\geq0}x^k+\frac {1}{8}\sum_{k\geq0}(k+1)x^k+\frac {1}{24}\sum_{k\geq0}\binom {k+2}{2}x^k\\
&\left. {+\left ( \frac {1}{8}-\frac{x}{8} \right )\sum_{k\geq0}(-1)^kx^{2k}+\left ( \frac {2}{9}+\frac {x}{9} \right)(1-x)\sum_{k\geq0}x^{3k}}\right)
\end {align*}$

Bỗng nhiên nghĩ đến chỗ này

$4t_1+2t_2+3t_3+3=n$
$\bullet\quad$ Nếu $n$ chẵn $n=2m$ thì $t_3$ là số lẻ
Đặt $t_3=2u+1;\quad(u\ge 0)$
$4t_1+2t_2+6u+6=2m$ hay
$t_2+2t_1+3u+3=m$
Hàm sinh cho pt này là $\dfrac{x^3}{(1-x)(1-x^2)(1-x^3)}$
Cái này chính là $f(m,3)=\left\lfloor\dfrac{m^2+3}{12}\right\rfloor$
$\bullet\quad$ Nếu $n$ lẻ $n=2m+1$ thì $t_3$ là số chẵn
Đặt $t_3=2v;\quad(v\ge 0)$
$4t_1+2t_2+6v+3=2m+1$ hay
$t_2+2t_1+3v+3=m+2$
Cái này chính là $f(m+2,3)=\left\lfloor\dfrac{(m+2)^2+3}{12}\right\rfloor$
Đến đây ta có thể viết kết quả của bài toán bằng công thức:
$$S_n=\left\lfloor\dfrac{\left(2n-3\left\lfloor\frac n2\right\rfloor\right)^2+3}{12}\right\rfloor$$


#743740 có bao nhiêu cách trả tiền khi mua một món hàng giá 127 đồng?

Gửi bởi hxthanh trong 20-02-2024 - 09:33

Giải lại bài toán này bằng… tay!
Xét phương trình nghiệm nguyên không âm:
$a+5b+10c+20d+50e+100f=127$
Đặt $a=5g+2$, ta có pt tương đương
$g+b+2c+4d+10e+20f=25$
Ứng với mỗi bộ $(f,e,d,c)$ thì
$(b,g)$ có $(26-20f-10e-4d-2c)$ nghiệm
Do đó số nghiệm cần tính là
\begin{align*} &=\sum_{f=0}^1\sum_{e=0}^{\left\lfloor\frac{5-4f}2 \right\rfloor}\sum_{d=0}^{\left\lfloor\frac{25-20f-10e}4 \right\rfloor}\sum_{c=0}^{12-10f-5e-2d} (26-20f-10e-4d-2c) \\
&=\sum_{f=0}^1\sum_{e=0}^{\left\lfloor\frac{5-4f}2 \right\rfloor}\sum_{d=0}^{\left\lfloor\frac{25-20f-10e}4 \right\rfloor} 2{14-10f-5e-2d\choose 2}
\end{align*}
$\bullet\;$ TH $f=0;\;e=0$ $\Rightarrow \sum_{d=0}^6 (14-2d)(13-2d)=504$
$\bullet\;$ TH $f=0;\;e=1$ $\Rightarrow \sum_{d=0}^3 (9-2d)(8-2d)=140$
$\bullet\;$ TH $f=0;\;e=2$ $\Rightarrow \sum_{d=0}^1 (4-2d)(3-2d)=14$
$\bullet\;$ TH $f=1\Rightarrow e=0$ $\Rightarrow \sum_{d=0}^1 (4-2d)(3-2d)=14$

Tổng cộng pt có: $504+140+14+14=\boxed{\large 672}$ nghiệm.


#743738 Hỏi anh A có bao nhiêu cách trả tiền món hàng giá 200 đồng với đúng 50 tờ tiề...

Gửi bởi hxthanh trong 20-02-2024 - 02:02

Cách làm tương tự để đếm số nghiệm nguyên không âm của phương trình:
$5x+10y+25z+t=200$
Đặt $t=5p$ (Do cả hai vế đều là bội của 5)
Ta có: $(x+p)+2y+5z=40$
Với mỗi giá trị $y,z$ thì $x+p=40-2y-5z$ có $(40-2y-5z)+1$ nghiệm.
Vậy nên số nghiệm của pt đã cho là:
$\sum_{y=0}^{\left\lfloor\frac{40}2\right\rfloor}\sum_{z=0}^{\left\lfloor\frac{40-2y}5\right\rfloor}(41-2y-5z)=1463$
Hay “ít” phức tạp hơn là:
$\sum_{z=0}^{\left\lfloor\frac{40}5\right\rfloor}\sum_{y=0}^{\left\lfloor\frac{40-5z}2\right\rfloor}(41-2y-5z)=1463$


#743737 Hỏi anh A có bao nhiêu cách trả tiền món hàng giá 200 đồng với đúng 50 tờ tiề...

Gửi bởi hxthanh trong 20-02-2024 - 01:15

Xét phương trình $4x+9y+24z=150$.
Trong không gian $Oxyz$ lấy các điểm $A\left ( 0,0,\frac{25}{4} \right )$, $B\left ( 0,\frac{50}{3},0 \right )$ và $C\left ( \frac{75}{2},0,0 \right )$
Hình chiếu của $\Delta ABC$ lên mặt phẳng $Oyz$ là $\Delta ABO$.
Đáp án bài toán chính là số điểm nguyên thỏa mãn $y=4k+2$ ($k\in \mathbb{N}$) của $\Delta ABO$ và bằng
$\sum_{k=0}^{\left \lfloor \frac{\frac{50}{3}-2}{4} \right \rfloor}\left ( \left \lfloor \frac{50-3(4k+2)}{8} \right \rfloor+1 \right )=16$.

Liên hệ hình học giải tích của chanhquocnghiem rất thú vị!
Mình xin đưa ra cách làm để các bạn khác đọc dễ hiểu hơn chút:
Với phương trình nghiệm nguyên không âm dạng
$ax+by+cz=n$ Trong đó $a,b,c,n$ là các số cho trước. Nếu chỉ để đếm số nghiệm thôi thì ta đổi biến thoả mái (phù hợp đk) sao cho đưa pt về dạng $x’+py’+qz’=m$
(Có một biến với hệ số 1).
Khi đó ta có $\begin{cases} 0\le y' \le \left\lfloor \frac mp \right\rfloor \\ 0\le z’ \le \left\lfloor \frac{m-py’}q \right\rfloor \end{cases} $
Số nghiệm sẽ là tổng $ \sum_{y’=0}^{\left\lfloor \frac{m}{p} \right\rfloor} \left( \left\lfloor \dfrac{m-py’}{q} \right\rfloor+1\right)$
Hoặc là: $ \begin{cases} 0\le z' \le \left\lfloor \frac {m}{q} \right\rfloor \\ 0\le y’ \le \left\lfloor \frac{m-qz’}{p} \right\rfloor \end{cases} $
Số nghiệm sẽ là tổng $\sum_{z’=0}^{\left\lfloor \frac mq \right\rfloor} \left(\left\lfloor \dfrac{m-qz’}p \right\rfloor+1\right) $
—————
Cụ thể $4x+9y+24z=150$
Đặt $y=4k+2 \Rightarrow x+9k+6z=33$
Vậy số nghiệm pt là:
$\sum_{k=0}^{\left\lfloor \frac{33}9 \right\rfloor} \left(\left\lfloor \dfrac{33-9k}6 \right\rfloor+1\right)=\sum_{z=0}^{\left\lfloor \frac {33}6 \right\rfloor} \left(\left\lfloor \dfrac{33-6z}9 \right\rfloor+1\right)=16$


#743735 Đếm số cách lát nền nhà hình vuông $n\times n;\;$ với...

Gửi bởi hxthanh trong 19-02-2024 - 23:10

Một nền nhà hình vuông kích thước $n\times n$ ô vuông đơn vị với $\quad n\equiv \pm 1\!\!\!\pmod 6$. Có một cây cột kích thước $1$ ô vuông đơn vị ở tâm nền nhà. Có $\dfrac{n^2-1}{3}$ viên gạch hình chữ “L” được tạo bởi $3$ ô vuông đơn vị.
Hãy tính số cách lát kín nền nhà đã cho bằng những viên gạch nói trên.

Để giảm độ khó, mời các bạn giải bài toán trên với $n=5$


#743734 Hỏi anh A có bao nhiêu cách trả tiền món hàng giá 200 đồng với đúng 50 tờ tiề...

Gửi bởi hxthanh trong 19-02-2024 - 22:52

Giải :
Để thuận tiện cho việc trình bày, ta xếp lại và xét hệ phương trình sau:
$\left\{\begin{matrix}
z_1+5z_2+10z_3+25z_4&=\;200 \\
z_1+z_2+z_3+z_4&=\;50 && (1)
\end{matrix}\right.$
Lấy phương trình thứ nhất trong (1) trừ phương trình thứ hai vế với vế ta được :
$4z_2+9z_3+24z_4=\;150 $ (2)

Để ý chỗ này phải có $z_3\equiv 2\!\!\!\pmod 4$
Từ đó xét 4 trường hợp $z_3\in\{2,6,10,14\}$
Nhanh và ngắn hơn xíu!


#743732 Hỏi anh A có bao nhiêu cách trả tiền món hàng giá 200 đồng với đúng 50 tờ tiề...

Gửi bởi hxthanh trong 19-02-2024 - 22:34

Post xong mới thấy Nobodyv3 đã giải phía trên rồi :( . Hàm sinh hai biến mình cũng xét tới nhưng triển khai ra đến $y^{50}$ xem ra bất khả thi, chí ít là với “siêu máy tính” wolframalpha.


#743731 Hỏi anh A có bao nhiêu cách trả tiền món hàng giá 200 đồng với đúng 50 tờ tiề...

Gửi bởi hxthanh trong 19-02-2024 - 22:28

Ta cần tìm số nghiệm nguyên không âm của hệ phương trình :
$\left\{\begin{matrix}
5z_1+10z_2+25z_3+z_4&=\;200 \\
z_1+z_2+z_3+z_4&=\;50 &
\end{matrix}\right.$

Tính bằng tay, thì hệ trên có $16$ nghiệm $(z_1,z_2,z_3,z_4)$
\begin{array}{|cccc|cccc|cccc|cccc|}
\hline 33&2&0&15&27&2&1&20&21&2&2&25&15&2&3&30\\
\hline 9&2&4&35&3&2&5&40&24&6&0&20&18&6&1&25\\
\hline 12&6&2&30&6&6&3&35&0&6&4&40&15&10&0&25\\
\hline 9&10&1&30&3&10&2&35&6&14&0&30&0&14&1&35\\
\hline
\end{array}
tương ứng với $z_2\equiv 2\!\!\!\pmod 4\Rightarrow z_2\in\{2,6,10,14\}$


#743708 Hỏi anh A có bao nhiêu cách trả tiền món hàng giá 200 đồng với đúng 50 tờ tiề...

Gửi bởi hxthanh trong 19-02-2024 - 09:00

À quên

Ta cần tìm số nghiệm nguyên không âm của hệ phương trình :
$\left\{\begin{matrix}
5z_1+10z_2+25z_3+z_4&=\;200 \\
z_1+z_2+z_3+z_4&=\;50 &
\end{matrix}\right.$

quên mất :)) cái dữ liệu 50


#743706 Hỏi anh A có bao nhiêu cách trả tiền món hàng giá 200 đồng với đúng 50 tờ tiề...

Gửi bởi hxthanh trong 19-02-2024 - 08:28

Giải phương trình nghiệm nguyên không âm
$ 5z_1+10z_2+25z_3+z_4=200 $
Lời giải
\begin{align*}[x^{200}]& \dfrac 1{(1-x)(1-x^5)(1-x^{10})(1-x^{25})}\\ &=[x^{225}]\dfrac{x^{25}}{(1-x)(1-x^{25})}\cdot
\dfrac{1}{(1-x^5)(1-x^{10})} \\ &=[x^{225}]\sum_{k\ge 0} \left\lfloor\dfrac{k+2}2 \right\rfloor x^{5k}\sum_{j\ge 0} \left\lfloor\dfrac j{25} \right\rfloor x^j \\ &=\sum_{k=0}^{45} \left\lfloor\dfrac{k+2}2 \right\rfloor\cdot \left\lfloor\dfrac{225-5k}{25} \right\rfloor \\ &=1463
\end{align*}

Ở đây có hai thứ cần bạn chứng minh:
\begin{equation}\label{s1} \sum_{n=0}^\infty \left\lfloor\dfrac nm \right\rfloor x^n=\dfrac{x^m}{(1-x)(1-x^m)} \end{equation}
\begin{equation}\label{s2} \sum_{n=0}^\infty \left\lfloor\dfrac {n+p}p \right\rfloor x^{mn}=\dfrac1{(1-x^m)(1-x^{pm})} \end{equation}