JMO 2016
問題 3

国民が持つ硬貨の枚数の合計は広義単調減少なので $S$ が不変である場合を考えれば良い．

非負整数 $m$ に対して，$m$ を $2^n$ で割った余りを $2$ 進数表示したときの桁和を $p(m)$ とする．徴税開始日に各国民が持っている金額を $a_1,a_2,\dots,a_{2^n}$ とすると任意の $k$ に対して

$$\sum_{i=1}^{2^n}p(a_i-k)\leq S$$

が成り立つので以下の評価により $S\geq n\cdot 2^{n-1}$ を得る．

$$2^nS\geq \sum_{i=1}^{2^n}\sum_{k=1}^{2^n}p(a_i-k)=\sum_{i=1}^{2^n}\sum_{k=1}^{2^n}p(k)=2^n\cdot n\cdot 2^{n-1}$$

一方で各国民がそれぞれ $0,1,2,\dots,2^n-1$ 円を最小の硬貨の枚数で持っている状態から永遠に徴税をすることは可能であり，このとき $S=n\cdot 2^{n-1}$ が実現される．以上より求める最小値は $n\cdot 2^{n-1}$ である．