Câu hỏi 12
Cho số nguyên dương $n$ và một bảng chơi gồm $n+1$ ô vuông xếp thành một hàng, được đánh số từ trái sang phải từ $0$ đến $n$. Lúc bắt đầu trò chơi, có $n$ viên đá trên ô số $0$ và các ô khác đều trống.
Một người chơi kiên nhẫn, ở mỗi nước đi, chọn một ô có $k \neq 0$ viên đá và dịch một viên trong số đó sang phải nhiều nhất $k$ ô. Viên đá phải ở lại trên bảng. Mục tiêu của anh ta là đưa tất cả $n$ viên đá đến ô số $n$ bằng một dãy các nước đi như vậy.
Chứng minh rằng người chơi không thể đạt được mục tiêu này với ít hơn $\left\lceil\frac{n}{1}\right\rceil+\left\lceil\frac{n}{2}\right\rceil+\left\lceil\frac{n}{3}\right\rceil+\ldots+\left\lceil\frac{n}{n}\right\rceil$ nước đi. (Ở đây $\lceil x\rceil$ kí hiệu số nguyên nhỏ nhất không nhỏ hơn $x$.)
Một người chơi kiên nhẫn, ở mỗi nước đi, chọn một ô có $k \neq 0$ viên đá và dịch một viên trong số đó sang phải nhiều nhất $k$ ô. Viên đá phải ở lại trên bảng. Mục tiêu của anh ta là đưa tất cả $n$ viên đá đến ô số $n$ bằng một dãy các nước đi như vậy.
Chứng minh rằng người chơi không thể đạt được mục tiêu này với ít hơn $\left\lceil\frac{n}{1}\right\rceil+\left\lceil\frac{n}{2}\right\rceil+\left\lceil\frac{n}{3}\right\rceil+\ldots+\left\lceil\frac{n}{n}\right\rceil$ nước đi. (Ở đây $\lceil x\rceil$ kí hiệu số nguyên nhỏ nhất không nhỏ hơn $x$.)