Lời giải Bài 9:
Xét $a_n$. Số các tập thuộc $a_n$ có $i$ phần tử là $\binom{n-i+1}{i}$ vì ta chỉ chọn các phần tử $i, i+1, ...,n$
Do đó $a_n=\sum_{i<n-i+1}\binom{n-i+1}{i}$
Xét $b_n$. Ta đếm số các tập thuộc $b_n$ có $i$ phần tử. Gọi các phần tử đó là $x_1 < x_2 < ... <x_i$ thì theo đề bài $1 \leq x_1 < x_2 - 1 < x_3 -2 ... <x_i-(i-1)\leq n -i +1$. Đặt $y_i=x_i-(i-1)$ thì số tập thuộc $b_n$ có $i$ phần tử bằng số các dãy $y_1,y_2,..,y_i$ mà $1\leq y_1 < y_2 <...<y_i \leq n-i+1$ hay bằng $\binom{n-i+1}{i}$. Do đó $b_n=\sum_{i<n-i+1}\binom{n-i+1}{i}$ hay ta có $a_n=b_n$
Đề xuất Bài 10: Xét một số tự nhiên được biểu diễn trong hệ nhị phân. Ta gọi một khoảng cách nhị phân là một khoảng gồm các số $0$ liền nhau và ở hai đầu của nó là hai số $1$. Ví dụ số $548=1000100100_{2}$ có hai khoảng cách nhị phân là $000$ và $00$.
Hỏi từ $1$ tới $4095$ có bao nhiêu số mà độ dài các khoảng cách nhị phân của nó nhỏ hơn hoặc bằng $3$?
- bangbang1412, canhhoang30011999, Long Phi và 2 người khác yêu thích