Đến nội dung

Hình ảnh

Có bao nhiêu số tự nhiên chia hết cho $3$, biết số đó gồm $2018$ chữ số lấy từ tập $X=\left \{ 3;5;7;9 \right \}$?


Lời giải hovutenha, 06-01-2023 - 20:37

Bài này sử dụng truy hồi

gọi tập số tự nhiên $n$ chữ số chia hết cho 3 là $A(n)$

gọi tập số tự nhiên $n$ chữ số chia cho 3 dư 1 là $B(n)$

gọi tập số tự nhiên $n$ chữ số chia cho 3 dư 2 là $C(n)$

Cần: $A(2018)$

Bài này cần xét chữ số cuối cùng

xét 1 số thuộc $A(n)$ thì có 2 cách chọn $(3,9)$ chữ số cuối cùng để tạo thành 1 số thuộc $A(n+1)$

xét 1 số thuộc $B(n)$ thì có 1 cách chọn $(5)$ chữ số cuối cùng để tạo thành 1 số thuộc $A(n+1)$

xét 1 số thuộc $C(n)$ thì có 1 cách chọn $(7)$ chữ số cuối cùng để tạo thành 1 số thuộc $A(n+1)$

suy ra: $A(n+1) = 2A(n) + B(n) + C(n)$

CMTT ta có $B(n+1)= A(n) + 2B(n) + C(n)$ và $C(n+1) = A(n) + B(n) + 2C(n)$

suy ra :

\begin{align*} A(n+1) & = 2A(n) + B(n) + C(n) \\ & = 2A(n) + A(n-1) + 2B(n-1) + C(n-1) + A(n-1) + B(n-1) + 2C(n-1) \\  & = 2A(n) - 4A(n-1) + 3(2A(n-1) + B(n-1) + C(n-1)) \\ & =5A(n) - 4A(n-1) \\ \Rightarrow A(n) & = 5A(n-1) - 4A(n-2)$ \end{align*}

sử dụng phương trình đặc trưng

$x^2 - 5x +4 =0$ có nghiệm $x=1$ và $x=4$

suy ra $A(n) = a + b4^n$

có $A(1) = 2$ và $A(2) = 6$  thay vào trên và giải hệ ta tìm được $a=\frac{2}{3}$ và $b =\frac{1}{3}$

suy ra $A(n) = \frac{2}{3} + \frac{1}{3}4^n$

suy ra $A(2018) = ....$

 

hôm nay mạng bị lag nên không gõ được latex, bạn thông cảm nhé!

Đi đến bài viết »


  • Please log in to reply
Chủ đề này có 5 trả lời

#1
Altuna

Altuna

    Lính mới

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

Có bao nhiêu số tự nhiên chia hết cho $3$, biết số đó gồm $2018$ chữ số lấy từ tập $X=\left \{ 3;5;7;9 \right \}$ ?


Bài viết đã được chỉnh sửa nội dung bởi HaiDangPham: 11-05-2023 - 10:24
LaTex


#2
hovutenha

hovutenha

    Hạ sĩ

  • Thành viên
  • 85 Bài viết
✓  Lời giải

Bài này sử dụng truy hồi

gọi tập số tự nhiên $n$ chữ số chia hết cho 3 là $A(n)$

gọi tập số tự nhiên $n$ chữ số chia cho 3 dư 1 là $B(n)$

gọi tập số tự nhiên $n$ chữ số chia cho 3 dư 2 là $C(n)$

Cần: $A(2018)$

Bài này cần xét chữ số cuối cùng

xét 1 số thuộc $A(n)$ thì có 2 cách chọn $(3,9)$ chữ số cuối cùng để tạo thành 1 số thuộc $A(n+1)$

xét 1 số thuộc $B(n)$ thì có 1 cách chọn $(5)$ chữ số cuối cùng để tạo thành 1 số thuộc $A(n+1)$

xét 1 số thuộc $C(n)$ thì có 1 cách chọn $(7)$ chữ số cuối cùng để tạo thành 1 số thuộc $A(n+1)$

suy ra: $A(n+1) = 2A(n) + B(n) + C(n)$

CMTT ta có $B(n+1)= A(n) + 2B(n) + C(n)$ và $C(n+1) = A(n) + B(n) + 2C(n)$

suy ra :

