Cosette

Cho 2n điểm trên đường tròn. Tính số cách nối 2n điểm đó thành n dây cung đôi một không cắt nhau (bài này dùng Hàm Sinh bạn nào biết chỉ mình với)

Bài toán này yc tìm số Catalan $C_{n}$.

Về cách cm: có thể dùng quan hệ truy hồi hoặc dùng ff hàm sinh...bạn có thể tham khảo sách giáo khoa, tài liệu... liên quan đến số Catalan.

Trở về bài toán trên, nếu mình nhớ không nhầm thì đáp án là $C_{n}=\frac{1}{n+1}.C_{2n}^{n}$

Có bao nhiêu cách bỏ 35 viên bi giống nhau vào 5 hộp khác nhau sao cho: mỗi hộp 1 và 2 không có 0, 1, 2, 7, 8, 9 hoặc 10 bi; hộp 3 ít nhất 2 và nhiều nhất 9 bi; và hộp 4 và 5 không giới hạn bi.

Em xin giải bằng pp hàm sinh.

Theo đề bài, ta lập được hàm sinh cho các hộp:

- Hộp 1 và 2:  

$x^{3}+x^{4}+x^{5}+x^{6}+x^{11}+x^{12}+x^{13}+...=x^{3}\left ( 1+x+x^{2}+x^{3} \right )+x^{11}\left ( 1+x+x^{2}+... \right )=$

$=x^{3}\frac{1-x^{4}}{1-x}+\frac{x^{11}}{1-x}=x^{3}\frac{\left ( 1-x^{^{4}}+x^{^{8}} \right )}{1-x}$

- Hộp 3:

$x^{2}+x^{3}+x^{4}+....+x^{9}=x^{2}\left ( 1+x+x^{2}+....+x^{7}\right )=x^{2}{\left( \frac{1-x^{8}}{1-x} \right )}$

- Hộp 4 và 5:

$1+x+x^{2}+x^{3}+...=\frac{1}{1-x}$

Vậy ta có:

$G(x)=\left ( x^{3}\frac{\left ( 1-x^{4}+x^{8} \right )}{1-x} \right )^{2}.x^{2}\frac{1-x^{8}}{1-x}.\left ( \frac{1}{1-x} \right )^{2}=x^{8}\left ( 1-x^{4}+x^{^{8}} \right )^{2}\left ( 1-x^{^{8}} \right )\left ( 1-x \right )^{-5}$

Số hạng $x^{35}$ là:

$x^{8}C_{31}^{27}x^{27}-2x^{12}C_{27}^{23}x^{23}+2x^{16}C_{23}^{19}x^{19}-2x^{24}C_{15}^{11}x^{11}+2x^{28}C_{11}^{7}x^{7}-x^{32}C_{7}^{3}x^{3}$

Hệ số của $x^{35}$ cũng là số cách cho bi vào hộp thỏa ycđb:

$C_{31}^{27}-2C_{27}^{23}+2C_{23}^{19}-2C_{15}^{11}+2C_{11}^{7}-C_{7}^{3}$

$=31465-2.17550+2.8855-2.1365+2.330-35=11970$

Có bao nhiêu cách bỏ 35 viên bi giống nhau vào 5 hộp khác nhau sao cho: mỗi hộp 1 và 2 không có 0, 1, 2, 7, 8, 9 hoặc 10 bi; hộp 3 ít nhất 2 và nhiều nhất 9 bi; và hộp 4 và 5 không giới hạn bi.

Chỗ đỏ em chưa hiểu ạ.

Tìm số tự nhiên n nhỏ nhất sao cho n! tận cùng bằng 290 chữ số 0

Mỗi chữ số $0$ là kết quả của tích $2$ thừa số $2.5=10$. Do đó thừa số nguyên tố của n! có ít nhất $290$ thừa số $2$ và $290$ thừa số $5$. Vì thừa số $2$ nhiều hơn hẳn thừa số $5$ nên ta chỉ quan tâm đến số thừa số $5$.

Số thừa số $5$:

$p=\left \lfloor \frac{n}{5} \right \rfloor+\left \lfloor \frac{n}{5^{2}} \right \rfloor+\left \lfloor \frac{n}{5^{3}} \right \rfloor+....$

Áp dụng công thức gần đúng tính tổng: $S=a(\frac{1}{1-r})$ với $ a=\frac{n}{5}$ và $ r=\frac{1}{5}$:

