MathLabs

Bài 5

Có nn người ngồi thành vòng tròn. Tổng cộng có nknk đồng xu được phân phối, không nhất thiết đều. Một bước chuyển một đồng xu giữa hai người kề nhau. Hãy tìm thuật toán dùng ít bước nhất để cuối cùng mọi người có cùng số đồng xu.
Bước 2 trên 5: Định nghĩa thế năng tổng tiền tố
Bước trướcBước tiếp
X=∑i=1n−1∣∑j=1idj∣X=\sum_{i=1}^{n-1}\left|\sum_{j=1}^id_j\right|
Phân tích chi tiết

Đặt X=∑i=1n−1∣d1+⋯+di∣X=\sum_{i=1}^{n-1}|d_1+\cdots+d_i|. Đại lượng này bằng không khi và chỉ khi mọi did_i bằng không. Bước qua cạnh i,i+1i,i+1 với i<ni<n chỉ đổi tổng tiền tố thứ ii, nên đổi XX một đơn vị.