Câu hỏi 16
Lão Triệu đi nghĩa vụ quân sự buồn chán quá, nên vẽ trên mặt đất $n + 1$ ô xếp thành một hàng ($n$ là số nguyên dương), đánh số từ trái sang phải là ô 0 đến ô $n$. Ban đầu, ô 0 có $n$ viên đá, các ô khác đều trống. Ở mỗi lượt, Lão Triệu trước hết chọn một ô khác rỗng, giả sử ô đó có $k$ viên đá. Sau đó, anh ấy lấy một viên đá từ ô đã chọn và di chuyển nó sang phải tối đa $k$ ô (viên đá không được vượt quá ô ngoài cùng bên phải). Mục tiêu của Lão Triệu là đưa tất cả các viên đá vào ô thứ $n$.
Chứng minh rằng số lượt Lão Triệu cần để đạt mục tiêu không ít hơn
$$
\left\lceil \frac{n}{1} \right\rceil + \left\lceil \frac{n}{2} \right\rceil + \left\lceil \frac{n}{3} \right\rceil + \cdots + \left\lceil \frac{n}{n} \right\rceil,
$$
trong đó $\lceil x \rceil$ là số nguyên nhỏ nhất không nhỏ hơn $x$.
Chứng minh rằng số lượt Lão Triệu cần để đạt mục tiêu không ít hơn
$$
\left\lceil \frac{n}{1} \right\rceil + \left\lceil \frac{n}{2} \right\rceil + \left\lceil \frac{n}{3} \right\rceil + \cdots + \left\lceil \frac{n}{n} \right\rceil,
$$
trong đó $\lceil x \rceil$ là số nguyên nhỏ nhất không nhỏ hơn $x$.