$p=\frac{n}{5}(\frac{1}{1-\frac{1}{5}})=290$

$\rightarrow n=1160$

Thử lại:

$p=\left \lfloor \frac{1160}{5} \right \rfloor+\left \lfloor \frac{1160}{5^{2}} \right \rfloor+\left \lfloor \frac{1160}{5^{3}} \right \rfloor+\left \lfloor \frac{1160}{5^{4}} \right \rfloor=232+46+9+1=288$

Do đó để $p=290$ thì $n=1160+2.5=1170$

là sao bạn ?

Thí dụ câu $2$ nhé...

Xây dựng hàm sinh:

$f(x)=(x^{3}+x^{4}+x^{5})^{4}=x^{12}(1+x+x^{2})^{4}=x^{12}(\frac{1-x^{3}}{1-x})^{4}=x^{12}(1-x^{3})^{4}\frac{1}{(1-x)^{4}}$

mà:

$(1-x^{3})^{4}=1-4x^{3}+6x^{6}-4x^{9}+x^{12} $

$\frac{1}{(1-x)^{4}}=\sum_{k=0}^{\infty }C_{k+3}^{k}x^{k}=1+C_{4}^{1}x+C_{5}^{2}x^{2}+...+C_{k+3}^{k}x^{k}+...$

Số cách chia quà chính là hệ số của $x^{18}$ hay hệ số của $x^{6}$ trong $2$ thừa số ở $RHS$.

Số cách chia là:

$C_{9}^{6}-4C_{6}^{3}+6=84-80+6=10$

 Cám ơn bạn đã giải đáp bài viết của mình! mà bạn ơi cho mình hỏi từ m.n= 4.(m+n) bạn biến đổi như thế nào để ra được (m-4).(n-4) =16 vậy bạn?

Suy ngĩ chân phương thôi...

m.n - 4.(m+n)=0

mn-4m-4n+16=16

(m-4)(n-4)=16

Trước tiên mình xin cám ơn bạn đã giải đáp cho mình ! Nhưng mà đáp án của thầy mình đưa ra là 126 

Ta cho trước mỗi em 1 phần quà thì ta có pt:

x₁+x₂+...+x₆=4

với x_i nguyên và $\geq 0$

Số cách chia cũng là số nghiệm của pt:$C_{9}^{5}=126$

Gọi $m,n$ là số kỳ thủ của mỗi đội.

Theo đề bài ta có:

$m.n=4(m+n) $

$(m-4)(n-4)=16$

$m-4=\frac{16}{n-4}$

$n-4$ là ước của $16$

Tương ứng với $n-4=1,2,4,8,16$ ta có $n=5,6,8,12,20$ $\rightarrow m=20,12,8,6,5$

Vì số kỳ thủ của ít nhất một trong hai đội là lẻ nên chỉ có $(m,n)=(20,5)$ là thỏa đề bài.

Vậy: Một đội có $20$ kỳ thủ và đội kia có $5$ kỳ thủ.

Ta có:

$5^{1995}=5^{1984}.5^{11}$

Nếu ta cm được $(5^{1995}-5^{11})\vdots 10^{8}$ thì $5^{11}$ chính là 8 chữ số tận cùng của $5^{1995}$.

$5^{1995}-5^{11}=5^{11}(5^{1984}-1)$

Ta thấy:

$5^{1984}-1=(5^{31.32}-1)(5^{31.32}+1)=(5^{31.16}-1)(5^{31.16}+1)(5^{31.32}+1)=(5^{31.8}-1)(5^{31.8}+1)(5^{31.16}+1)(5^{31.32}+1)$

..................

$5^{1984}-1=(5^{31}-1)(5^{31}+1)(5^{31.2}+1)(5^{31.4}+1)(5^{31.8}+1)(5^{31.16}+1)(5^{31.32}+1)$

Nhận thấy $RHS$ có:

$(5^{31}-1)\vdots 2^{2}$

phần còn lại là tích $6$ số chẵn $\rightarrow $ tích $6$ thừa số này $\vdots 2^{6}$

Hay:

$(5^{1984}-1)\vdots 2^{8}$     $ (1)$

Hơn nữa:

$5^{11}\vdots 5^{8}$                 $(2)$

Từ $(1) $ và  $(2)$ ta được:

$(5^{1995}-5^{11})\vdots 10^{8}$

Hay nói cách khác: 8 chữ số tận cùng của $5^{1995}$ là $5^{11}=48828125$