Đến nội dung


Chú ý

Nếu các bạn đăng kí thành viên mà không nhận được email kích hoạt thì hãy kiểm tra thùng thư rác (spam). Nếu không biết cách truy cập vào thùng thư rác thì các bạn chịu khó Google hoặc đăng câu hỏi vào mục Hướng dẫn - Trợ giúp để thành viên khác có thể hỗ trợ.


Hình ảnh

Tổ hợp - Chỉnh hợp :

bài mật khẩu

  • Chủ đề bị khóa Chủ đề bị khóa
Chủ đề này có 1 trả lời

#1 vankietcap

vankietcap

    Lính mới

  • Thành viên mới
  • 1 Bài viết

Đã gửi 03-01-2021 - 18:00

Một người cần lập mật khẩu từ các chữ cái {a,b,c,d} có độ dài ít nhất 6 ký tự nhưng tối đa là 10 ký tự, đồng thời số ký tự a bằng số ký tự b. Hỏi có bao nhiêu cách lập mật khẩu thỏa yêu cầu bài toán?

 


#2 Nobodyv2

Nobodyv2

    Hạ sĩ

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

Đã gửi 04-01-2021 - 22:39

Một người cần lập mật khẩu từ các chữ cái {a,b,c,d} có độ dài ít nhất 6 ký tự nhưng tối đa là 10 ký tự, đồng thời số ký tự a bằng số ký tự b. Hỏi có bao nhiêu cách lập mật khẩu thỏa yêu cầu bài toán?

Ta xét 2 TH:
a/ Mật khẩu không có cặp ký tự (a,b):
Số mật khẩu thuộc loại này là:
$2^{6}+2^{7}+2^{8}+2^{9}+2^{10}=2^{6}.\frac{2^{5}-1}{2-1}=64.31=1984$
b/ Mật khẩu có cặp ký tự (a,b):
+ Mật khẩu có 6 ký tự:
- có 1 cặp ký tự (a,b): $A_{6}^{2}.2^{4}=480$
- có 2 cặp ký tự (a,b): $C_{6}^{2}.C_{4}^{2}.2^{2}=360$
- có 3 cặp ký tự (a,b): $\frac{6!}{3!.3!}=20$
Số mật khẩu có 6 ký tự là:
$480+360+20=860$
+ Mật khẩu có 7 ký tự:
Tương tự, có:
$A_{7}^{2}.2^{5}+C_{7}^{2}.C_{5}^{2}.2^{3}+C_{7}^{3}.C_{4}^{3}.2=1344+1680+280=3304$
+ Mật khẩu có 8 ký tự:
$A_{8}^{2}.2^{6}+C_{8}^{2}.C_{6}^{2}.2^{4}+C_{8}^{3}.C_{5}^{3}.2^2+\frac{8!}{4!.4!}=3584+6720+2240+70=12614$
+ Mật khẩu có 9 ký tự:
$A_{9}^{2}.2^{7}+C_{9}^{2}.C_{7}^{2}.2^{5}+C_{9}^{3}.C_{6}^{3}.2^3+C_{9}^{4}.C_{5}^{4}.2=9216+24192+13440+1260=48108$
+ Mật khẩu có 10 ký tự:
$A_{10}^{2}.2^{8}+C_{10}^{2}.C_{8}^{2}.2^{6}+C_{10}^{3}.C_{7}^{3}.2^4+C_{10}^{4}.C_{6}^{4}.2^2+\frac{10!}{5!.5!}=23040+80640+67200+12600+252=183732$
Cộng các giá trị trên, ta có số mật khẩu thỏa yêu cầu là $250602$.

++++++++++++++++++++++
Để kiểm tra kết quả của lời giải trên, ta sẽ tiếp cận bài toán bằng cách khác, cụ thể như sau:
Gọi $P_{1}$ là tập các mật khẩu có kích thước là n gồm các ký tự thuộc tập $\left \{ a,b,c,d \right \}$ thỏa yc đề bài.
Gọi $P_{2}$ là tập các mật khẩu có n ký tự a và n ký tự b ( ngoài ra không có ký tự nào khác).
Ta sẽ chứng minh ánh xạ $f$ từ tập $P_{1}$ vào $P_{2}$ là song ánh.
Ta có: mật khẩu có độ dài n bao gồm các ký tự a,b,c,d và số các ký tự a bằng số các ký tự b được nhân đôi thành mật khẩu có độ dài 2n theo qui tắc:
+ Hai mật khẩu này được viết liền nhau thành mật khẩu có độ dài là 2n.
+ Các ký tự c ở n ký tự đầu được đổi thành ký tự a, các ký tự c ở n ký tự sau được đổi thành ký tự b.
Tương tự, các ký tự d ở n ký tự đầu được đổi thành ký tự b, các ký tự d ở n ký tự sau được đổi thành ký tự a.
Như vậy ta lập được một mật khẩu có đúng n ký tự a và n ký tự b$\rightarrow f$ là một đơn ánh.
Để chứng minh $f$ là toàn ánh, ta xét ánh xạ $f^{-1}$ sau đây:
Một mật khẩu có n ký tự a và n ký tự b, ta phân ra 2 phần: n ký tự đầu, n ký tự cuối sau đó xếp chúng thành 2 hàng, cột theo cột (tương tự như khi ta xếp 2 số để thực hiện phép cộng). Ta thực hiện phép cộng theo qui tắc:
$a+a \rightarrow a; b+b\rightarrow b; a+b \rightarrow c$ và $ b+a\rightarrow d.$
Như vậy ta sẽ có một mật khẩu có n ký tự thuộc $\left \{ a,b,c,d \right \}$ với số các ký tự a bằng số các ký tự b$\rightarrow f$ là một toàn ánh.
Suy ra $f$ là song ánh. Điều này kéo theo:
$\left | P_{1} \right |=\left | P_{2} \right |=C_{2n}^{n}$ $(*)$
Áp dụng $(*)$ vào bài toán, ta có số mật khẩu thỏa yc đề bài là:
$\sum_{n=6}^{10}C_{2n}^{n}=924+3432+12870+48620+184756=250602.$

Bài viết đã được chỉnh sửa nội dung bởi Nobodyv2: 07-01-2021 - 12:18

<p>Hi guys, my name is Nobody.
Đọc sách cho là đã nhiều, đụng tới việc mới biết rằng chưa đủ.
Hôm qua thì đã qua, ngày mai thì chưa tới, nên chúng ta hãy sống trọn vẹn cho ngày nay.




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

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