MathLabs

第5题

nn 个人围坐成圈,共分配 nknk 枚硬币但不一定平均。一步是相邻两人之间转移一枚硬币。求一个用最少步数使每人硬币数相同的算法。
第 1/5 步:表示不平衡量
di=ci−k,∑i=1ndi=0d_i=c_i-k,\qquad\sum_{i=1}^nd_i=0
详细分析

按圆周编号,令 cic_i 为初始硬币数并置 di=ci−kd_i=c_i-k。由于总数为 nknk,有 ∑i=1ndi=0\sum_{i=1}^nd_i=0。重新编号使 d1≥0d_1\ge0。