Có bao nhiêu số tự nhiên có 40 chữ số được lấy từ {1, 2, 3} mà tổng các chữ số là chẵn

Bài toán tổ hợp trong đề thi học sinh giỏi tỉnh Quảng Ngãi năm học 2020-2021 (thi ngày 4/12/2020) có nội dung như sau.

Bài toán.


Có bao nhiêu số tự nhiên có 40 chữ số được lấy từ các chữ số 1, 2, 3 mà tổng các chữ số trong số tự nhiên đó là chẵn?

Lời giải 1. (N-Hữu Thuân)


Tổng các chữ số của số tự nhiên cần lập là chẵn nên số chữ số $2$ là chẵn.
+ Với mỗi $k \in \{ 0,2,4,...,40\} $, số cách chọn $k$ vị trí đề điền chữ số $2$ là $C_{40}^k$
tương ứng, số cách chọn vị trí và điền hai chữ số còn lại là $2^{40-k}$
+ Như vậy số các số tự nhiên thỏa yêu cầu bài toán là:
$\displaystyle \sum_{i=0}^{20}C_{40}^{2i}2^{40-2i}=\dfrac{(2-1)^{40}+(2+1)^{40}}{2}\\ = \dfrac{1+3^{40}}{2}=6078832729528464401.$

Lời giải 2. (Hoài Việt)


Gọi $A(n), B(n)$ là tập các số tự nhiên có $n$ chữ số được lập từ các số $1, 2, 3$ và có tổng các số lần lượt là chẵn và lẻ.
Gọi $a(n),b(n)$ lần lượt là số phần tử của tập $A(n), B(n).$
Từ mỗi số thuộc tập $A(n)$ có 2 cách thêm một số vào cuối số đó để tạo thành số thuộc tập $B(n+1)$ và 1 cách thêm để tạo thành số thuộc tập $A(n+1)$.
Từ mỗi số thuộc tập $B(n)$ có 2 cách thêm vào cuối số đó để tạo thành số thuộc tập $A(n+1)$ và 1 cách thêm để tạo thành số thuộc tập $B(n+1)$.
Dẫn đến $a(n+1)= a(n)+2b(n)$ và $b(n+1)=2a(n)+b(n)$.
Suy ra $a(n+1)=a(n) + 2(2a(n-1) + b(n-1))\\ =a(n)+4a(n-1)+2b(n-1)\\ =an+4a(n-1) +a(n) - a(n-1)\\ =2a(n)+3a(n-1)$
Và $a(1)=1; a(2)=5$ nên ta có được dãy truy hồi $a(n)$ với: $a(1)=1; a(2)=5;\\ a(n+1)=2a(n)+3a(n-1)$
Từ đó ta tính được
$$a(40)= 6078832729528464401.$$
Lưu ý: Dùng phương trình sai phân, ta tìm được công thức số hạng tổng quát
$$a(n)=\dfrac{(-1)^n+3^n}{2}.$$
Theo FB MathVN. Người đăng: Mr. Math.

Đăng nhận xét

Please Select Embedded Mode To Show The Comment System.*

Mới hơn Cũ hơn