Câu hỏi 68
Cho $n$ là một số nguyên dương. Trên bảng, Bobo viết $n$ số nguyên không âm. Sau đó anh ta thực hiện một dãy các bước, mỗi bước như sau:
- với mỗi $i=1, \ldots, n$, anh ta tính số $a_{i}$ các số nguyên đang có trên bảng mà không vượt quá $i$,
- anh ta xóa mọi số trên bảng,
- anh ta viết lên bảng các số $a_{1}, a_{2}, \ldots, a_{n}$.
Ví dụ, nếu $n=5$ và các số ban đầu trên bảng là $0,7,2,6,2$ thì sau bước thứ nhất trên bảng là 1, 3, 3, 3, 3, sau bước thứ hai là 1, 1, 5, 5, 5, và cứ thế.
a. Chứng minh rằng với mọi $n$ và mọi cấu hình ban đầu, đến một lúc nào đó các số trên bảng sẽ không thay đổi nữa.
b. Theo $n$, xác định số nguyên $k$ nhỏ nhất sao cho với mọi cấu hình ban đầu, các bước từ bước thứ $k$ trở đi không làm thay đổi các số viết trên bảng.
- với mỗi $i=1, \ldots, n$, anh ta tính số $a_{i}$ các số nguyên đang có trên bảng mà không vượt quá $i$,
- anh ta xóa mọi số trên bảng,
- anh ta viết lên bảng các số $a_{1}, a_{2}, \ldots, a_{n}$.
Ví dụ, nếu $n=5$ và các số ban đầu trên bảng là $0,7,2,6,2$ thì sau bước thứ nhất trên bảng là 1, 3, 3, 3, 3, sau bước thứ hai là 1, 1, 5, 5, 5, và cứ thế.
a. Chứng minh rằng với mọi $n$ và mọi cấu hình ban đầu, đến một lúc nào đó các số trên bảng sẽ không thay đổi nữa.
b. Theo $n$, xác định số nguyên $k$ nhỏ nhất sao cho với mọi cấu hình ban đầu, các bước từ bước thứ $k$ trở đi không làm thay đổi các số viết trên bảng.