Câu hỏi 89
Bản dịch phát biểu gốc tiếng Anh:
Một giá sách có $n$ tập, mang nhãn từ $1$ đến $n$ theo một thứ tự nào đó. Thủ thư muốn xếp chúng đúng thứ tự như sau. Thủ thư chọn một tập nằm quá xa về bên phải, chẳng hạn tập mang nhãn $k$, lấy ra và chèn sao cho nó ở vị trí thứ $k$. Ví dụ, nếu giá sách đang có thứ tự $1,3,2,4$, thủ thư có thể lấy tập $2$ và đặt ở vị trí thứ hai. Khi đó sách có thứ tự đúng $1,2,3,4$.
a. Chứng minh nếu lặp quy trình thì dù thủ thư chọn thế nào, cuối cùng mọi tập đều đúng thứ tự.
b. Số bước lớn nhất mà quy trình có thể thực hiện là bao nhiêu?
Bản dịch phát biểu song song tiếng Pháp:
Một giá sách có $n$ tập, mang nhãn từ $1$ đến $n$ theo một thứ tự nào đó. Thủ thư muốn xếp chúng đúng thứ tự như sau. Thủ thư chọn một tập nằm quá xa về bên phải, chẳng hạn tập mang nhãn $k$, lấy ra và chèn sao cho nó ở vị trí thứ $k$. Ví dụ, nếu giá sách đang có thứ tự $1,3,2,4$, thủ thư có thể lấy tập $2$ và đặt ở vị trí thứ hai. Khi đó sách có thứ tự đúng $1,2,3,4$.
a. Chứng minh nếu lặp quy trình thì dù thủ thư chọn thế nào, cuối cùng mọi tập đều đúng thứ tự.
b. Số bước lớn nhất mà quy trình có thể thực hiện là bao nhiêu?
Một giá sách có $n$ tập, mang nhãn từ $1$ đến $n$ theo một thứ tự nào đó. Thủ thư muốn xếp chúng đúng thứ tự như sau. Thủ thư chọn một tập nằm quá xa về bên phải, chẳng hạn tập mang nhãn $k$, lấy ra và chèn sao cho nó ở vị trí thứ $k$. Ví dụ, nếu giá sách đang có thứ tự $1,3,2,4$, thủ thư có thể lấy tập $2$ và đặt ở vị trí thứ hai. Khi đó sách có thứ tự đúng $1,2,3,4$.
a. Chứng minh nếu lặp quy trình thì dù thủ thư chọn thế nào, cuối cùng mọi tập đều đúng thứ tự.
b. Số bước lớn nhất mà quy trình có thể thực hiện là bao nhiêu?
Bản dịch phát biểu song song tiếng Pháp:
Một giá sách có $n$ tập, mang nhãn từ $1$ đến $n$ theo một thứ tự nào đó. Thủ thư muốn xếp chúng đúng thứ tự như sau. Thủ thư chọn một tập nằm quá xa về bên phải, chẳng hạn tập mang nhãn $k$, lấy ra và chèn sao cho nó ở vị trí thứ $k$. Ví dụ, nếu giá sách đang có thứ tự $1,3,2,4$, thủ thư có thể lấy tập $2$ và đặt ở vị trí thứ hai. Khi đó sách có thứ tự đúng $1,2,3,4$.
a. Chứng minh nếu lặp quy trình thì dù thủ thư chọn thế nào, cuối cùng mọi tập đều đúng thứ tự.
b. Số bước lớn nhất mà quy trình có thể thực hiện là bao nhiêu?