\begin{align*} A(n+1) & = 2A(n) + B(n) + C(n) \\ & = 2A(n) + A(n-1) + 2B(n-1) + C(n-1) + A(n-1) + B(n-1) + 2C(n-1) \\  & = 2A(n) - 4A(n-1) + 3(2A(n-1) + B(n-1) + C(n-1)) \\ & =5A(n) - 4A(n-1) \\ \Rightarrow A(n) & = 5A(n-1) - 4A(n-2)$ \end{align*}

sử dụng phương trình đặc trưng

$x^2 - 5x +4 =0$ có nghiệm $x=1$ và $x=4$

suy ra $A(n) = a + b4^n$

có $A(1) = 2$ và $A(2) = 6$  thay vào trên và giải hệ ta tìm được $a=\frac{2}{3}$ và $b =\frac{1}{3}$

suy ra $A(n) = \frac{2}{3} + \frac{1}{3}4^n$

suy ra $A(2018) = ....$

 

hôm nay mạng bị lag nên không gõ được latex, bạn thông cảm nhé!


Bài viết đã được chỉnh sửa nội dung bởi perfectstrong: 31-03-2023 - 15:03
LaTeX


#3
Nobodyv3

Nobodyv3

    Generating Functions Faithful

  • Thành viên
  • 935 Bài viết
Cũng có thể dùng định lý về căn bậc 3 của đơn vị để tiếp cận bài toán, nhưng không biết có phù hợp với topic này không...
===========
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...

#4
Nobodyv3

Nobodyv3

    Generating Functions Faithful

  • Thành viên
  • 935 Bài viết
<p>Lỗi rồi...&nbsp;</p>
Lang thang rồi gặp lại bài này, thôi thì mình trình bày luôn, hy vọng các bạn xem thì không bổ bề dọc cũng bổ bề ngang!.
Xét đa thức :
$f(x)=(x^3+x^5+x^7+x^9)^{2018}$
Gọi $\omega =e^{2\pi i/3}$ là một nghiệm của phương trình $x^3-1=0$ thì theo định lý RUF ta có $1+\omega+\omega^2=0 $ và số các số chia hết cho 3 là : $N=\frac {f(1)+f(\omega )+f(\omega ^2)}{3}$.
Ta có :
$f(1)=4^{2018}; f(\omega )=(2+\omega ^5+\omega ^7)^{2018}=1$ và $ f(\omega^2 )=(2+\omega ^{10}+\omega ^{14})^{2018}=1$.
Do đó số các số thỏa yêu cầu là :
$N=\frac {4^{2018}+1+1}{3}=\boldsymbol {\frac {4^{2018}+2}{3}}$

Bài viết đã được chỉnh sửa nội dung bởi Nobodyv3: 30-03-2023 - 08:26

===========
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...

#5
hxthanh

hxthanh

    Tín đồ $\sum$

  • Hiệp sỹ
  • 3915 Bài viết
Tự nhiên nghĩ ra cách này không biết có đúng không?
Trong tập $X=\{3,5,7,9\}$ nếu ta thay số $5$ bằng số $8$ thì kết quả bài toán không đổi vì $8\equiv 5\equiv 2\!\!\pmod 3$. Tương tự thay $3$ bởi $6$, ta có tập mới $Y=\{6,7,8,9\}$
Mặt khác do $\gcd(3,4)=1$ nên ta có thể thay tập $Y$ trên bởi $Z=\{2,3,0,1\}$ đồng dư theo modul $4$

Số các số nguyên dương không quá $M$ chia hết cho $N$ là $\left\lfloor\frac{M}{N}\right\rfloor$

Bài toán của ta trở thành: “Có bao nhiêu số tự nhiên trong hệ cơ số $4$ có không quá $n$ chữ số, mà chia hết cho $3$”

Như vậy đáp số cho bài toán là $\left\lfloor\frac{4^n-1}{3}\right\rfloor+1$

Bài viết đã được chỉnh sửa nội dung bởi hxthanh: 30-04-2023 - 09:49


#6
Nobodyv3

Nobodyv3

    Generating Functions Faithful

  • Thành viên
  • 935 Bài viết
Tuyệt vời!
Một cách giải Made in hxthanh và $hxthanh^{ \textregistered}$
===========
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 người đang xem chủ đề

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