Tel: 024.7300.7989 - Phone: 1800.6947 (Thời gian hỗ trợ từ 7h đến 22h)

Thi thử toàn quốc ĐGNL sư phạm Hà Nội 18-19/4/2026 Xem chi tiết
Giỏ hàng của tôi
Trang chủ
Luyện thi đại học môn toán

Xâu nhị phân là xâu chỉ chứa ký tự 0 hoặc 1. Gọi $a_{n}$ là số lượng xâu nhị phân có n ký

Câu hỏi số 955116:
Vận dụng

Xâu nhị phân là xâu chỉ chứa ký tự 0 hoặc 1. Gọi $a_{n}$ là số lượng xâu nhị phân có n ký tự và không chứa xâu con 00.

Đúng Sai
a) Ta có $a_{3} = 4$.
b) Xâu nhị phân có 11 ký tự không chứa xâu con 00 và có tận cùng bên phải bằng $1 = a_{10}$.
c) Tồn tại giá trị $n$ sao cho $a_{n + 2} < a_{n + 1} + a_{n}$.

Đáp án đúng là: S; Đ; S

Quảng cáo

Xem lời giải
Câu hỏi:955116
Phương pháp giải

Thiết lập hệ thức truy hồi cho dãy số $(a_{n})$ bằng cách chia các xâu thỏa mãn thành hai loại dựa vào ký tự cuối cùng.

Dựa vào hệ thức truy hồi để tính các giá trị cụ thể và kiểm tra tính đúng sai của từng mệnh đề.

Giải chi tiết

Xét các xâu nhị phân độ dài n không chứa xâu con 00.

Với $n = 1$, các xâu thỏa mãn là 0, 1. Suy ra $a_{1} = 2$.

Với $n = 2$, các xâu thỏa mãn là 01, 10, 11. Suy ra $a_{2} = 3$.

Với $n \geq 3$, một xâu nhị phân độ dài $n$ không chứa xâu con 00 có thể có ký tự tận cùng là 1 hoặc 0.

Nếu xâu có ký tự tận cùng là 1, thì $n - 1$ ký tự trước đó tạo thành một xâu độ dài $n - 1$ không chứa xâu con 00. Số lượng xâu như vậy là $a_{n - 1}$.

Nếu xâu có ký tự tận cùng là 0, thì để không xuất hiện xâu con 00, ký tự liền trước nó bắt buộc phải là 1. Tức là xâu kết thúc bằng 10. Khi đó, $n - 2$ ký tự trước đó tạo thành một xâu độ dài $n - 2$ không chứa xâu con 00. Số lượng xâu như vậy là $a_{n - 2}$.

Do đó, ta có hệ thức truy hồi: $a_{n} = a_{n - 1} + a_{n - 2}$ với mọi $n \geq 3$.

Xét mệnh đề a): Ta có $a_{3} = a_{2} + a_{1} = 3 + 2 = 5$.

Vậy mệnh đề a) Sai.

Xét mệnh đề b): Số lượng xâu nhị phân có 11 ký tự không chứa xâu con 00 và có tận cùng bên phải bằng 1 chính là trường hợp thứ nhất khi $n = 11$.

Theo chứng minh trên, số lượng xâu này bằng số lượng xâu hợp lệ có độ dài $11 - 1 = 10$, tức là bằng $a_{10}$.

Vậy mệnh đề b) Đúng.

Xét mệnh đề c): Từ hệ thức truy hồi $a_{n} = a_{n - 1} + a_{n - 2}$ với mọi $n \geq 3$, ta suy ra $a_{n + 2} = a_{n + 1} + a_{n}$ với mọi $n \geq 1$.

Do đó không tồn tại giá trị $n$ nào để $a_{n + 2} < a_{n + 1} + a_{n}$.

Vậy mệnh đề c) Sai.

Đáp án cần chọn là: S; Đ; S

Group 2K8 ôn Thi ĐGNL & ĐGTD Miễn Phí

Câu hỏi trước Câu tiếp theo

>>  2K8 Chú ý! Lộ Trình Sun 2026 - 3IN1 - 1 lộ trình ôn 3 kì thi (Luyện thi 26+ TN THPT, 90+ ĐGNL HN, 900+ ĐGNL HCM, 70+ ĐGTD - Click xem ngay) tại Tuyensinh247.com.Đầy đủ theo 3 đầu sách, Thầy Cô giáo giỏi, luyện thi theo 3 giai đoạn: Nền tảng lớp 12, Luyện thi chuyên sâu, Luyện đề đủ dạng đáp ứng mọi kì thi.

Hỗ trợ - Hướng dẫn

  • 024.7300.7989
  • 1800.6947 free

(Thời gian hỗ trợ từ 7h đến 22h)
Email: lienhe@tuyensinh247.com

Đăng ký nhận tư vấn