MathLabs

第5問

nn 人が円形に座っている。合計 nknk 枚の硬貨が必ずしも均等でなく配られている。1回の操作では隣り合う二人の間で硬貨1枚を移す。全員の硬貨枚数を等しくする最小操作回数のアルゴリズムを求めよ。
ステップ 5/5: 環をまたぐ操作と反復を比較する
X→0X\to0
詳しい解説

X=0X=0 になるまで減少操作を繰り返す。環の辺 XX を越す両方向の変化も計算し、1より大きく減る方向があればそれを選ぶ。各操作で XX は厳密に減少し、ポテンシャルの議論により最少回数で終了する。 n,1n,1 XX