Câu hỏi 157
Cho $n$ là một số nguyên dương. Sisyphus thực hiện một dãy lượt đi trên một bảng gồm $(n+1)$ ô xếp thành một hàng, đánh số từ $0$ đến $n$ từ trái sang phải. Ban đầu, $n$ viên đá được đặt vào ô $0$, các ô khác để trống. Ở mỗi lượt, Sisyphus chọn một ô khác rỗng bất kì, giả sử ô đó có $k$ viên đá, lấy một viên trong số đó và di chuyển nó sang phải không quá $k$ ô (viên đá phải ở lại trên bảng). Mục tiêu của Sisyphus là chuyển tất cả $n$ viên đá đến ô $n$.
Chứng minh rằng Sisyphus không thể đạt mục tiêu với ít hơn
$$
\left[ \frac{n}{1} \right] + \left[ \frac{n}{2} \right] + \left[ \frac{n}{3} \right] + \dots + \left[ \frac{n}{n} \right]
$$
lượt. (Như thường lệ, $[x]$ kí hiệu số nguyên nhỏ nhất không nhỏ hơn $x$.)
Chứng minh rằng Sisyphus không thể đạt mục tiêu với ít hơn
$$
\left[ \frac{n}{1} \right] + \left[ \frac{n}{2} \right] + \left[ \frac{n}{3} \right] + \dots + \left[ \frac{n}{n} \right]
$$
lượt. (Như thường lệ, $[x]$ kí hiệu số nguyên nhỏ nhất không nhỏ hơn $x$.)