Câu hỏi 77
Ban đầu có $n$ chiếc cốc được đánh số $1, 2, \ldots, n$, và dung tích của cốc số $i$ là $i$ lít. Tổng cộng $n$ lít nước được phân chia vào các cốc này sao cho thể tích nước trong mỗi cốc là một số nguyên. Ở mỗi bước, ta có thể rót nước từ một cốc sang một cốc khác cho đến khi cốc nguồn cạn hoặc cốc đích đầy.
a. Chứng minh rằng từ một cấu hình bất kỳ (trong đó thể tích nước trong mỗi cốc là số nguyên), có thể đạt tới cấu hình mà mỗi cốc chứa đúng $1$ lít nước sau không quá $\frac{4n}{3}$ bước.
b. Chứng minh rằng từ một cấu hình bất kỳ (trong đó thể tích nước trong mỗi cốc là số nguyên), có thể đạt tới bất kỳ cấu hình nào khác có cùng tính chất sau không quá $\frac{5n}{3}$ bước.
a. Chứng minh rằng từ một cấu hình bất kỳ (trong đó thể tích nước trong mỗi cốc là số nguyên), có thể đạt tới cấu hình mà mỗi cốc chứa đúng $1$ lít nước sau không quá $\frac{4n}{3}$ bước.
b. Chứng minh rằng từ một cấu hình bất kỳ (trong đó thể tích nước trong mỗi cốc là số nguyên), có thể đạt tới bất kỳ cấu hình nào khác có cùng tính chất sau không quá $\frac{5n}{3}$ bước.